정렬 알고리즘(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(n2)
나머지는 평균 최선의 경우는 O(n log(n))으로 Merge 정렬과 동일하다.
Quick Sort도 재귀를 사용한다.
퀵소트의 경우 pivot을 배열의 맨 마지막 값으로 pivot값보다 작은 값을 차례 지정한다.
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(n2)
나머지는 평균 최선의 경우는 O(n log(n))으로 Merge 정렬과 동일하다.
Quick Sort도 재귀를 사용한다.
시작 : [ 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보다 작은 값은 존재하지 않기에 스왑하지 않음
댓글
댓글 쓰기