Java - 알고리즘 ( quick sort )

1. 퀵 정렬이란?

• 퀵 정렬 ( quick sort )이란 ?
  • 정렬 알고리즘의 꽃
  • 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성함
  • 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
  • 함수는 왼쪽 + 기준점( pivot ) + 오른쪽을 리턴함

2. 퀵 정렬의 구현

// src/com.company/QuickSort.java

package com.company;

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

public class QuckSort {
    public ArrayList<Integer> splitFunc(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.splitFunc(leftArr));
        mergedArr.addAll(Arrays.asList(pivot));
        mergedArr.addAll(this.splitFunc(rightArr));

        return mergedArr;
    }
}

아주 간단히 구현할 수 있다.

• 만약 리스트의 갯수가 1개라면 그대로 해당 리스트를 반환합니다.
• 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 놓습니다.
• left, right 리스트 변수를 만들고
• 맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교
  • 기준점보다 작으면 left.add(해당 데이터)
  • 기준점보다 크면 right.add(해당 데이터)
• 결국 QucikSort.sort(left) + pivot + QuickSort.sort(right)을 리턴하는 방식으로 재귀 호출

위와 같이 정상작동함을 확인할 수 있습니다.

3. 알고리즘 분석

4. 알고리즘 분석

• 병합정렬과 유사, 시간복잡도는 O(n log n)
  • 단, 최악의 경우
    • 이미 정렬된 배열에서 pivot이 가장 크거나, 가장 작으면 가장 큰 시간이 소요됨
    • 모든 데이터를 비교하는 상황이 나옴
    • O($n^2$)