[Algoritm] 초보자도 쉽게이해하는 퀵정렬 알고리즘! 백준문제풀이, java

퀵정렬(Quick Sort)

https://youtu.be/8hEyhs3OV1w?si=sVFYYhCKw2J13kHx

 

퀵정렬 개념, 퀵정렬이란?

퀵정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다. 

분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 보이는 정렬방법이다.

 

퀵정렬은 주어진 배열에서 하나의 원소(pivot)를 선택한다. 그 다음 배열의 모든 원소를 검사하면서 pivot 보다 작은 값을 pivot의 왼쪽에 , 큰값을 pivot의 오른쪽에 배치한다. 이렇게하면 배열이 두개로 나뉘는데, 두개로 나뉜 배열에서 각각 새로운 pivot을 선택해 동일한 작업을 반복한다. 배열을 더이상 쪼갤 수 없을 때, 즉 크기가 0이나 1이 될 때까지 반복한다.

 

pivot에 따라 시간복잡도가 극명하게 나뉘기 때문에 pivot을 정하는 것이 핵심이다. 대표적으로 세개의 방법이 있는데 다음과 같다.

1) 첫번째 값이나 마지막 값을 pivot으로 정한다.

2) 첫번째값, 가운데 값, 마지막 값 중에 중간 값을 pivot으로 정한다.

3) 무작위 값을 pivot으로 정한다.

 

 

 

그림으로 이해하기

 

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

 

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

 

시간 복잡도

최악

• O(n^2)

최선

• O(nlog₂n)

 

장단점 (사용하면 좋은/나쁜 상황)

장점

• 평균적으로 매우 빠른 수행 속도를 내는 정렬방식이다.
  • 시간복잡도가 같은 정렬알고리즘과 비교했을때 가장 빠르다.
  • 불필요한 데이터 이동을 줄이고, 먼거리의 데이터를 교환하며, 한번 결정된 피벗은 추후 연산에서 제외되기 때문임
• 추가 메보리 공간을 필요로 하지않는다. O(log n)만큼의 메모리만 필요로한다.

단점

• 정렬된 리스트에 대해서는 퀵정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
• pivot에 따라 수행속도가 느려질 수 있다.

 

 

소스코드 예시와 설명 (백준문제_ java)

백준 문제 정렬로 풀기

  문제 -  https://www.acmicpc.net/problem/11004

import java.util.*;
import java.io.*;

public class 퀵정렬_k번째수구하기_11004 {
    public static void quickSort(int[] A, int S, int E, int K){
        if(S<E){
            int pivot = partition(A,S,E);
            if(pivot==K) return; //k번째수가 pivot이면 종료
            else if(pivot>K) quickSort(A, S, pivot-1, K); //k가 pivot보다 작으면 왼쪽 그룹만 정렬
            else quickSort(A,pivot+1, E, K); //k가 pivot보다 크면 오른쪽 그룹만 정렬
        }
    }

    public static void swap(int[] A, int i, int j){
        int temp = A[i];
        A[i]=A[j];
        A[j]=temp;
    }

    public static int partition(int[] A, int S, int E){
        if(S+1==E){
            if(A[S]>A[E]) swap(A,S,E);
            return E;
        }

        int M = (S+E)/2;
        swap(A,S,M); // 피봇을 제일 앞으로 이동 - 계산의 편의를 위함
        int pivot = A[S];
        int i=S+1,j=E;

        while(i<=j){
            while(j>=S+1 && pivot < A[j]){
                j--;
            }
            while (i <= E && pivot > A[i]) {
                i++;
            }
            if(i<=j) swap(A,i++,j--);

        }
        A[S]= A[j];
        A[j] = pivot;
        return j;
    }

    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N;i++) A[i] = Integer.parseInt(st.nextToken());

        quickSort(A, 0, N-1, K-1);

        System.out.println(A[K-1]);

    }
}