[알고리즘] Quick Sort

Quick Sort

개념

• 기준점(pivot)을 정한 후, 기준점을 기준으로 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 분류하는 작업을 재귀적으로 반복하여 정렬하는 알고리즘이다.
  1. 기준점(pivot)을 정한다. (보통 가장 왼쪽이나 가장 오른쪽으로 정한다.)
  2. 기준점보다 큰 데이터는 left list로, 큰 데이터는 right list로 분류한다.
  3. left/right list를 다시 1번 step으로 넘어가서 기준점을 정하고 데이터를 나눠서 분류하는 작업을 반복한 후 데이터를 합친다.
• 분할 정복(Divide and Conquer) 알고리즘이다.
• 평균 시간복잡도는 O(nlog n)이다. (log n은 레벨, n개은 데이터 정렬 비용)
• 최악의 경우 맨 처음의 pivot이 가장 크거나 가장 작다면 모든 데이터를 비교해야하여 O($n^2$)이 나온다.

예시

사진 출처: https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

Java 구현 코드

package algorithm;

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

public class QuickSort {

	public static void main(String[] args) {
		Integer[] arr = {3,8,43,20,9,15,61,54,13,94,2,10};
		
		List<Integer> list = new ArrayList<>(Arrays.asList(arr));
		
		System.out.println(quickSort(list).toString());
		
	}
	public static List<Integer> quickSort(List<Integer> arr) {
		List<Integer> leftList = new ArrayList<>();
		List<Integer> rightList = new ArrayList<>();
		
		// 크기가 1보다 작거나 같으면 그대로 반환
		if (arr.size() <= 1)
			return arr;
		
		int pivot = arr.remove(0);
		
		// data가 pivot보다 작으면 왼쪽으로, 크면 오른쪽으로 봔환
		for (int data: arr) {
			if (pivot > data)
				leftList.add(data);
			
			else rightList.add(data);
		}
		
		// 왼쪽, 오른쪽 list를 다시 quick sort한 후
		// 왼쪽 list + pivot + 오른쪽 list를 반환
		quickSort(leftList).add(pivot);
		leftList.addAll(quickSort(rightList));
		return leftList;
		
	}	
}