[알고리즘] 정렬 알고리즘

정렬 알고리즘

• 합병 정렬 (Merge sort) : O(nlogn)
• 퀵 정렬 (Quick sort) : O(n^2)
• 립 정렬 (Heap sort) : O(nlogn)

합병 정렬 (Merge sort)

• 입력을 2개의 부분 문제로 분할하며 크기가 1/2 씩 감소하는 분할 정복 알고리즘(DC) 이다
• 정렬이 안되어있는 배열 S를 비내림차순으로 정렬하는 과정
  • S를 반으로 나누어 A와 B로 명명
  • 나눠진 배열을 각각 정렬 (이 때 A가 끝날 때 까지 B는 정렬하지 않음)
  • 배열이 1개씩 남을 때 까지 반복 (분할)
  • A와 B에 각각 비내림차순 정렬
  • A와 B의 앞 index의 수를 비교하며 병합 진행 (정복)
• 시간 복잡도
  • 최선의 경우 : A와 B가 이미 정렬이 이미 되어있던 경우 ⇒ A번 또는 B번
  • 최악의 경우 : 모든 원소의 비교가 필요한 경우 ⇒ A+B

1. 분할

void mergesort (int n, keytype S[]) {
	const int h = n/2, m = n-h;     // h = 중간 값
	keytype A[1..h], B[1..m];       // 중간 값을 기준으로 A와 B로 나눔
	if (n > 1) {
		copy S[1] through S[h] to A[1] through A[h];
		copy S[h+1] through S[n] to B[1] through B[m];

		mergesort(h,A);    // 배열 A 먼저 모두 분해
		mergesort(m,B);    // 배열 A 끝난 후 B 모두 분해
		merge(h,m,A,B,S);  // 병합 함수로 전달
	}
}

1. 병합

void merge(int h, int m, const keytype A[], const keytype B[], const keytype S[]) {
	index i = 1, j = 1, k = 1;

	while (i <= h && j <= m) { // h: A배열의 수 , m: B배열의 수
		if (A[i] < B[j]) {       // A의 배열의 원소가 더 작을 때
			S[k] = A[i];           // S에 추가
			i++;                   // A배열의 비교 할 인덱스 위치 +1
		} else {
			S[k] = B[j];           // B의 배열의 원소가 더 작을 때
			j++;                   // B배열의 비교 할 인덱스 위치 +1
		}
		k++;                     // S에 넣을 위치 k에 +1
	}

	if (i > h)
		copy B[j] through B[m] to S[k] through S[h+m];
	else
		copy A[i] through A[h] to S[k] through S[h+m];
}

•  분석
  • 단위연산: merge에서 발생하는 비교연산
  • 입력크기: 배열 S에 있는 항목의 개수 n
  • T(n): 최악의 경우 ⇒ O(n logn)

퀵 정렬 (Quick sort)

• Partition 알고리즘 이라고도 한다
• 서로의 위치를 교환해가며 정렬한다

Produre partition(p, j){
	integer p, j, i
	global A(p, j)   // p ~ j 위치까지 있는 배열 A (맨 앞 : p, 맨 뒤 : j)
	x = A(p)         // x: partition element
	i = p            // 맨 앞 위치인 p (pivot)부터 시작
	
	loop
		loop1 i = i+1 until A(i) >= x repeat  // i에 1을 더해가며 앞에서부터 기준 값 x보다 큰게 있으면 멈춤
		loop2 j = j-1 until A(j) <= x repeat  // j에서 1을 빼가며 뒤에서부터 기준 값 x보다 작은게 있으면 멈춤 
	
		if i<j then   // i가 j보다 작을 땐 A의 i위치와 j위치의 원소 교환
			call INTERCHANGE(A(i), A(j))
		else exit     // i가 j보다 커졌을 때 = 모든 원소를 비교했을 때
		
		repeat        // 비교가 끝나지 않았으면 loop1로 가서 다시 비교

	A(p) = A(j)     // A의 j위치 원소를 맨 앞(x의 위치)으로
	A(j) = x        // A의 j위치에 기준값 x를 넣어 j와 x 값 교환
}

• partition x를 기준으로 좌/우로 구분만 한 상태가 된다
• 이후 x를 기준으로 좌/우 배열로 나누어 quick sort 진행 (이 때에도 한쪽이 모두 끝날 때 까지 반대쪽은 진행하지 못한다)

• 분석
  • 시간 복잡도 : 최악의 경우 O(n^2) / 평균의 경우 O(nlogn
    •