평균 O(nlogn) - Quick sort (퀵정렬) 알고리즘

퀵 정렬은 분할 정복 알고리즘으로 피벗을 이용하여 원소들을 정렬하는 알고리즘이다.

1. 피벗을 하나 선택하고 왼쪽에서는 피벗보다 큰 값을 찾고, 오른쪽에서는 피벗보다 작은 값을 찾아 두 원소를 교환한다.

2. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 같은 위치에 갈 때까지 계속 반복한다.

3. 피벗과 탐색위치에 해당하는 숫자를 바꿔준다.

4. 탐색 위치를 기준으로 두 부분으로 나누어 다시 처음부터 반복한다.

5. 반복이 끝난다면 부분리스트들을 이어서 합친다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class NlogNSort_quickSort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        int n = Integer.parseInt(br.readLine());

        int[] a = new int[n];

        for(int i = 0; i < a.length; i++){
            a[i] = Integer.parseInt(br.readLine());
        }

//      ======================================

        quick_sort(a, 0, a.length - 1 );

//      ======================================
        for(int i = 0; i < a.length; i++){
            System.out.print(a[i] + "\n");
        }

    }

    //quick sort
    public static void quick_sort(int[] a, int lo, int hi){
        if(lo >= hi){
            return;
        }

        int pivot = partition(a, lo, hi);

        quick_sort(a, lo, pivot - 1);
        quick_sort(a, pivot + 1, hi);


    }

    private static int partition(int[] a, int left, int right) {

        int lo = left;
        int hi = right;
        int pivot = a[left];

        while(lo < hi){

            while(a[hi] > pivot && lo < hi){
                hi--;
            }

            while(a[lo] <= pivot && lo < hi){
                lo++;
            }

            int tmp = a[lo];
            a[lo] = a[hi];
            a[hi] = tmp;

        }

        int tmp = a[left];
        a[left] = a[lo];
        a[lo] = tmp;

        return lo;
    }


}

comment :

# 평균 O(nlogn), 최악의 경우(pivot이 계속해서 최소 또는 최대일 경우)엔 O(n^2)까지 증가할 수 있다.