정렬 알고리즘

거품정렬 (Bubble Sort)

서로 인접한 두 원소의 대소를 비교하고 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘

 

시간복잡도

평균	최선	최악
O(n²)	O(n²)	O(n²)

공간복잡도

swap을 통해 정렬이 수행되므로 O(n)

 

장점 : 구현이 간단하고 소스코드가 직관적이다. 다른 메모리 공간을 필요로 하지 않는다. (제자리 정렬) 안정 정렬이다.

단점 : 시간복잡도가 O(n²)으로 비효율적이다.

 

선택정렬 (Selection Sort)

선택 정렬의 평균 케이스

선택 정렬의 Worst 케이스

현재 순서에 해당하는 위치에 넣을 원소를 선택하는 알고리즘

배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는다고 생각하면 된다.

최악의 경우는 오름차순 정렬 시, 내림차순으로 정렬되어있는 경우이다.

 

시간복잡도

평균	최선	최악
O(n²)	O(n²)	O(n²)

공간복잡도

swap을 통해 정렬이 수행되므로 O(n)

 

장점 : 구현이 간단하고 소스코드가 직관적이다. 다른 메모리 공간을 필요로 하지 않는다. (제자리 정렬)

단점 : 시간복잡도가 O(n²)으로 비효율적이다. 불안정 정렬이다.

 

퀵 정렬 (Quick Sort)

배열 가운데에서 pivot을 골라 pivot을 기준으로 요소를 재귀적으로 정렬해나가는 알고리즘.

배열 가운데에서 하나의 원소(pivot)를 고른다. 피벗의 앞에는 피벗보다 작은 모든 원소들이 오도록 하고, 피벗 뒤에는 값이 큰 모든 원소들이 오도록 배열을 둘로 나눈다. 이후에 피벗은 움직이지 않는다. 분할된 두 배열에 대해 재귀적으로 이 과정을 반복한다. 

*분할 정복Divde-Conquer 방식을 통해 구현.

* 분할 정복 : 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식

 

시간복잡도

평균	최선	최악
O(nlog₂n)	O(nlog₂n)	O(n²)

공간복잡도

swap을 통해 정렬이 수행되므로 O(n)

 

장점 : 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에 시간 복잡도가 O(nlog₂n)으로 가장 빠르다.

단점 : 불안정 정렬이다. 정렬되어 있는 배열의 경우 퀵 소트의 불균형 분할에 의해 오히려 수행시간이 오래 걸린다. (최악의 경우)

 

병합 정렬 (Merge Sort)

요소를 쪼갠 후 다시 합병시키면서 정렬해나가는 알고리즘. 합병 혹은 병합 정렬이라고도 불린다.

퀵 소트와 마찬가지로 분할 정복Divde-Conquer 방식을 통해 구현.

 

시간복잡도

평균	최선	최악
O(nlogn)	O(nlogn)	O(nlogn)

공간복잡도

O(n)

 

퀵 정렬과의 차이점 

퀵 정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)

병합 정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)

 

장점 : 퀵 소트와 달리 Pivot을 설정하는 과정 없이 무조건 절반으로 분할하기 때문에 Pivot에 따라 성능이 안 좋아지는 경우가 존재하지 않는다. 따라서 평균, 최선, 최악의 시간복잡도가 모두 O(nlogn)이라는 빠른 속도를 가진다. 안정 정렬에 속한다.

단점 : 임시 배열을 사용하여 정렬할 요소들을 넣고 정렬을 반복하기 때문에 추가적인 메모리가 필요하다는 단점이 있다.

 

 

참고 자료

thumbs.gfycat.com/RectangularHarmlessGalapagosmockingbird-size_restricted.gif

codepumpkin.com/category/algorithms/

gyoogle.dev/blog/