DKU/알고리즘 및 실습

Bubble Sort Algorithm

marvel_hyeon 2024. 10. 3. 00:38
728x90

거품 정렬(bubble sort)는 정렬 알고리즘의 하나로, Selection Sort 알고리즘과 유사하다.

서로 인접한 두 원소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.

 

거품 정렬은 첫번째 원소와 두번째 원소 → 두번째 원소와 세번째 원소 → 세번째 원소와 네번째 원소 ・・・ 처럼 인접한 두 원소를 비교하며 정렬한다. 마지막 두개의 원소의 크기를 비교하여 정렬을 마치면 1회전이 끝난 것이고, 제일 큰 원소가 맨 마지막에 위치하게 된다. 2회전을 시작할 때는 이미 정렬된 맨 마지막 원소를 제외하고 비교를 시작한다. 이렇게 회전 수가 늘어날 마다 정렬해야하는 배열에서 제외되는 원소 수가 늘어난다.


Bubble Sort 수도 코드

 

i가 1부터 배열 A의 길이까지 반복하고,

j가 배열A의 길이에서 i+1이 될때까지 반복한다. (바꿔말하면 (배열A의 길이 - i)값만큼 반복)

만약 A[j]의 값이 A[j - 1]보다 작으면, 두 요소의 자리를 교환한다.

 

위 수도 코드에 의하면 맨 오른쪽 요소부터 크기 비교를 하기 시작한다.

한바퀴 돌면 i의 크기가 1 커지고, j의 크기가 1만큼 줄면서, 이미 정렬된 맨 오른쪽 요소를 빼고 다시 반복을 시작한다.


외부의 반복문이 n번 돌아가면, 내부의 반복문은 (n-1) + (n-2) ・・・ + 2 + 1 번 돌아간다.

즉, n(n-1)/2번 반복된다.

 

풀어서 설명해보자면,

외부의 i 반복문이 4번 돌아간다고 하자. 배열 A의 길이가 4인 것이다.

그러면 j는 1회전을 하기까지 4번, 2회전을 하기까지 3번... 마지막 회전을 할때는 1번의 반복이 일어난다.

 

따라서 거품 정렬의 실행 시간은 T(n) = n(n-1)/2, 시간복잡도는 O($n^2$)이라고 볼 수 있다.

'DKU > 알고리즘 및 실습' 카테고리의 다른 글

Heap Sort Algorithm  (0) 2024.10.16
Recurrences  (0) 2024.10.08
Growth of Functions  (0) 2024.09.26
Merge Sort Algorithm  (0) 2024.09.25
Insertion Sort Algorithm  (0) 2024.09.11