[알고리즘] 자바에서의 퀵 정렬

퀵 정렬(Quick Sort)

- 퀵 정렬은 정렬 알고리즘의 꽃이라고 할 수 있다.

- 기준점(pivot) 을 정해서, 기준점 보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성한다.

- 각 왼쪽, 오른쪽은 재귀 용벙을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다.

- 함수는 왼쪽 + 기준점 + 오른쪽 으로 리턴한다.

- 기준점을 고를땐 해당 리스트의 맨 앞에 있는 데이터로 결정한다.

- 왼쪽, 오른쪽으로 갈라진 이후, 각 리스트 길이가 1 이하라면 해당 리스트를 그대로 리턴해준다.

- 그렇지 않으면 기준점을 결정하고 해당 기준점 보다 작은지 큰지를 판별한 다음, 작다면 왼쪽 재귀 호출, 크다면 오른쪽 재귀 호출을 수행한다.

- 각 재귀 호출을 수행하면서 정렬이 완료되면, 자바의 경우 addAll() 과 같은 메소드를 통해 리스트 끼리 병합해준다.

 

직접 자바 코드로 작성해보자.

- QuickSort.java

import java.util.ArrayList;
import java.util.List;

public class QuickSort {
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>();
		list.add(3);
		list.add(6);
		list.add(17);
		list.add(1);
		list.add(9);
		list.add(5);
		list.add(4);
		
		System.out.println(qsort(list).toString());
	}

	private static List<Integer> qsort(List<Integer> list) {
		if(list.size() <= 1)
			return list;
		
		int pivot = list.get(0);
		
		List<Integer> leftList = new ArrayList<Integer>();
		List<Integer> rightList = new ArrayList<Integer>();
		
		for(int i = 1; i < list.size(); i++) {
			if(pivot > list.get(i))
				leftList.add(list.get(i));
			else
				rightList.add(list.get(i));
		}
		
		List<Integer> resultList = qsort(leftList);
		resultList.add(pivot);
		resultList.addAll(qsort(rightList));
		return resultList;
		
	}
}

- 배열을 이용하는 경우도 작성하고 싶었으나, 기준점 보다 작거나 큰 경우 만들어질 배열의 크기를 특정하기가 쉽지 않아 리스트 자료구조로만 작성하는 방식으로 진행했다.

 

알고리즘 분석

- 병합정렬과 유사하며, 시간복잡도는 O(nlog n) 이다.

- 단 최악의 경우는 다음과 같다.

    - 맨 처음 pivot 이 가장 크거나, 가장 작으면 모든 데이터를 비교하는 상황이 나오게 된다.

    - O(n^2)

 

분할 정복을 이용하는 알고리즘

기준점을 사이에 두고 왼쪽, 오른쪽, 왼쪽, 오른쪽....과 같이 길이가 긴 리스트를 잘게 잘게 쪼개서 분류하여 정렬하는 알고리즘이다.

- 전체 리스트 부터 시작하여 잘개 쪼개서 정렬한 다음 다시 합쳐서 최종 결과를 반환받는다.

- 하향식 접근법을 이용하여 알고리즘을 수행하므로 분할 정복법에 해당한다.