그 다음 큰 것을 찾아서 뒤로 보낸다 ... 이렇게 이어질 테니 계산해보면 시간복잡도는 O(N^2) 이다.
선택정렬 코드
int arr[10] = {3, 2, 7, 116, 62, 235, 1, 23, 55, 77};
int n = 10;
for(int i = n-1; i > 0; i--){ // 최대값을 찾으면 i위치로 보낼것이다. i:맨 마지막부터 앞에서 두번째 까지.
int mxidx = 0;
for(int j = 1; j <= i; j++){
if(arr[mxidx] < arr[j]) mxidx = j;
}
swap(arr[mxidx], arr[i]);
}
선택 정렬은 가장 큰 수를 찾으면, 인덱스 i로 이동시킨다. 내부 반복문에서 mxidx 인덱스와 j인덱스 자리의 숫자를 비교한다. 이 반복문이 종료되면 가장 큰 숫자의 인덱스가 mxidx에 저장된다. 가장 큰 숫자 인덱스 mxidx와 뒤쪽 인덱스 i를 swap한다. ( == 가장 큰 숫자를 뒤로 보낸다)
max_element 함수로 줄여본 코드
max_element(arr, arr+k)
// arr[0], arr[1], arr[2], .. , arr[k-1] 에서 최댓값인 원소의 주소를 반환
arr[0]부터 arr[k-1] 까지 탐색한 후 최댓값인 원소 주소를 반환한다.
arr[k]가 아니라 arr[k-1]임을 주의하자.
int arr[10] = {3, 2, 7, 116, 62, 235, 1, 23, 55, 77};
int n = 10;
for(int i = n-1; i > 0; i--){ // 맨 마지막부터 앞에서 두번째 까지.
swap(*max_element(arr, arr+i+1), arr[i]);
}
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
int tmp[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수
// mid = (st+en)/2라고 할 때 arr[st:mid], arr[mid:en]은 이미 정렬이 되어있는 상태일 때 arr[st:mid]와 arr[mid:en]을 합친다.
void merge(int st, int en){
int mid = (st+en)/2;
int lidx = st; // arr[st:mid]에서 값을 보기 위해 사용하는 index
int ridx = mid; // arr[mid:en]에서 값을 보기 위해 사용하는 index
for(int i = st; i < en; i++){
if(ridx == en) tmp[i] = arr[lidx++];
else if(lidx == mid) tmp[i] = arr[ridx++];
else if(arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++];
else tmp[i] = arr[ridx++];
}
for(int i = st; i < en; i++) arr[i] = tmp[i]; // tmp에 임시저장해둔 값을 a로 다시 옮김
}
// a[st:en]을 정렬하고 싶다.
void merge_sort(int st, int en){
if(en == st+1) return; // 리스트의 길이가 1인 경우
int mid = (st+en)/2;
merge_sort(st, mid); // arr[st:mid]을 정렬한다.
merge_sort(mid, en); // arr[mid:en]을 정렬한다.
merge(st, en); // arr[st:mid]와 arr[mid:en]을 합친다.
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
merge_sort(0, n);
for(int i = 0; i < n; i++) cout << arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357
}
merge함수에서 두 리스트를 합친 결과를 임시롤 저장할 곳이 필요해서 tmp 변수가 필요하다.
merge_sort함수에서 배열의 크기가 1일 때는 아무것도 안해도 정렬이 완료된다.
이후에는 재귀적으로 절반을 나눠 각각 정렬이 되게 한다.
아직 헷갈리더라도 이건 어려운 내용인것이 맞고 시간과 반복시도가 해결해주는 문제니까 계속 가면 된다.
만약 l 과 r이 타겟을 못찾으면 l > r 이 된다. 인덱스 l과 r이 역전되버린다. 이 때는 break 로 탐색을 멈춘다.
l 과 r이 타겟을 찾으면, swap(arr[l], arr[r]) 스왑 한다!
스왑이 종료되면, 인덱스 r과 인덱스 pivot을 스왑한다.
그리고 pivot을 기준으로 왼쪽과 오른쪽을 보면 pivot이 올바른 자리에 있음을 확인할 수 있다.
나머지 부분은 재귀호출해서 정렬시킨다.
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
void quick_sort(int st, int en) { // arr[st to en-1]을 정렬할 예정
if(en <= st+1) return; // 수열의 길이가 1 이하이면 함수 종료.(base condition)
int pivot = arr[st]; // 제일 앞의 것을 pivot으로 잡는다. 임의의 값을 잡고 arr[st]와 swap해도 상관없음.
int l = st+1; // 포인터 l
int r = en-1; // 포인터 r
while(1){
while(l <= r && arr[l] <= pivot) l++;
while(l <= r && arr[r] >= pivot) r--;
if(l > r) break; // l과 r이 역전되는 그 즉시 탈출
swap(arr[l], arr[r]);
}
swap(arr[st], arr[r]);
quick_sort(st, r);
quick_sort(r+1, en);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
quick_sort(0, n);
for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}
3. 퀵 소트의 시간복잡도
pivot 하나를 올바른 자리에 보낼 때 마다 상수번의 연산으로 l과 r이 한 칸씩 가까워진다.
따라서한 세트의 시간복잡도는 O(N)이다.
재귀 종료 조건인 base condition은 구간의 길이가 1 이하일 때다. pivot을 제자리로 보낸 뒤에, 재귀적으로 자기 자신을 호출한다.
pivot 하나를 올바른 자리에 보내는 세트가 O(N)이 걸리는데.
pivot 을 하나씩 제외하면 N, N-1, N-2 ... 번의 연산이 필요하다.
4. 퀵 소트의 단점?
만약 pivot이 매번 완벽하게 중앙에 위치한다면?
리스트를 균등하게 반으로 쪼개서재귀를 호출하게 된다.
이 때는 n, n/2, n/4 ... 번의 연산이 필요할 것이다. 그러면 머지 소트때와 같이 세트마다 O(logN)이 걸린다.
한 세트의 연산횟수 N과 재귀 호출 연산횟수 logN을 곱하면 된다.
물론 항상 pivot이 완벽하게 중앙에 오지 않겠지만대략 시간복잡도는 O(NlogN)이 된다.
그리고 앞서 말한 cache hit rate가 높아서 퀵 소트는 속도가 굉장히 빠르다.
{1,2,3,4,5,6,7,8} 을 퀵 소트로 정렬하면 시간 복잡도가 얼마일까?
pivot은 항상 중앙에 있는게 아니라. 제일 왼쪽에 위치하게 된다.
그래서 한 단계마다 longN개가 아니라 N개를 확인해야 한다. -> 시간복잡도는 O(N^2)이 된다.
퀵 소트는 평균적으로 O(NlogN)이지만 최악의 경우 O(N^2)이다.
단순히 제일 왼쪽 값을 pivot으로 선택해보면 지금처럼 리스트가 오름차순 이거나 내림차순일 때 O(N^2)이 된다.
[참고]
STL을 못 쓰는 경우, 정렬을 직접 구현해야 한다면 퀵 소트를 쓰는게 아니라 머지 소트를 구현하라고 한 이유가 여기에 있다.
최악의 경우 O(N^2)의 시간복잡도인 퀵 소트를 쓸 필요가 없다.
하지만 대부분의 정렬 라이브러리는 퀵 소트를 쓰는 것도 사실이다.
pivot을 '잘'고르는 것이 관건인데. 랜덤으로 선택하거나. 후보 3개를 정해서 중앙값을 선택하기도 한다.
최악의 경우에도 O(NlogN)을 보장하기 위해 일정 깊이 이상의 재귀가 호출되면 힙 소트로 정렬한다.
재귀가 과도하게 호출되면 오버헤드 때문에 성능저하가 오는 데 이를 피하기 위함이다. 이러한 정렬을 Introspective sort라고 한다.
5. 머지 소트 VS 퀵 소트
머지소트와 퀵 소트는 둘 다 재귀적 구조로 구현된다.
먼저 시간복잡도를 보면 머지소트는 무조건 O(NlogN)이고. 퀵 소트는 최악에 O(N^2), 평균적으로 O(NlogN)이다.
평균적으로 (이름값하는) 퀵 소트가 빠르다.
퀵 소트는 In-Place Sort 인 점을 기억하자.
그리고 머지 소트는 우선 순위가 같은 원소들끼리의 원래 순서가 유지되는 Stable Sort이지만 퀵 소트는 아니다.
