3. 퀵 정렬 (Quick Sort), 병합 정렬 (Merge Sort)

Quick Sort

특정한 값을 기준으로 큰 숫자와 작은 숫자를 나눈다.

- 기준값(pivot)

- 분할 정복

- 왼쪽은 앞에서부터 탐색하며 기준값보다 큰 값을 찾고, 오른쪽은 뒤에서 탐색하여 기준값보다 작은 값을 찾는다. 찾은 후에 그 두 값의 위치를 바꿔준다. 

   - 언제까지? 두 값이 엇갈릴때까지

   - 좌측 인덱스(기준값보다 큰 값)값보다 우측 인덱스(기준값보다 작은 값)이 커지면 위치 변경

 

#include <stdio.h>

int number = 10;
int arr[10] = {3,7,8,1,5,9,6,10,2,4};

void quickSort(int* arr, int start, int end){
	if(start >= end){// 원소가 1개인 경우 
		return;
	}
	
	int key = start;
	int i = start+1;
	int j = end;
	int temp;
	
	while(i<=j){
		while(arr[i]<=arr[key]){
			//키 값보다 큰 값을 만날때까지
			i++;
		}
		while(arr[j]>=arr[key] && j>start){
			j--;
		}
		
		if(i>j){
			temp= arr[j];
			arr[j]=arr[key];
			arr[key]=temp;
		}else{
			temp= arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
		}
	}	
	quickSort(arr, start, j-1);
	quickSort(arr, j+1, end);
	
}


int main(void){
	quickSort(arr, 0, number-1);
	
	for(int i =0; i<number; i++){
		printf("%d ", arr[i]);
	}
}

 

시간복잡도:

- 평균 속도: O(N*logN)

- 최악: O(n^2)

최악이 발생하는 경우: 정렬이 거의 다 된 경우 분할 정복의 이점을 사용하지 못해서 그냥 탐색만 하고 바뀌는 건 없음

- 평균적으로 좋은 효율을 내서 C언어 라이브러리 중 정렬을 제공하는 기능도 대체로 quick sort 를 사용한다.

 

Merge Sort

큰 문제를 두 개의 문제로 잘라서 문자를 해결한 후에 합치는 것.

- 피벗 값이 없음. 항상 반으로 나누기 때문에

- 항상 반으로 자르기 때문에 logN 이 나오는 것

- 합치는 순간에 정렬

 

시간복잡도 O(NlgN) 보장함

- 메모리를 좀 낭비한다는 단점

 #include <stdio.h>
 
 int num = 8;
 int sorted[8]; // 정렬 배열은 반드시 전역변수로 - 임시로 저장하는  
 
 void merge(int a[], int m, int middle, int n){
 	int i = m;
 	int j = middle+1;
 	int k = m;
 	
 	// 작은 순서대로 배열
	while(i<=middle && j<=n){
		if (a[i] <= a[j]){
			sorted[k] = a[i];
			i++;
		}else{
			sorted[k]=a[j];
			j++;
		}
		k++;
		
	}	
	// left data also needed to be inserted
	if(i>middle){
		for (int t = j; t<=n; t++){
			sorted[k] = a[t];
			k++;
		}
	}else{
		for(int t = i; t<=middle; t++){
			sorted[k] = a[t];
			k++;
		}
	}
 	// sorted array inserted into real array
 	for(int t = m; t<=n; t++){
 		a[t] = sorted[t];
	 }
 	
 } 
 
 void mergeSort(int a[], int m, int n){
 	if(m<n){
 		int middle = (m+n)/2;
 		mergeSort(a, m, middle);
 		mergeSort(a, middle+1, n);
 		merge(a, m, middle, n);
	 }
 }

 
 int main(void){
 	int arr[num] = {7, 6, 5, 8, 3, 5, 9, 1};
 	mergeSort(arr, 0, num-1);
 	for(int i = 0; i<num; i++){
 		printf("%d ", arr[i]);
	 }
 	
 }