알고리즘 기초 4.퀵정렬

퀵정렬에 관하여...

분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 속도를 자랑하는 정렬 방법이다. (단. 언제나 빠른것은 아니다)

합병 정렬(merge sort)과는 달리 퀵 정렬은 리스트를 비균등하게 분할한다.

분할 정복(divide and conquer) 방법

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.

과정 

1. 리스트안에 안에 있는 요소를 하나 선택한다. 이렇게 고른 원소를 피벗(pivot)이라고 부른다.

2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)

3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다

분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 바놉ㄱ한다.

부분 리스트에서도 마찬가지로 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.

4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

리스트의 크기가 0이나 1이 될 떄까지 반복!                                                                                                                       

초기상태

5

3

7

9

1

2

4

6

8

10

5번 피벗값으로 한다면
왼쪽에서 오른쪽으로 피벗값보다 큰 수를 찾는다. 7

오른쪽에서 왼쪽으로 피벗값보다 작은 수를 찾는다 4

7하고 4를 교체한다

5

3

4

9

1

2

7

6

8

10

왼쪽에서 오른쪽 9

오른쪽에서 왼쪽 2

9와 2를 교체

5

3

4

2

1

9

7

6

8

10

왼쪽에서 오른쪽 9

오른쪽에서 왼족 1

왼쪽에서 오른쪽과 오른쪽에서 왼쪽으로 가는 부분이 엇갈려서 겹치게 될때..

오른쪽에서 왼쪽인 값을 피벗값과 교체한다.

1

3

4

2

5

9

7

6

8

10

피벗값이 교체 되었을 때 피벗값을 기준으로 왼쪽은 피벗값보다 작은 수가 나열되어 있으며

오른쪽엔 피벗값보다 큰수가 나열되어있다.

마찬가지로 

나눠진 이 두개를 퀵정렬로 다시 정렬하면된다!!

1

3

4

2

6

7

6

8

10

퀵정렬은 피벗값에 따라서 최선은nlogN이지만 최악은 n^2이 될수 있으므로 유의해야한다.

c언어.

#include <stdio.h>
int number = 10;
int data[10] = {1,10,5,8,7,6,4,3,2,9};
//특정한 값을 기준으로 큰값과 작은 값을 바꾼다. 피벗값. 
void quickSort(int *data,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(data[i]<=data[key]){ // 키 값보다 큰 값을 만날 뗴까지.. 
			i++;
		}
		while(data[j]>=data[key]&&j>start){ //키 값보다 작은 값을 만날 때까지.... 왼쪽에서 시작하는 지점 보단 커야한다. 
			j--; 
		}
		if(i > j){
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		} else {
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}
	 quickSort(data, start, j-1);
	 quickSort(data,j+1,end);
}
int main(void){
	quickSort(data,0,number-1);
	for(int i=0;i<number;i++){
		printf("%d ",data[i]);
	}
}

java 
package basic;
public class QicSot {
	static int number= 10;
	static int data[] = {1,3,5,7,9,2,4,6,8,10};
	public static void quick(int data[],int start, int end) {
		if(start>=end) {
			return;
		}
		
		int key = start;
		int i	= start+1;
		int j	= end;
		int temp;
		
		while(i<=j) { //엇갈릴떄 까지 반복
			
			while(data[i]<=data[key]) {
				i++;
			}
			
			while(data[j]>=data[key]&&j>start) {
				j--;
			}
			
			if(i > j) {
				temp		=	data[j];
				data[j]		=	data[key];
				data[key]	=	temp;
			}
			else {
				temp	=	data[j];
				data[j]	=	data[i];
				data[i]	=	temp;
			}
		}
		quick(data,start,j-1);
		quick(data,j+1,end);
	}
	public static void main(String[] args) {
		quick(data,0,number-1);
		for(int i=0; i<number; i++) {
			System.out.print(data[i]+" ");
		}
	
	}
}