퀵정렬

1. 퀵정렬 (quick sort)

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

각 왼쪽 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하며 위 작업을 반복함

함수는 왼쪽 + 기준점(pivot) + 오른쪽을 리턴함

 

2. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

@Slf4j
public class QuickSort {

    public static List<Integer> quickSort(List<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }

        List<Integer> leftList = new ArrayList<>();
        List<Integer> rightList = new ArrayList<>();
        List<Integer> pivotList = new ArrayList<>();

        Integer pivot = dataList.get(0);

        for (int i = 0; i < dataList.size(); i++) {
            if (pivot > dataList.get(i)) {
                leftList.add(dataList.get(i));
            } else if (pivot < dataList.get(i)) {
                rightList.add(dataList.get(i));
            } else {
                pivotList.add(dataList.get(i));
            }
        }
        return Stream.of(quickSort(leftList), pivotList, quickSort(rightList)).flatMap(Collection::stream).collect(Collectors.toList());
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        log.error("________________ = {}", dataList);


        dataList = quickSort(dataList);

        log.error("________________ = {}", dataList);


    }
}

 

3. 분석

병합정렬과 유사

시간복잡도는 O(nlogn)

최악의 경우(pivot이 가장 크거나 가장 작으면 모든 데이터를 비교해야함) O(n^2)