퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

기준값(일반적으로 전체 원소중 가운데 위치한 원소) 피봇(povot)을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하고 기준값보다 작은 원소들은 왼쪽 부분집합으로, 큰 원소들은 오른쪽 부분집합으로 정렬한다.

왼쪽 끝에서 오른쪽으로 이동하면서 피봇보다 크거나 같은 원소를 찾아 L이라 하고, 오른쪽 끝에서 왼쪽으로 이동하면서 피봇보다 작은 원소를 찾아 R이라 한 후 두 원소를 교환한다.

L과 R이 만나면 피봇과 교환한 후 위치를 확정한다.

확정된 피봇의 위치를 기준으로 왼쪽, 오른쪽 부분집합에 대해서 퀵 정렬을 반복한다.

부분집합의 크기가 1 이하가 되면 종료한다.

​

퀵 정렬은 버블 정렬과 같이 교환 방식의 정렬이지만 버블 정렬은 원소가 이동할 때 한칸씩 이동하는 반면 퀵 정렬은 최대한 가까이 이동 시켜 비교, 교환 횟수를 줄인 정렬이다.

평균 시간 복잡도는 O(nlog2n)이다.

​

예시)

{57, 16, 41, 2, 50, 6, 32, 27}

​

1. 네번째 자리에 있는 2를 피봇으로 정하고 퀵 정렬을 한다.

{57,    16,    41,    2,    50,    6,    32,    27}

L, R                  피봇

L이 찾은 57과 찾지못해 만난 R

===> L과 R이 만났으니 피봇과 교환하고 위치 확정

{2,     16,    41,    57,    50,    6,    32,    27}

​

2. 왼쪽 부분집합은 비어있는 공집합이기 때문에 수행하지 않고 오른쪽 부분집합에 대하여 가운데 있는 50을 피봇으로 정하고 퀵 정렬을 한다.

{2,    16,    41,    57,    50,    6,    32,    27}

             L이 찾은 57  피봇           R이 찾은 27

===> L과 R을 교환 후 다시 찾는다.

{2,    16,    41,    27,    50,    6,    32,    57}

                                피봇          L, R

                                 R이 찾은 32와 찾지 못해 만난 L

===> L과 R이 만났으니 피봇과 교환하고 위치 확정

{2,    16,    41,    27,    32​,    6,    50,    57}

​

3. 오른쪽 부분집합은 크기가 1이기 때문에 수행하지 않고 왼쪽 부분집합에 대하여 가운데 있는 24을 피봇으로 정하고 퀵 정렬을 한다.

{2,    16,    41,    27,    32,    6,    50,    57}

                 L    피봇             R

===> L과 R을 교환 후 다시 찾는다.

{2,    16,    6,    27,    32,    41,    50,    57}

               피봇이면서 L, R

===> L과 R이 만났으니 피봇과 교환하고 위치 확정(제자리)

{2,    16,    6,    ​27,    32,    41,    50,    57}

​

4. 왼쪽 부분집합에 대하여 16을 피봇으로 정하고 퀵 정렬을 한다.

{2,    16,    6​,    27,    32,    41,    50,    57}

     피봇,L   R

===> L과 R을 교환하는데 L이 피봇이므로 위치를 확정

{2,    6,    16,    27,    32,    41,    50,    57}

​

5. 왼쪽 부분집합은 크기가 1이기 때문에 수행하지 않고 오른쪽 부분집합에 대하여 32를 피봇으로 정하고 퀵 정렬을 한다.

{2,    6,    16,    27,    32,    41,    50,    57}

                             피봇,L,R

===> L과 R이 만났으니 피봇과 교환하고 위치 확정(제자리)

{2,    6,    16,    27,    32,    41,    50,    57}

​

6. 오른쪽 부분집합의 크기가 1이기 때문에 퀵 정렬을 종료한다.

{2,    6,    16,    27,    32,    41,    50,    57}

​

프로그램 작성)

package test;

class Sort {
	public void quickSort(int[] a, int start, int end) {
		if(start < end) {
			int pivot = divide(a, start, end);
			
			// 재귀 호출을 통해 반복 실행
			quickSort(a, start, pivot-1);
			quickSort(a, pivot+1, end);
		}
		
	}
	
	public int divide(int[] a, int start, int end) {
		int pivot, L, R;
		
		L = start;
		R = end;
		pivot = (start + end) / 2;
		
		while(L < R) {
			// 피봇보다 작으면 증가
			while((a[L] < a[pivot]) && (L < R)) {
				L++;
			}
		
			// 피봇보다 크거나 같으면 감소
			while((a[R] >= a[pivot]) && (L < R)) {
				R--;
			}
			
			if(L < R) {
				swap(a, L, R);
				
				if(L == pivot) {
					// 피봇의 위치가 변경된 경우
					return R;
				}
			}
		}
		
		// L > R이 된 경우
		swap(a, pivot, R);
		
		return R;
	}
	
	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

public class Test {
	public static void main(String[] args) {
		int a[] = {57, 16, 41, 2, 50, 6, 32, 27};

		System.out.println("정렬 전 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Sort s = new Sort();
		s.quickSort(a, 0, 7);

		System.out.println("정렬 후 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
	}
}

실행 결과)