퀵 정렬(quick sort) 이란

가장 기초적인 정렬 알고리즘 (선택,삽입,버블)을 학습하고 조금 더 복잡한 정렬 알고리즘들을 학습하려고 한다.

이름만 들어도 빠를거 같은 퀵 정렬에 대해서 알아보자.

퀵 정렬 이란?

1. 퀵 정렬은 분할 정복 방식을 통해 정렬하는 알고리즘이다.

    1-1. 퀵 정렬은 피벗(pibot)을 정한 뒤 피벗을 기준으로 리스트를 분할 한다. (피벗 왼쪽, 피벗 오른쪽)

    1-2. 퀵 정렬은 올바르게 정렬될 때까지 재귀적으로 분할 정복한다.

2. 퀵 정렬은 필수적으로 피벗(pibot)을 지정해야 한다. 방식에는 3가지가 있다. (일반적으로 첫번째값을 많이 쓴다고 한다)

    2-1. 첫번째 값이나 마지막 값을 피벗으로 지정.

    2-2. 첫번째, 가운데 , 마지막 값 중에 중간값을 피벗으로 지정.(Median of Three)

    2-3. 무작위 값을 피벗으로 지정

 

퀵 정렬의 장단점

장점 : 

1. 선택 정렬, 삽입 정렬, 버블 정렬과 같은 O(n2) 시간복잡도를 가지는 알고리즘들과 비교했을 때 ,

퀵 정렬은 일반적으로 O(n log n)시간 복잡도를 가지기에 빠르다.

단점:

1. 대부분의 경우 빠르지만 피벗값 설정에 따라 최악의 경우 O(n2)의 시간복잡도를 가진다.

때문에 아무값이나 피벗으로 지정하면 시간복잡도에서 불리할 수 있다. Median of Three 방식으로 피벗을 지정하는게 가장 안정적인

방법으로 알려져있다.

 

* 퀵 정렬 예시

int arr[] = {4,1,5,7,2,3,6};

이러한 배열이 있을때 아래와 같이 설정된다.

pibot lt rt

 

{4, 1 ,5 ,7 ,2 ,3 ,6 }

 

lt는 피벗보다 큰 값을 찾을때까지 증가되고 rt는 피벗보다 작은 값을 찾을때까지 감소된다. 

 

{4, 1 ,5 ,7 ,2 ,3 ,6 }

lt가 rt보다 인덱스번호가 낮으므로 arr[lt], arr[rt]교체.

{4, 1 ,3 ,7 ,2 ,5 ,6 }

lt는 피벗보다 큰 값을 찾을때까지 증가되고 rt는 피벗보다 작은 값을 찾을때까지 감소된다. 

{4, 1 ,3 ,7 ,2 ,5 ,6 }

lt가 rt보다 인덱스번호가 낮으므로 arr[lt], arr[rt]교체.

{4, 1 ,3 ,2 ,7 ,5 ,6 }

lt는 피벗보다 큰 값을 찾을때까지 증가되고 rt는 피벗보다 작은 값을 찾을때까지 감소된다. 

{4, 1 ,3 ,2 ,7 ,5 ,6 }

엇갈렸다. 이때는 rt값과 피벗값을 교체한다.

{2, 1 ,3 ,4 ,7 ,5 ,6 }

 

이렇게 lt가 rt보다 커져서 엇갈리고 피벗값을 교체하게 된다.

이다음부터 rt 4를 기준 분할하여 이 과정을 분할된 배열의 길이가 1이 될때까지 반복한다.

 

{2, 1 ,3 }

{7, 5 ,6 }

 

소스코드

import java.util.*;
public class Main {
    public void solution(int [] arr, int start, int end) {
        if(start>=end) return;
        int pibot = start;
        int lt= start+1;
        int rt= end;
        int tmp;
        while (lt<=rt){
            //lt가 피벗보다 큰 값을 만날때까지 lt++
            while (lt<=rt && arr[lt] <= arr[pibot]) lt++;
            //rt가 피벗보다 작은 값을 만날때까지 rt--
            while (rt>pibot && arr[rt] >= arr[pibot])rt--;
            //엇갈리는 경우로써, 피벗과 rt교체
            if(lt>rt){
                tmp = arr[rt];
                arr[rt] = arr[pibot];
                arr[pibot]= tmp;
            }
            else{
                tmp = arr[lt];
                arr[lt] = arr[rt];
                arr[rt] = tmp;
            }
        }
        solution(arr,0,rt-1);
        solution(arr,rt+1,end);
    }
    public static void main(String[] args) {
        Main M = new Main();
        Scanner kb = new Scanner(System.in);
        int arr[] = {4,1,5,7,2,3,6};
        M.solution(arr, 0, arr.length-1);
        for(int i : arr ) System.out.print(i+" ");
    }
}