정렬 알고리즘(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값보다 작은 값을 차례 지정한다.

시작 : [ 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보다 작은 값은 존재하지 않기에 스왑하지 않음




댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째