[Algorithm] Quick Sort

Quick Sort

퀵소트란 분할 정복을 기반으로 만들어진 정렬방법이다.

1. 문제를 해결한다.

2. 문제들을 작은 문제로 분할한다.

3. 문제를 해결한다.

이렇게 큰문제를 해결하고 다시 작은 문제로 분할해 가면서 해결한다.

 

 

 

Pivot

퀵정렬에는 pivot 이라는 개념이 존재한다.

pivot은 정렬할때 기준을 잡아준다.

 

 

 

Quick Sort 용어

• Left: 가장 왼쪽 인덱스(왼쪽)
• Right: 가장 오른쪽 인덱스(오른쪽)
• Low: pivot 보다 큰값을 탐색하기 위한 인덱스
• High: Pivot 보다 작은 값을 탐색하기 위한 인덱스

 

 

Quick Sort 동작과정

• Low 를 증가시키면서 Pivot 보다 큰값을 찾는다.
• High 를 감소시키면서 Pivot 보다 작은 값을 찾는다.
• 찾은 값을 바꿔준다.
• 계속 반복하면서 Low 와 High 가 교차되면 Pivot 과 High 지점을 변경해 준다.
• 그렇게 되면 왼쪽은 Pivot 보다 작은값 오른쪽은 Pivot 보다 큰 값으로 정렬이 된다.

 

 

 

코드구현

package com.company;

public class Main {
    public void swap(int [] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    public int partition(int []arr, int left, int right) {
        int pivot = arr[left];

        int low = left;
        int high = right;

        while(low < high) {

            while (pivot >= arr[low] && low < right) low++;
            while (pivot <= arr[high] && high > left) high--;

            if(low <= high) {
                swap(arr, low, high);
            }
        }

        swap(arr, left, high);
        return high;
    }

    public void quickSort(int []arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex-1);
        quickSort(arr, pivotIndex+1, right);
    }

    public static void main(String[] args) {
        Main main = new Main();
        int []arr = {9,7,22,1,33,444,2,3};
        main.quickSort(arr, 0, arr.length-1);

        for (int i : arr) {
        System.out.print(i + " ");
        }
    }

}