in-place : 배열 내부에서 정렬 진행하므로, 추가 공간이 필요 없음(반대의 경우는 별도 저장공간을 필요로 함)
안정 정렬(stable) : 동일한 값의 요소가 정렬 이후에도 자리를 유지함
버블정렬(Bubble Sort)
시간복잡도 : O(n^2)
중복된 값이 있을 경우, 정렬 과정을 거쳐도 그 순서가 유지됨
사이클 ([0] ~ [4] 까지 있는 배열인 경우)
인접한 두 요소를 비교, 사이클을 한 번 돌 때마다 배열 우측 끝에 가장 큰 요소가 배치됨
첫 번째 : [0]과 [1] 비교하여 정렬 > [1]과 [2] 비교하여 정렬 > [2]와 [1] 비교하여 정렬 > [3]과 [4] 비교하여 정렬
두 번째 : [0]과 [1] 비교하여 정렬 > [1]과 [2] 비교하여 정렬 > [2]와 [3] 비교하여 정렬
세 번째 : [0]과 [1] 비교하여 정렬 > [1]과 [2] 비교하여 정렬
네 번째 : [0]과 [1] 비교하여 정렬
선택정렬(Selection Sort)
시간복잡도 : O(n^2)
중복된 값이 있을 경우, 정렬 과정을 거치면 순서가 바뀔 수 있음
사이클
사이클을 한 번 돌 때마다 배열 좌측 끝에 가장 작은 요소가 배치됨
첫 번째 : 배열 내 요소들 중에서 최소값 추출 > 해당 요소를 배열의 [0] 요소와 교체
두 번째 : 추출한 값을 제외한 요소들 중에서 최소값 추출 > 해당 요소를 [1] 요소와 교체
n 번째 : ... > 반복
탐색 횟수를 줄이기 위한 방법
최솟값을 찾을 때 최댓값을 같이 찾기
탐색 시 동일한 값이 있다면 함께 정렬하기(다음 탐색 시 중복된 값이 최솟값이 될 것이므로)
삽입정렬(Insertion Sort)
시간복잡도 : O(n^2) / best O(n) (배열이 정렬되어 있는 경우)
삽입하기 때문에 배열이 길수록 효율 낮아지나, (삽입하면 데이터가 하나씩 밀려야 하므로)
배열이 정렬되어 있는 경우에는 한 번씩만 비교하므로 효율이 높아짐
사이클
두 번째 요소부터 시작
앞의 요소의 크기와 자신의 크기를 비교하며 자신의 위치를 찾아서 삽입하는 정렬
기타
in-place sort (데이터 swap 시 임시 변수 필요하나, 무시할만큼 적은 양이므로 in-place sort취급)
병합정렬(Merge Sort)
시간복잡도 : O(nlogn)
정렬하고 병합하는 과정에서 결과를 임시로 저장하는 배열이 필요하므로, 타 알고리즘 대비 O(n) 수준의 메모리가 추가로 필요함
퀵정렬보다 빠르지는 않으나 균등 이분할하기 때문에 항상 O(nlogn)의 시간복잡도를 유지할 수 있음
분할 > 정복 > 결합 단계로 구성됨 (최소단위까지 분할한 뒤, 다시 합치면서 정렬)
분할 : 배열을 같은 크기로 이분할
정복 : 부분 배열을 정렬 (부분 배열의 크기가 1보다 크다면 아니라면 순환호출을 이용해 다시 분할)
결합 : 정복을 통해 정렬된 부분 배열들을 하나의 배열에 결합
사이클
전체 배열을 이분할 > 분할한 배열을 다시 이분할 > ... 최소단위 (배열 크기 1) 까지 이분할 > 최소단위 2개씩 정렬, 병합 > 병합된 배열들 2개를 정렬, 병합 > ...
병합정렬의 시간복잡도가 O(nlogn)인 이유
N개 요소의 배열을 1개 단위로 나타내면 이진트리형태가 되며, 이진트리의 높이는 log n
분할되어 있는 배열을 결합하는 과정에서, 두 분할배열을 순차적으로 비교하여 결합하게 되는데, 각 분할배열은 이미 정렬이 되어 있으므로 두 배열의 index순서에 따라 차례대로 비교하고 정렬하면서 결합하게 됨 -> 즉, 두 분할배열의 요소들만큼 비교하게 되므로 비교 횟수는 O(n) 번
O(n)의 비교작업 + 트리 높이인 O(logn) = O(nlogn)
기타
안정 정렬
퀵정렬(Quick Sort)
시간복잡도 : O(n^2)
평균 시간복잡도는 O(nlogn)으로, 평균적으로 비교적 빠른 속도를 낼 수 있음
그러나 비균등 이분할이기 때문에 정렬된 데이터에 퀵정렬 사용 시 O(n^2)까지 증가하므로, 이런 경우 삽입 정렬이 더 빠를 수 있음
병합정렬은 O(nlogn)의 시간복잡도가 보장되므로, 추가 공간에 부담이 없다면 병합정렬이 적절할 수 있음
사이클
분할 > 정복 단계로 구성됨 (기준점인 피벗(pivot)을 활용)
배열 내 임의의 기준값인 피벗을 설정
피벗을 기준으로 왼쪽은 피벗보다 작은 요소, 오른쪽은 피벗보다 큰 요소로 배치, 피벗 기준 이분할
피벗 기준 왼쪽, 오른쪽 배열에 각각의 피벗을 설정, 반복
피벗
배열 내에서 어떤 값을 피벗으로 설정하는지에 따라 속도가 달라짐
피벗을 정하는 방법으로는 첫 번째 요소를 추출, 마지막 요소를 추출, 배열의 index를 랜덤으로 추출, 배열의 중간 index의 값을 추출, 배열 내 index 중 3개의 무작위수 추출 후 중위값에 해당하는 index의 값을 추출하는 등의 방법이 있음
피벗 기준 정렬이 끝난 경우, 해당 피벗의 위치가 확정됨
기타
불안정 정렬
in-place (코드 구현 방식에 따라서 O(n)의 추가 공간을 사용하게 될 수도 있으나, 이는 퀵 정렬의 장점을 해하므로 지양)
퀵셀렉션정렬(Quick Selection Sort)
퀵 정렬에서 피벗 기준 좌우 정렬이 끝난 경우, 배열 전체는 정렬되지 않았으나피봇이 왼쪽에 정렬된 값들 보다는 크고 우측에 정렬된 값들 보다는 작으며피벗의 위치가 확정된다는 점을 활용한 정렬
위의 상황(피벗 기준으로 좌우 정렬 연산이 끝난 경우)에서 피봇의 index가 k보다 작은 경우 우측 배열을 선택하고, k보다 큰 경우 좌측 배열을 선택 > 반복
힙정렬(Heap Sort)
시간복잡도 : O(nlogn)
추가적인 메모리가 필요 없으며 항상 O(nlogn)이 보장됨
사이클
배열을 힙 구조로 배열 > 최상위 루트 노드와 말단 노드를 교환 > 다시 힙 구조로 재배열
