버블 정렬(Bubble Sort)

버블 정렬은 단계별로 인접한 수를 비교하여 큰 수를 배열의 뒤로 보내서 정렬하는 것을 말합니다.

예를 들어서 설명해 보겠습니다.

 

정렬하고자 하는 배열은 "4 5 3 6 7 2 1" 이고 이를 오름차순 정렬해보겠습니다.

---

일단 앞에서부터 이웃한 두 수를 비교해서 인덱스 i 번째 수 보다 i + 1 번째 수가 작다면(array[i] > array[i+1]) 두 수를 바꿔줍니다.

위의 그림에서 이웃한 두 수 4, 5를 비교했을 때 i 번째 수(4)보다 i+1 번째 수(5)가 더 크므로 바꿔주지 않고 다음 인덱스로 넘어갑니다.

5, 3을 비교했을 때는 i 번째 수(5)보다 i+1 번째 수(3)가 더 작으므로 두 수를 바꿔줍니다.

 

[1 단계]

이런 식으로 배열의 끝까지 진행하면 가장 큰 수가 배열의 맨 끝에 위치하게 됩니다.

배열의 끝까지 탐색을 완료하면 다시 위의 과정을 처음부터 시작합니다.

---

[2 단계]

마찬가지로 이웃한 두 수를 비교해서 i번째 수보다 i+1번째 수가 더 작다면 두 수를 바꿔줍니다.

이 때, 1단계에서 가장 큰 수가 배열의 끝으로 가게 만들어주었으므로, 2단계에서는 2번째로 큰 수가 배열의 끝-1에 가도록 만들어 주어야 합니다.

따라서, 2단계에서는 배열길이를 n이라고 했을 때, n-1 숫자까지만 비교해야합니다.

그 결과 n-1번째 인덱스에 두 번째 큰 수(6)가 위치하게 됩니다.

---

[3 단계]

3단계에서도 위의 과정을 반복합니다. 3단계 결과는 n-2 위치에 3번째로 큰 수를 오게 합니다.

---

[4 단계]

---

[5 단계]

---

[6 단계]

---

이 과정을 반복하면 "1 2 3 4 5 6 7"인 오름차순 정렬된 배열을 구할 수 있습니다.

시간복잡도는 2중 for문을 사용하므로 O(n^2)이 됩니다.

 

내림차순 정렬을 할 때는 i번째 수와 i+1번째 수를 비교해서 i번째 수가 i+1번째 수보다 더 작으면(array[i] < array[i+1]) 두 수를 바꿔주게만 하면 됩니다. 이런 식으로 하면 1단계에서는 가장 작은 수가 n번째 위치에 위치하게 됩니다. 위의 배열을 예시로 보면 1이 배열의 끝에 위치하게 될 것입니다.

---

소스코드 : https://gist.github.com/fpdjsns/bcd325e4757bcf16c35768145eb7cf5a

Bubble_Sort. [Input : The first line contains an integer, n, denoting the number of an array size. next line contains n space-se

실행결과