Sorting (정렬)

Bubble sort (거품정렬)

- performance : O(n^2)        - performance 안좋지..

- space complexity : O(1)      - swapping을 위한 공간 1개 필요   

- 인접한 두개의 자료를 비교해서 차순에 맞게 정렬하는 작업을 (자료개수-1) 번 만큼 반복한다.

- 뒤부터 채워준다.

[4, 3, 1, 2]
[3, 4, 1, 2]
[3, 1, 4, 2]
-------------

[3, 1, 2, 4]
[1, 3, 2, 4]
[1, 2, 3, 4]
-------------

[1, 2, 3, 4]
[1, 2, 3, 4]
[1, 2, 3, 4]

---

Selection Sort (선택정렬)

- Worst case performance : O(n^2)

- Best case performance : O(n^2)

- Average case performance : O(n^2)

- Worst case space complexity : O(n) total, O(1) auxiliary

- Minimum value라는 1개의 공간을 사용한다!! 

- 처음부터 하나하나 Minimum value의 공간에 집어 넣고 뒤의 값들과 비교 하면서 Minimum value를 변경해 주고, 앞의 값과 Minimum value값을 교환해 주는 식으로 마지막까지 해준다. 

- 앞부터 채워준다.

[6, 5, 2, 4, 3, 1, 0]
[0, 5, 2, 4, 3, 1, 6]
[0, 1, 2, 4, 3, 5, 6]
[0, 1, 2, 4, 3, 5, 6]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6]

---

Insertion Sort (삽입정렬)

- 아주 간단하게 구현 할 수 있지만, 효율적이지 않음

[5, 4, 3, 0, 1, 2]
[4, 5, 3, 0, 1, 2]
[3, 4, 5, 0, 1, 2]
[0, 3, 4, 5, 1, 2]
[0, 1, 3, 4, 5, 2]
[0, 1, 2, 3, 4, 5]

---

Merge Sort (병합정렬)

- performance (n log n)

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted) 

2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublists remaining. This will be the sorted list.

[1,5,4,8,8,3,2,4] 이 있다면.

1. sublists의 구성이 1개가 될 때 까지 list를 쪼갠다.  

[1],[5],[4],[8],[8],[3],[2],[4]

2. 각 element를 sort와 merge하는데, 하나의 list가 될 때까지 반복해 준다.

[1,5],[4,8],[3,8],[2,4]

[1,4,5,8],[2,3,4,8]

[1,2,3,4,4,5,8,8]

끝

split :  [8, 7, 6, 5, 4, 3, 2, 1]
split :  [8, 7, 6, 5]
split :  [8, 7]
split :  [8]
split :  [7]
merge :  [7, 8]
split :  [6, 5]
split :  [6]
split :  [5]
merge :  [5, 6]
merge :  [5, 6, 7, 8]
split :  [4, 3, 2, 1]
split :  [4, 3]
split :  [4]
split :  [3]
merge :  [3, 4]
split :  [2, 1]
split :  [2]
split :  [1]
merge :  [1, 2]
merge :  [1, 2, 3, 4]
merge :  [1, 2, 3, 4, 5, 6, 7, 8]

---

Quick Sort (퀵정렬)

- performance : O(n log n), worst case O(n^2)(이미 정렬되어 있는 경우)

- space complexity : O(n)

1. Finde Pivot, move items smaller than pivot to the left side of pivot, move items greater than pivot to the right side of pivot.

2. Repeatedly do step 1 from both left side items and right side items.

list :  [1, 5, 8, 6, 2, 4, 2, 7, 8, 3]
pivot :  3
left :  [1, 2, 2]
list :  [1, 2, 2, 3, 5, 4, 8, 7, 8, 6]
pivot :  2
left :  [1]
list :  [1, 2, 2, 3, 5, 4, 8, 7, 8, 6]
right :  [2]
list :  [1, 2, 2, 3, 5, 4, 8, 7, 8, 6]
right :  [5, 4, 8, 7, 8, 6]
list :  [1, 2, 2, 3, 5, 4, 8, 7, 8, 6]
pivot :  6
left :  [5, 4]
list :  [1, 2, 2, 3, 5, 4, 6, 7, 8, 8]
pivot :  4
left :  []
list :  [1, 2, 2, 3, 4, 5, 6, 7, 8, 8]
right :  [5]
list :  [1, 2, 2, 3, 4, 5, 6, 7, 8, 8]
right :  [7, 8, 8]
list :  [1, 2, 2, 3, 4, 5, 6, 7, 8, 8]
pivot :  8
left :  [7]
list :  [1, 2, 2, 3, 4, 5, 6, 7, 8, 8]
right :  [8]
list :  [1, 2, 2, 3, 4, 5, 6, 7, 8, 8]

- pivot을 중앙값으로 잡고 하는 경우

list :  [54, 26, 93, 17, 77, 31, 44, 55, 20]
pivot :  77
left :  [54, 26, 17, 31, 44, 55, 20]
equal :  [77]
right :  [93]
list :  [54, 26, 17, 31, 44, 55, 20]
pivot :  31
left :  [26, 17, 20]
equal :  [31]
right :  [54, 44, 55]
list :  [26, 17, 20]
pivot :  17
left :  []
equal :  [17]
right :  [26, 20]
list :  [26, 20]
pivot :  20
left :  []
equal :  [20]
right :  [26]
list :  [54, 44, 55]
pivot :  44
left :  []
equal :  [44]
right :  [54, 55]
list :  [54, 55]
pivot :  55
left :  [54]
equal :  [55]
right :  []

Out:[17, 20, 26, 31, 44, 54, 55, 77, 93]

Source Code : The-G

reference

- 상상개발자

- merge-sort