Developer Ahn

- quick sort
 

- 분할 정복(divide and conquer) 방법, 보통 재귀를 이용하여 구현

- 합병 정렬과 달리 비균등하게 분할

- 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택하고 피벗을 기준으로 분할

- 속도가 빠르고 추가 메모리 공간을 필요로 하지 않음, 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 등에 기인

- 시간 복잡도 분석
 : 재귀 호출의 깊이는 
 : 각각의 패스에서 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어짐, 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시
 : 총 시간 복잡도는 

- 단점으로
 : 정렬된 리스트에 대해서는 오히려 수행시간이  되버리는 불균형 분할 발생 -> 단순히 왼쪽 데이터를 피벗으로 사용하지 않고 리스트 내의 몇개의 데이터 중에서 크기순으로 중간 값(median)을 피벗으로 선택하여 극복 (왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기순으로 중간값을 선택하는 방법(median of three)

- CODE

#include < iostream>
using namespace std;

int arr[1000001];

int partition(int *a, int low, int high) {
	int pivotIndex = low + (high - low) / 2;
	int pivotValue = arr[pivotIndex];
	swap(arr[pivotIndex], arr[high]);
	int pos = low;
	for (int i = low; i < high; i++) {
		if (a[i] < pivotValue) {
			swap(a[i], a[pos]);
			pos++;
		}
	}
	swap(arr[pos], arr[high]);
	
	return pos;
}

void quicksort(int *a, int low, int high){
	if (low < high) {
		int pivot = partition(a, low, high);
		quicksort(a, low, pivot - 1);
		quicksort(a, pivot + 1, high);
	}
}

int main()
{
	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	quicksort(arr, 0, n - 1);

	for (int i = 0; i < n; i++) {
		cout << arr[i] << "\n";
	}

	return 0;
}

- merge sort

- 분할 정복(divide and conquer) 방법, 보통 재귀를 이용하여 구현

- 분할(divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  정복(conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법 적용
  결합(combine): 정렬된 부분 배열들을 하나의 배열에 합병

- 시간복잡도 분석
 : 배열이 부분 배열로 나누어지는 단계에서는 비교 연산이나 이동 연산이 수행되지 않는다. 재귀 호출의 깊이는 
 : 합병단계에서 비교 연산 최대 n번, 임시 배열에 복사했다가 다시 가져와야하는 이동 연산 n 번으로 총 2n번 레코드의 이동 발생
 : 총 시간 복잡도는 

- 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일 (데이터의 분포에 영향을 덜 받는 안정적인 정렬 방법)

- 단점으로
  : 임시 배열이 필요함
  : 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래 -> 연결리스트로 극복

- CODE

#include <iostream>
using namespace std;

int arr[1000001];
int save[1000001];

void merge_sort(int* a, int start, int end) {
	if (start == end) {
		return;
	}
	else if (start + 1 == end) {
		if (a[start] > a[end]) {
			swap(a[start], a[end]);
		}
		return;
	}

	// divide
	int mid = (start + end) / 2;
	merge_sort(a, start, mid);
	merge_sort(a, mid + 1, end);
	int left = start;
	int right = mid + 1;
	int k = 0;

	// conquer
	while (left <= mid && right <= end) {
		if (a[left] <= a[right]) {
			save[k++] = a[left++];
		}
		else {
			save[k++] = a[right++];
		}
	}
	while (left <= mid) {
		save[k++] = a[left++];
	}
	while (right <= end) {
		save[k++] = a[right++];
	}

	// combine
	for (int i = start; i <= end; i++) {
		a[i] = save[i - start];
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	merge_sort(arr, 0, n - 1);

	for (int i = 0; i < n; i++)
		cout << arr[i] << "\n";

	return 0;
}

- shell sort

- 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것을 착안한 방법

- 셸 정렬은 삽입 정렬의 보다 빠르다.

- 전체의 리스트를 한 번에 정렬하지 않고, 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬

- gap만큼 떨어진 요소들을 삽입 정렬하고, gap을 반씩 줄여가면서 1까지 반복

- 최악의 경우의 시간복잡도 지만 평균적인 경우는 로 삽입 정렬보다 빠르다

출처: http://wonjayk.tistory.com/220