자료구조 - 퀵 정렬

퀵 정렬은 배열에서 하나의 요소를 선택하여 기준(pivot)으로 삼는다. 그리고 배열의 왼쪽 부분과 오른쪽 부분에서 인덱스 값을 탐색하며 기준보다 크거나 작으면 그 두 수를 서로 교환하는 방식이다.

다음과 같은 배열이 있다고 가정할 때

 

기준을 잡는데 나는 왼쪽 인덱스를 기준으로 삼았다. 이 때 left 는 배열의 가장 왼쪽, right 는 배열의 가장 오른쪽 인덱스를 가리킨다.

 

low와 high 는 서로 거리를 좁여가며 수를 비교하는데 low는 기준보다 큰 값을 찾고, high 는 기준보다 작은 값을 찾는다.

 

 

low 와 high 가 각각 수를 찾으면 서로 위치를 교환한다.

 

교환 후 다시 low 와 high는 수를 찾는다.

 

또 low 와 high 가 조건에 맞는 수를 찾으면 서로 위치를 교환한다.

그렇게 찾다가 high 가 low 보다 낮은 인덱스에 위치하면 작은 값인 high 와 pivot 값의 위치를 교환한다.

5 를 기준으로 왼쪽 구간과 오른쪽 구간을 보면 왼쪽은 5보다 작고 오른쪽은 5보다 큰 것을 알 수 있으며 왼쪽, 오른쪽 구간은 다시 위 과정을 반복한다.

 

 

 

▼퀵 정렬 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void Swap(int arr[], int idx1, int idx2)
	{
		int temp = arr[idx1];
		arr[idx1]=arr[idx2];
		arr[idx2]=temp;
	}
	public static void QuickSort(int arr[], int left, int right)
	{
		if(left<=right)
		{
			int pivot = Partition(arr,left,right);
			QuickSort(arr,left,pivot-1);
			QuickSort(arr,pivot+1,right);
		}
	}
	public static int Partition(int arr[], int left, int right)
	{
		int pivot = arr[left];
		int low = left+1;
		int high = right;
		while(low<=high)
		{
			while( low<=right && pivot>=arr[low])
				low++;
			while( high>=(left+1) && pivot<=arr[high])
				high--;
			if(low<=high)
				Swap(arr,low,high);
		}
		Swap(arr,left,high);
		return high;
	}
	public static void main(String[] args){
		int arr[] = {5,3,8,4,9,1,6,2,7};
		
		System.out.print("정렬 전 배열 : ");
		for(int val : arr)
			System.out.print(val+" ");
	
		QuickSort(arr,0,8);
		
		System.out.println();
		
		System.out.print("정렬 후 배열 : ");
		for(int val : arr)
			System.out.print(val+" ");
	}
}

 

결과

정렬 전 배열 : 5 3 8 4 9 1 6 2 7 
정렬 후 배열 : 1 2 3 4 5 6 7 8 9