퀵 정렬(Quick Sort)::자료구조

 QuickSort는 주어진 array를 분할 정복하고, pivot을 설정해 pivot과 비교하며 정렬하는 방법입니다.

 pivot 설정은 개발자에 따라 다르게 설정할 수 있지만, 보통은 중앙값을 pivot으로 설정합니다.

 

 분할 정복을 하기 때문에 최소, 평균 시간복잡도가 O(n*log n)이지만, pivot과 비교되는 값이 항상 조건에 충족되어 pivot을 지속해서 바꿔주어야 하는 경우(최악의 경우) O(n^2)이 됩니다.

 

 기존의 array에서 값을 변경하기 때문에 공간복잡도는 1입니다.

 

 자바와 벡터를 이용해 QuickSort를 구현해 보겠습니다.

 

 

Java 코드

 

import java.util.Vector;

public class QuickSort {
	
	static void quickSort(Vector<Integer> v, int s, int e) {
		int i = s;
		int j = e;
		int pivot = v.get((s + e) / 2);
		
		while (i <= j) {
			while (v.get(i) < pivot)	++i;
			while (pivot < v.get(j))	--j;
			
			if (i <= j) {
				int temp = v.get(i);
				v.set(i, v.get(j));
				v.set(j, temp);
				
				++i; --j;
			}
		}
		
		if (s < e) {
			quickSort(v, s, i - 1);
			quickSort(v, i, e);
		}
	}
	
	public static void main(String[] args) {
		Vector<Integer> v = new Vector<>();
        
		v.add(20);
		v.add(112);
		v.add(403);
		v.add(52);
		v.add(70);
		v.add(6);
		v.add(33);
		v.add(45);
		v.add(50);
		v.add(7);
		v.add(61);
		v.add(33);
		
		System.out.println(v);
		quickSort(v, 0, v.size() - 1);
		System.out.println(v);
	}
	
}

 

결과

 

[20, 112, 403, 52, 70, 6, 33, 45, 50, 7, 61, 33]
[6, 7, 20, 33, 33, 45, 50, 52, 61, 70, 112, 403]