정렬 ***TODO

 stable sort는 정렬을 했을 때 중복된 값들의 순서가 변하지 않는 sort. 변한다면 unstable이다. 아래 정렬들은 stable.

• Bubble Sort, Insertion Sort
• Counting Sort
• Merget Sort

 

 in-place sort는 추가적인 메모리가 거의 들지 않는 sort. 아래 정렬들은 in-place.

• Bubble Sort, Selection Sort, Insertion Sort
• Quick Sort, Heap Sort

 

Implenentation of Sort

Bubble Sort : $O(n^{2})$ - Stable and In-Place Sort

 array의 값 2개를 비교해서 비교함수를 만족하지 않는다면 swap하는 방식

for(int i = 0; i<N; i++){
	for(int j = i+1; j<N; j++){
		if(arr[i] > arr[j]) swap(arr[i], arr[j]);
	}
}

 

Selection Sort : $O(n^{2})$ - In-Place Sort

 i보다 뒤에 있는 것들 중 비교함수를 만족하는 최대/최소값을 찾아 i와 swap하는 방식

for(int i = 0; i<N; i++){
	int minidx = i;
	for(int j = i+1; j<N; j++){
		if(arr[j] < arr[minidx]){
			minidx = j;
		}
	}
	swap(arr[i], arr[minidx]);
}

 

Insertion Sort : $O(n^{2})$ - Stable and In-Place Sort

 maxval보다 더 크다면 그 maxval값은 더 앞으로 올 수 있음. 앞으로 올 수 있을 때 까지 당기고, 마지막으로 arr[j+1]에 maxval을 넣음.

for(int i = 1; i<N; i++){
	int maxval = arr[i];
	int j;
	for(j = i-1; j>=0 && arr[j] > maxval; j--){
		arr[j+1] = arr[j];
	}
	arr[j+1] = maxval;
}

 

Counting Sort : O(n+k) - Stable Sort

 n은 input 개수, k는 input 중 max값

int N, input, INF; // INF : input의 max value
cin>>N>>INF;
vector<int> arr(INF+1);
for(int i = 0; i<N; i++){
	cin>>input;
	arr[input]++;
}

for(int i = 1; i<=10000; i++){
	while(arr[i]--){
		cout<<i<<'\n';
	}
}

 

Radix Sort : O(nd)

 n은 input 개수, d는 input의 자리수 중 max값

 

Merge Sort : O(nlogn) - Stable Sort

 주어진 배열을 가운데 기준 [시작~가운데], [가운데+1~끝] 반반으로 나눠 반을 정렬하는 기법. div&conq의 기법 중 하나이다.

void merge(vector<int>& arr, int begin, int end){
	int mid = (begin + end) / 2;
	int leftarrlen = mid - begin + 1;
	int rightarrlen = end - mid;

	vector<int> leftarr(leftarrlen), rightarr(rightarrlen);

	for(int i = begin; i <= mid; i++){
		leftarr[i - begin] = arr[i];
	}
	for(int i = mid+1; i <= end; i++){
		rightarr[i - mid -1] = arr[i];
	}

	int leftidx = 0, rightidx = 0, arridx = begin;
	while(leftidx < leftarrlen && rightidx < rightarrlen){
		if(leftarr[leftidx] <= rightarr[rightidx]){
			arr[arridx++] = leftarr[leftidx++];
		} else{
			arr[arridx++] = rightarr[rightidx++];
		}
	}
	
	while(leftidx < leftarrlen){
		arr[arridx++] = leftarr[leftidx++];
	}
	while(rightidx < rightarrlen){
		arr[arridx++] = rightarr[rightidx++];
	}
	return;
}

void merge_sort(vector<int>& arr, int begin, int end){
	if(begin >= end) return;
	int mid = (begin + end) / 2;
	merge_sort(arr, begin, mid);
	merge_sort(arr, mid+1, end);
	merge(arr, begin, end);
}

int main(){
	// ... arr 설정
    merge_sort(arr, 0, arr.size()-1);
	return 0;
}

 

Quick Sort : O(nlogn) - In-Place Sort

 빠름

 

Heap Sort : O(nlogn) - Stable and In-Place Sort

 heap 이용

 

STL Sort

sort() Function implemented by Intro Sort : O(nlogn)

 intro sort는 quick sort가 기반이지만 일정 depth 이상으로 넘어갈 경우 데이터가 편향되어 있다고 간주하고 그때부터 heap sort를 진행함. 따라서 worst case O(nlogn).

 

stable_sort() Function

 stable_sort이다.