[정렬 알고리즘] 버블 소팅

A. 정렬 알고리즘

1. 버블 소팅

a. 버블 소팅이란?

🌟 서로 인접한 두 원소를 비교하며 리스트나 배열의 요소들을 정렬하는 방법

 

컴퓨터 과학 및 프로그래밍에서 사용되는 정렬 알고리즘 중 하나

간단하고 이해하기 쉽다

 

b. 작동방식

1) 비교 단계

 

리스트 또는 배열을 처음부터 끝까지 반복하면서 인접한 두 요소를 비교

이때, 첫 번째 요소가 두 번째 요소보다 크다면 두 요소를 교체

2) 교체 단계

 

만약 첫 번째 요소가 두 번째 요소보다 크면 두 요소를 교체

그 결과로 큰 요소가 리스트의 끝쪽으로 "버블"처럼 이동하게 되며, 작은 요소는 앞쪽으로 이동

 

3) 반복

 

비교와 교체 단계를 리스트의 첫 번째 요소부터 마지막 요소까지 계속 반복 : 패스

이러한 과정을 하나의 패스(pass)라고 부르며, 패스가 끝나면 가장 큰 요소가 리스트의 마지막 위치로 이동

4) 정렬이 완료될 때까지 반복

 

위의 과정을 리스트가 정렬될 때까지 반복

즉, 패스를 수행하면 리스트에서 가장 큰 요소가 마지막 위치로 이동하게 되므로,

정렬되지 않은 부분 리스트의 크기가 1 감소함

정렬이 완료될 때까지 이러한 패스를 반복하여 리스트를 정렬

 

🎨 도식화

 

도식화 하자면 이런 느낌 / https://wonjayk.tistory.com/219

 

c. 장점과 단점

👍 장점

• 단순하고 이해하기 쉬움
• 작은 크기의 데이터나 리스트가 이미 거의 정렬되어 있는 경우에는 버블 소팅이 유용

 

👎 단점

• 대규모 데이터에 대해서는 비효율적
• 평균 및 최악의 경우 시간 복잡도는 O(n^2)
• 더 효율적인 정렬 알고리즘(예: 병합 정렬, 퀵 소트)을 사용하는 것이 좋을 수 있음

 

d. 버블 소팅 코드

📘 문법

//1. 스왑하는 기능 
void Swap(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}

//버블 소팅기능 생성
//int lotto[6] = { 1, 42, 3, 15, 5, 6 }; 를 소팅한다고 가정
void Sort(int* numbers, int count) {	//2.
	for (int i = 0; i < count; i++) {	//6.
		for (int j = 0; j < count - 1 - i; j++) {	//3. 5.
			if (numbers[j] > numbers[j + 1]) {	//4.
				Swap(numbers[j], numbers[j + 1]);
			}
		}
	}
}

 

🤍 문법 설명

 

1. Swap : a와 b를 스왑하는 기능을 생성 
2. Sort : 배열과 배열의 길이를 입력받고
3. 5번 비교를 하면 6번째에는 비교할게 없으니 count -1을 해줌
4. n번과 n+1번을 비교하고 조건에 맞다면 둘 위치를 변경
5. 한 번 패스가 돌았다면 맨 마지막 배열은 가장 큰 배열이니 다시 검사 안해도 됨  = i번째도 빼줌
6. 위의 검증을 총 배열의 길이 -1만큼 해줘야 하니 2중 for문을 작성함

 

 

 

---

출처 : https://chat.openai.com/