1.정렬 알고리즘이란
:어떤 n개의 요소를 오름차순 혹은 내림차순으로 크기에 맞게 위치시키는 알고리즘이다.
2.정렬 알고리즘의 속성
- Stable vs Unstable
:Stable 정렬 알고리즘은 크기가 같은 요소가 정렬 이후에도 같은 순서로 배치될 수 있는 알고리즘이다. 대표적으로 merge-sort가 있다. - In-place
:In-place 정렬 알고리즘은 요소를 초기에 저장한 메모리 공간만으로 정렬을 수행할 수 있는 알고리즘이다. 대표적으로 quick-sort가 있다. - 비교 기반 정렬 알고리즘
:정렬 알고리즘의 시간복잡도를 비교연산이 대표하는 알고리즘을 말한다. 즉 O(nlogn)이라는 시간복잡도가 비교연산에 의해 계산되었을 경우 이런 정렬 알고리즘을 비교 기반 정렬 알고리즘이라고 한다.
3. 정렬알고리즘 설명
1)버블 정렬
:버블 정렬이란 인접한 두 값의 크기를 비교하여 왼쪽이 더 클 경우 위치를 스왑하는 알고리즘이다. 배열 처음부터 끝까지 지나갈경우 가장 마지막 값에 올바른 요소가 위치하는 것이 보장된다.
- 안정적 정렬 알고리즘이다.
- in-place정렬 알고리즘이다.
시간 복잡도는 O(n^2)이다.
2)선택 정렬
:배열을 끝까지 탐색하여 최소값을 찾아 맨 앞에 성분과 교환하는 행위를 반복하는 정렬.
- 불안정 정렬 알고리즘이다.
- in-place정렬 알고리즘이다.
- 데이터 입력상태에 민감하지 않다.
시간 복잡도는 O(n^2)이다.
3)삽입 정렬
:정렬 부분을 늘려가면서 새로 추가되는 요소를 올바른 삽입 위치에 추가하는 알고리즘이이다.
- 안정 정렬 알고리즘이다.
- in-place정렬 알고리즘이다.
- 데이터 입력상태에 따라 시간복잡도가 많이 달라질 수 있다.
시간 복잡도는 O(n^2)이다.
선택 정렬 vs 삽입 정렬
- 데이터가 이미 어느정도 정렬 되어 있는 것이 기대되는 경우 삽입 정렬을 사용하는것이 좋다.(반면, 데이터 분포에 상관없이 균일한 시간복잡도를 원하는 경우 선택 정렬을 사용하는 것이 낫다.)
- stable을 원하는 경우 삽입정렬을 사용하는 것이 낫다.
4)합병 정렬
:divide하면서 배열을 여러개로 나누고 conquer하면서 정렬한다.
- 요소를 담은 배열과 크기가같은 배열이 하나더 필요하다.
- stable하다.
recursion으로 구현할 경우 함수 내에 divide하는 기능과 conquer하는 기능이
시간 복잡도는 항상 O(nlogn)이다.
5)퀵 정렬
:특정 pivot을 선택하여 pivot왼쪽에는 그보다 작은 값들, 오른쪽에는 그보다 큰 값들로만 위치하도록 하여 재귀적으로 반복하는 정렬 방법이다.
- 최악의 경우 O(n^2)이 될 수 있지만 일반적으로 O(nlogn)이며 이 경우 합병 정렬보다 빠르다.
- in-place
- unstable
cf)퀵 정렬이 최악의 경우가 되는 경우는 pivot을 잘못 선택하는 경우인데 이를 막기위해 3개의 수를 임의 로 선택한 후 그중 median값을 pivot으로 선택한다.
cf)퀵 정렬이 빠른 이유는 memory locality관점에서도 설명할 수 있는데, 합병 정렬에 비해 동시간 내에 같은 요소에 자주 접근하기 때문에 이러한 데이터를 cache메모리에 올려놓고 자주 사용할 확률이 올라가서 처리속도를 향상 시킬 수 있다.
출처: https://www.geeksforgeeks.org/quicksort-better-mergesort/
