[알고리즘] 퀵 정렬(Quick Sort) - JAVA(자바)

퀵 정렬(Quick Sort)

• 기준 값을 정하고 그 값을 기준으로 작은 값과 큰 값으로 부분리스트를 분할하고 정렬하는 과정을 반복한 뒤,  부분리스트의 길이가 1이 되면 합치는 정렬이다.
  • 기준 값(pivot)을 정한다. (1.왼쪽 끝  2.가운데 3.오른쪽 끝 4. 랜)
  • pivot을 기준으로 왼쪽 시작점(start)에서부터 큰값을 찾고 오른쪽 시작점(end)에서부터 작은 값을 찾는다.
  • 왼쪽에서 큰값과 오른쪽에서 작은 값이 있다면 서로 교환한다.
  • start와 end가 만나면 왼쪽 영역과 오른쪽 영역에서 각각 새로운 피벗을 선정하고 같은 작업을 반복한다.
  • staer와 end 사이에 값이 1개라면 정렬이 종료된다.
  • * 피벗을 왼쪽으로 선정했을 때, 이미 정렬된 배열(오름차순)이라면 피벗은 항상 부분 영역에 가장 작은값이 되기 때문에 왼쪽 영역은 없고 오른쪽 영역만 피봇을 제외하고 계속 정렬하게 된다. -> 최악의 경우로  시간복잡도 O(n²)   -> 안정적으로 사용하려면 가운데를 피벗으로 선택하는 것이 좋다.

• 시간복잡도는 O(nlogn)이다.
  • 분할이 트리형태(6개의 원소를 가진다면 6->3->1)로 이루어지기 때문에 합치는 과정에서 깊이가 log²n이 되고,  값의 대소 비교횟수는 부분 영역의 원소를 다 보게 되므로 n번이 된다. 따라서 시간복잡도는 O(n*log²n) = O(nlogn)이 된다.
• 제자리 정렬(입력받은 배열외에 다른 메모리가 필요하지 않다.)
• 불안정정렬(=동일한 값에 대해 순서가 바뀔수도 있다.)
  • 피벗을 기준으로 반 나눠서 정렬하기 때문에, 같은 값이 서로 떨어져 있다면 순서가 바뀔수도 있다.

 

 

배열[6,3,4,1,5,2]이 있을 때, 퀵 정렬로 정렬하는 과정

분할 및 정렬을 한 후 배열을 합치면 퀵 정렬한 배열이 된다.

 

 

[구현코드 - JAVA]

가운데를 기준값(pivot)으로 정해서 퀵정렬하는 코드

public class QuickSort {
	public static void main(String[] args) {
		int[] arr = {6,3,4,1,5,2};

		quick_sort(arr,0,arr.length-1);
		//정렬 후
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" "); //1 2 3 4 5 6
		}
	}
	
	
	public static void quick_sort(int A[], int start, int end) { // A[start..end]을 오름차순 정렬한다.
		//start=end가 되면 종료 - 부분배열의 크기가 1이 될 때
		if (start >= end) return; 
		
		//분할 후 정렬
		//부분배열 정렬 종료시 start가 part가 됨
		int part = partition(A,start,end);
		quick_sort(A, start, part-1); //왼쪽 영역
		quick_sort(A, part, end); //오른쪽 영역
	}

	//분할한 영역 정렬
	public static int partition(int A[],int start,int end) {
	    int pivot = A[(start+end)/2]; //가운데를 피벗으로
	    
	    while(start<=end) { //start==end면 부분배열 정렬 종료
	    	while(A[start]<pivot) start++;
	    	while(pivot<A[end]) end--;
	    	
	    	//자리 교환
	    	if(start<=end) {
	    		int temp = A[start];
	    		A[start] = A[end];
	    		A[end] = temp;
	    		start++;
	    		end--;
	    	}
	    }
	    
	    return start;
	    
	}
}