[정렬] 버블소트

 정렬중 가장 기본적인 정렬이고, 구현이 가장 쉽다는 장점이 있다. 하지만 시간이 비교적 오래걸린다는 단점을 가지고 있다.

 n번째 수와 n-1번째 수를 비교하여 큰수를 오른쪽으로 보낸다. 이 과정을 배열의 처음부터 끝까지 반복하면 제일 마지막에는 가장 큰 수가 올것이다. 이걸 n번 반복하면 결국은 모든 수가 오름차순으로 정렬이 된다.

9

3

1

7

5

3

9

1

7

5

3

1

9

7

5

3

1

7

9

5

3

1

7

5

9

<Step 1>

 위 과정을 n번 반복하게되면 정렬된 배열이 나오게된다.

 버블소트의 worstcase는 입력되는 수가 역순으로 들어왔을 때 이고, averagecase역시 이며,  bestcase로는 이미 정렬이 되어있을 때의 O(1)이다. 

공간 복잡도는 배열의 크기인 O(1)이다.

3

1

7

5

9

1

3

7

5

9

1

3

7

5

9

1

3

5

7

9

1

3

5

7

9

<Step 2>

위 경우는 운좋게 두번만에 정렬이 되지만 코딩상 

이 과정을 <Step 5>까지 반복하게 된다.

< 출처 : 유투브(YouTube) - Bubble Sort >

(c++)

(java)