정렬 알고리즘 :: 퀵 소트(Quick sort)

퀵 소트 Quick sort

 

 

치타가 지상에서 가장 빠른 속도를 가진 동물이라면, 퀵소트는 가장 빠른 정렬 알고리즘이다.

이미 달릴 대로 달린 그의 표정에서 여유가 느껴지지 않는가.

 

마찬가지로 퀵소트란 이름만 들어도 알 수 있듯이, 가장 빠른 속도를 자랑하는 정렬 알고리즘이다.

개념만 보면 비교를 통해 정렬하는 방식이 여느 정렬알고리즘과 큰 차이가 없으나,

컴퓨터 아키텍쳐를 고려한 비교법을 채택했기때문에 효율적인 정렬이 가능해진다.

 

원리는 데이터 열의 중간 값을 찾아 기준으로 삼고 좌우로 값을 위치시키는 것이다.

이러한 가운데 원소 하나를 피벗(Pivot)이라 하며, 좌우로 나누는 것을 분할이라고 한다.

즉, 피벗을 정한 후 분할을 반복하는 재귀적 호출을 통해 정렬이 이루어진다.

 

예를 들어, { 5, 1, 7, 10, 3} 의 정렬되지 않은 배열이 있다.

 

5	1	7	10	3	Pivot은 7이 된다. 7보다 작으면 왼쪽, 크면 오른쪽에 위치시킨다. 만약 끝 값이 조건에 맞지 않을 경우 자신의 위치와 맞바꿔 해결한다.
5	1	3	10	7	분할된 좌측 열에서 Pivot은 1이 된다. 같은 방식으로 정렬을 수행한다.
1	5	3	10	7	Pivot은 5가 되고, 같은 방식으로 정렬을 수행한다.
1	3	5	10	7	이제 우측 배열에서의 Pivot은 10이 된다. 같은 방식으로 정렬을 수행한다.
1	3	5	7	10	조건을 만족할 경우 정렬이 완료된다.

 

상세설명

헷갈릴 수 있는데, 값을 가리키는 포인터가 피봇, 좌측 인덱스, 우측 인덱스로 총 3개인 셈이다.

최초 5, 1, 7, 10, 3이 있을 때, 피봇 7보다 작은 값은 좌측에 있어야하고 큰 값은 우측에 있어야한다.

즉, 7을 가리킬 Pivot 인덱스와, 좌측의 값을 가리킬 인덱스(좌↓), 우측을 가리킬 인덱스(↓우)가 필요한 셈이다.

 

좌↓		피봇		↓우
5	1	7	10	3

피봇이 7일 때, 좌측 인덱스가 가리키는 5와 비교한다. 7이 크기때문에 그대로 유지한채로 좌측 인덱스를 한칸 늘린다.

 

---

~ 광고 타임 ~

---

 

	좌↓	피봇		↓우
5	1	7	10	3

 

피봇이 여전히 7일 때, 좌측 인덱스가 가리키는 1과 비교한다. 7이 크기때문에 그대로 유지한채로 좌측 인덱스를 한칸 늘린다.

이때, 피봇과 인덱스가 겹쳐지게되면 그대로 둔채로 우측 값을 비교하기 시작한다.

 

		좌↓, 피봇		↓우
5	1	7	10	3

 

피봇 7과 우측 인덱스가 가리키는 3의 값을 비교하니 7보다 작음을 알 수 있다.

조건에 맞지 않으므로, 좌측 인덱스 값과 우측 인덱스 값을 교환하고 우측 인덱스를 한칸 줄인다.

 

		좌↓	↓우	피봇
5	1	3	10	7

 

계속해서 피봇 7과 우측 인덱스가 가리키는 10을 비교했을 때, 7보다 크고 우측인덱스가 가리키므로 맞는 조건이 된다.

그러므로 우측 인덱스를 한 칸 줄인다.

 

		좌↓, ↓우		피봇
5	1	3	10	7

 

좌측 인덱스와 우측 인덱스가 만나게 되었다. 이를 기점으로 분할 정복이 시작된다.

좌측의 5, 1 배열을 새로운 배열이라고 받아들이고 피봇은 1이되며, 좌측 값 5와 우측값 1을 가지고 똑같이 진행한다.

 

 

---

~ 광고 타임 ~

---

 

 

좌↓	피봇, ↓우
5	1

 

피봇 1과 좌측 인덱스 5를 비교했을 때, 5값이 크다. 때문에 좌측 인덱스와 우측 인덱스를 교환하고 좌측인덱스를 한칸 늘린다.

 

피봇	좌↓, ↓우
1	5

 

피봇 1과 우측 인덱스 5를 비교하면 조건에 일치하므로, 우측 인덱스를 한칸 줄인다. 

 

피봇, ↓우	좌↓
1	5

 

우측 인덱스와 좌측 인덱스가 어긋나는 시점이므로 부분 정렬을 마친후 남은 배열을 다시 같은 방법으로 반복하여 정렬하여 마무리하게 된다.

 

즉, 기본 순서는 피봇을 찾고 좌측값과 비교하면서 우측 인덱스와 교환한다. 좌측 인덱스가 피봇과 같거나 넘어갈 때, 우측 인덱스를 줄여가며 비교하여 자리를 바꾼다.

우측인덱스와 좌측인덱스가 같거나 서로를 넘어갈 때, 좌우로 나눠진 부분 배열에서 다시 피봇을 찾아 과정을 반복한다.

 

 

 

 

JAVA 코드

package tisory.blog.it_ing;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		System.out.println(" == 아이티-잉 정렬 알고리즘 == \n");
		int[] arr = {5, 1, 7, 10, 3};

		System.out.println("#4. 퀵정렬");
		System.out.println("Input : " + Arrays.toString(arr));
		fn_QuickSort(0, arr.length-1, arr); //좌, 우 인덱스값과 배열 전달
		System.out.println("Result : " + Arrays.toString(arr));
		
	}
	private static void fn_QuickSort(int left, int right, int arr[]) {
		if(arr == null || arr.length == 0){ return; }
		int pivot = arr[(left+right)/2]; //중간값을 피봇으로 삼는다.
		int lIdx = left, rIdx = right, temp =0; //좌, 우 인덱스 설정
		
		while(lIdx <= rIdx){ //좌우 인덱스가 교차하거나 같지 않을 경우 반복
			while(arr[lIdx] < pivot){ lIdx++;} //피봇이 좌측인덱스 값보다 크면 인덱스만 늘린다.
			while(arr[rIdx] > pivot){ rIdx--;} //피봇이 우측인덱스 값보다 작으면 인덱스만 줄인다.
			if(lIdx <= rIdx){ //피봇과 비교했을 때 조건에 만족하지 않으면 인덱스 끼리 값을 교환한다.
				temp = arr[lIdx];
				arr[lIdx] = arr[rIdx];
				arr[rIdx] = temp;
				lIdx++;
				rIdx--;
			}
		}

		System.out.println("STEP : " + Arrays.toString(arr));
		if(left < rIdx){ fn_QuickSort(left, rIdx, arr); } //좌측 배열로 분할해 반복한다.
		if(lIdx < right){ fn_QuickSort(lIdx, right, arr); } //좌측완료 후 우측 배열을 분할해 반복한다.
	}
}

 

결과

 

 

 

C/C++ 코드

 

#include <stdio.h>
#define ARRAY_MAX 5 //배열의 길이를 설정해봤다.

//출력 함수
void printArr(int *arr){
	int i=0;
	for(i=0; i<ARRAY_MAX; i++){
		printf(" %d", arr[i]);
	}
	printf("\n");
}

//퀵 소트 재귀함수
void fn_QuickSort(int left, int right, int *arr){
	int lIdx=left, rIdx=right, temp;
	int pivot = arr[(left+right)/2];

	while(lIdx <= rIdx){
		while(arr[lIdx] < pivot){ lIdx++; }
		while(arr[rIdx] > pivot){ rIdx--; }
		if(lIdx <= rIdx){
			temp = arr[lIdx];
			arr[lIdx] = arr[rIdx];
			arr[rIdx] = temp;
			lIdx++;
			rIdx--;
		}
	}

	//출력
	printf("STEP : ");
	printArr(arr);

	//분할
	if(left < rIdx){ fn_QuickSort(left, rIdx, arr); }
	if(lIdx < right){ fn_QuickSort(lIdx, right, arr); }
}

int main(void){
	int arr[ARRAY_MAX] = {5, 1, 7, 10, 3};

	printf("#4. ÄüÁ¤·Ä\ninput :");
	printArr(arr);
	//퀵정렬 재귀 함수 호출
	fn_QuickSort(0, ARRAY_MAX-1, arr);

	printf("Result :");
	printArr(arr);

	return 0;
}

 

결과

 

 

 

 

 

 

끝.