퀵

 

 

 

기준점을 잡고 기준점보다 작은 데이터는 좌측, 큰 데이터는 우측으로 정렬한다.

좌측과 우측에 정렬된 데이터들에 대해서 다시 피봇을 설정하고 위 작업을 반복한다.

피봇으로 설정할 때 마다 원소의 위치가 정해진다.

 

모든 원소들에 대해서 피봇을 설정했으면, 정해진 위치를 기반으로 합치며 정렬을 수행한다.

 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> testData = new ArrayList<Integer>();

        for (int index = 0; index < 100; index++) {
            testData.add((int) (Math.random() * 100));
        }

        QuickSort qSort = new QuickSort();
        qSort.sort(testData);
    }
}

class QuickSort {

    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }
        int pivot = dataList.get(0);

        ArrayList<Integer> leftArr = new ArrayList<Integer>();
        ArrayList<Integer> rightArr = new ArrayList<Integer>();

        for (int index = 1; index < dataList.size(); index++) {
            if (dataList.get(index) > pivot) {
                rightArr.add(dataList.get(index));
            } else {
                leftArr.add(dataList.get(index));
            }
        }

        ArrayList<Integer> mergedArr = new ArrayList<Integer>();

        mergedArr.addAll(this.sort(leftArr)); // 아직 정렬되지 않은 부분은 재귀호출로 정렬
        mergedArr.addAll(Arrays.asList(pivot));
        mergedArr.addAll(this.sort(rightArr));// 아직 정렬되지 않은 부분은 재귀호출로 정렬

        return mergedArr;
    }
}

 

 

 

시간복잡도 : O(n logn)

단, 이미 정렬된 배열이나 리스트에 대해서는 O(n^2)