버블 정렬(Bubble Sort) vs 선택정렬(Selection Sort) vs 삽입정렬(Insertion Sort)

 

버블 정렬과 선택정렬, 그리고 삽입정렬은 정렬 중 가장 기초적인 정렬들 입니다.

우선 버블 정렬부터 살펴보겠습니다.

 

버블 정렬(Bubble Sort)

- 오른쪽에서 정렬을 시작하여 왼쪽으로 가며, 본인의 값이 왼쪽의 값보다 작을 경우 위치를 변경해주는 정렬입니다.

- 한 사이클이 지나면 맨 왼쪽의 값은 항상 가장 작은 값이 됩니다. 따라서 다음 사이클은 맨 좌측 값 하나를 제외하고 돌립니다.

 

ex) int[] arr = { 3, 2, 1 }이고, 버블 정렬을 통해 정렬하라고 하면,

<첫 사이클>

1) 2와 1을 비교합니다. 2가 더 크므로 둘의 위치를 교체해줍니다. => {3, 1, 2}

2) 3과 1을 비교합니다. 3이 더 크므로 둘의 위치를 교체해줍니다. => {1, 3, 2}

<둘째 사이클>

3) 3과 2를 비교합니다. 3이 더 크므로 둘의 위치를 교체해줍니다. => {1, 2, 3}

 

이렇게 사이클 두번만에 모든 숫자가 정렬 되었습니다.

 

버블 정렬의 시간복잡도는 (n-1) + (n-2) + (n-3) ... + 1 ~= (n^2)/2 입니다.

따라서 O(n^2) 입니다.

 

선택 정렬(Selection Sort)

- 선형 탐색을 통해 가장 작은 값과 그 값의 위치를 기억했다가, 맨 왼쪽으로 교체해주는 정렬입니다.

- 버블 정렬과 마찬가지로, 가장 작은 값들을 계속해서 찾기 때문에, 다음 사이클은 맨 좌측 값 하나를 제외하고 돌립니다.

 

ex) int[] arr = {3, 2, 1} 이고, 선택 정렬을 통해 정렬하라고 하면,

<첫 사이클>

1) 선형 탐색을 통해 가장 작은 값은 1로 밝혀짐. => 맨 좌측으로 이동해야 하기 때문에 3과 1의 위치 변경. => {1, 2, 3}

<둘째 사이클>

2) 선형 탐색을 통해 가장 작은 값은 2로 밝혀짐. => 이미 올바른 위치임. => {1, 2, 3}

 

이렇게 모든 숫자가 정렬 되었습니다.

 

선택 정렬의 시간복잡도는 (n-1) + (n-2) + (n-3) ... + 1 ~= (n^2)/2 입니다.

따라서 O(n^2) 입니다.

 

 

삽입 정렬(Insertion Sort)

- 수열의 왼쪽의 숫자부터 순서대로 정렬하는 알고리즘입니다.

- 왼쪽에는 정렬된 숫자들이, 오른쪽에는 아직 정렬되지 않는 숫자들이 있게되고, 우측 숫자들에서 차례대로 왼쪽으로 하나씩 보내며 위치를 지정하는 정렬입니다.

- 원래 존재하는 숫자들보다 작을 경우 왼쪽으로 한칸씩 이동하고, 클 경우 다음 사이클을 돕니다.

 

ex) int[] arr = {3, 2, 1} 이고, 삽입 정렬을 통해 정렬하라고 하면,

<첫 사이클>

1) 숫자 3을 정렬합니다. 숫자가 하나이니 그대로 유지합니다.

<정렬된 숫자>         <정렬안된 숫자>

3                                      2, 1

 

<둘째 사이클>

2) 숫자 2를 정렬합니다. 원래 있던 3보다 작기 때문에 왼쪽으로 한칸 이동합니다.

<정렬된 숫자>        <정렬안된 숫자>

 2, 3                                  1

 

<셋째 사이클>

3) 숫자 1을 정렬합니다. 원래 있던 3보다 작기 때문에 왼쪽으로 한칸 이동합니다.

<정렬된 숫자>        <정렬안된 숫자>

 2, 1, 3                                

 

4) 원래 있던 2보다 작기 때문에 왼쪽으로 한칸 더 이동합니다.

<정렬된 숫자>        <정렬안된 숫자>

 1, 2, 3 

 

이렇게 사이클 세 번 만에 정렬이 완료되었습니다.

 

삽입 정렬의 시간복잡도는 k라운드에서 k-1번 일어나게 되므로 1 + 2 + 3 + ... + n-1 ~= (n^2)/2

따라서 O(n^2)입니다.