Bubble Sort(거품 정렬)

Bubble Sort(거품 정렬)

2021. 8. 5. 00:38ㆍ카테고리 없음

n-1번의 round

각 round마다 2개 값씩 비교

코드

Round 1

초기상태: 정렬을 하고자 하는 list

1. 0번째와 1번째를 비교 -> 교환(8>5)

2. 1번째와 2번째를 비교 -> 교환(8>6)

3. 2번째와 3번째를 비교 -> 교환(8>2)

Round 2

4. 0번째와 1번째를 비교 -> 교환하지 않는다(5<6)

5. 1번째와 2번째를 비교 -> 교환(6>2)

6. 2번째와 3번째를 비교 -> 교환하지 않는다(6<8)

Round 3

7. 0번째와 1번째를 비교 -> 교환(5>2)

8. 1번째와 2번째를 비교 -> 교환하지 않는다(5<6)

9. 2번째와 3번째를 비교 -> 교환하지 않는다(6<8)

교환: (n-1)+(n-2)+(n-3)+...+2+1 = n*(n-1)/2

비교: (n-1)+(n-2)+(n-3)+...+2+1 = n*(n-1)/2

T(n) = O(n^2)

장점

단점

순서에 맞지 않은 요소를 인접한 요소와 교환한다.
하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

출처

https://www.youtube.com/watch?v=Du-EHAUE0kM&list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl&index=16