정렬 알고리즘(Bubble, Insertion, Selection, Merge, Quick) Feat. Java

요즘, 프레임워크나 라이브러리에 대한 공부위주로 하다보니까 기본기가 많이 부족하다고 느껴서 정렬알고리즘을 공부하고 한 번 정리해보았다.


1. Bubble

시간복잡도 O(n²), 가장 기본적인 정렬 알고리즘.
시작 :   [ 5, 2, 4, 3, 1]
1회전 : [ 2, 4, 3, 1, 5]
2회전 : [ 2, 3, 1, 4, 5]
3회전 : [ 2, 1, 3, 4, 5]
4회전 : [ 1, 2, 3, 4, 5]




2. Selection

시간복잡도 O(n²), 가장 작은 값 차례대로 배열의 맨 마지막으로 보낸다.

시작 :    [ 5, 2, 4, 3, 1 ]
1회전 :  [ 5, 2, 4, 3, 1 ] => [ 1, 2, 4, 3, 5 ] => i 는 0, min_Val 은 4 ----> swap(0, 4)
2회전 :  [ 1, 2, 4, 3, 5 ] => [ 1, 2, 4, 3, 5 ] => i 는 1, min_Val 은 1 ----> swap(1, 1)
3회전 :  [ 1, 2, 4, 3, 5 ] => [ 1, 2, 3, 4, 5 ] => i 는 2, min_Val 은 3 ----> swap(2, 3)
4회전 :  [ 1, 2, 3, 4, 5 ] => [ 1, 2, 3, 4, 5 ] => i 는 3, min_Val 은 3 ----> swap(3, 3)





















3. Insertion

시간복잡도 최선의 경우에는 O(n) 인데 이미 정렬이 되어있는 경우이다.
나머지는 Bubble, Selection과 마찬가지로 O(n²)이다.

시작 :    [ 5, 2, 4, 3, 1 ]
1회전 :  [ 5, 2, 4, 3, 1 ] => [ 2, 5, 4, 3, 1 ] => i 는 1
2회전 :  [ 2, 5, 4, 3, 1 ] => [ 2, 4, 5, 3, 1 ] => i 는 2
3회전 :  [ 2, 4, 5, 3, 1 ] => [ 2, 3, 4, 5, 1 ] => i 는 3
4회전 :  [ 2, 3, 4, 5, 1 ] => [ 1, 2, 3, 4, 5 ] => i 는 4











4. Merge

시간복잡도 O(nlog(n))
재귀를 사용해야 되기 때문에 까다로운 부분이 있다.
배열의 중간을 기준으로 왼쪽과 오른쪽으로 파티션을 분할하는 과정을
파티션의 크기가 1이 될 때까지 반복한후 다시 합치면서 정렬한다.

시작 : [ 5, 2, 4, 3, 1 ]
left : [ 5, 2 ]                   right : [ 4, 3, 1 ]
left : [ 5 ] right : [ 2 ]         left : [ 4 ]  right :  [ 3, 1 ]
                                                             left : [ 3 ] right : [ 1 ]

Merge 시작
left : [ 2, 5 ]                                       right : [ 1, 3 ]
                                                          right : [ 1, 3, 4 ]

[ 1, 2, 3, 4, 5 ]



5. Quick

시간복잡도 최악의 경우에 O(n²) 
나머지는 평균 최선의 경우는 O(n log(n))으로 Merge 정렬과 동일하다.
Quick Sort도 재귀를 사용한다.

퀵소트의 경우 pivot을 배열의 맨 마지막 값으로 pivot값보다 작은 값을 차례 지정한다.

시작 : [ 5, 3, 1, 4, 2 ]  quickSort( arr, 0, arr.length - 1 )

[ 5, 3, 1, 4, 2 ] => [ 1, 2, 5, 4, 3 ] 

pivot : 2  

2보다 작은 1을 첫 번째 자리에 있는 5와 스왑

pivot이 두 번째로 작기 때문에 더 이상 스왑 하지 않는다.

스왑은 한 번 만 발생했기 때문에 두 번째 공간에 있는 3과 pivot을 스왑하고

partitionIndex 1을 반환.

[ 1, 2, 5, 4, 3 ] => [ 1, 2, 3, 4, 5 ] 

quickSort(arr, 0, 1 - 1(0)) => 종료

quickSort(arr, 2, 4 )

pivot : 3

begin : 2 이기 때문에 arr[2] 부터 검사, 3보다 작은 값은 5, 4 둘 다 아니기 때문에 스왑하지 않음

스왑이 발생하지 않았기에 5와 3을 스왑

partitionIndex 2를 반환.

[ 1, 2, 3, 4, 5 ] => [ 1, 2, 3, 4, 5 ]

 pivot : 5

 begin : 3 이기 때문에 arr[3] 부터 검사, 5보다 작은 값은 존재하지 않기에 스왑하지 않음