[알고리즘] 퀵정렬

퀵 소트

퀵소트는 비교정렬의 한 종류이다.

찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다.

데이터 양이 크고 섞여 있을 경우 가장 빠른 속도를 낼 수 있다.

 

알고리즘

1. 리스트 가운데서 하나의 원소를 고른다. (이 원소를 피벗이라 한다.)

2. 피벗 앞에는 피벗보다 작은 원소들이 오고, 피벗 뒤에는 큰 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다.

이렇게 피벗의 위치가 정해진다.

3. 피벗의 앞쪽 리스트와 피벗의 뒤쪽 리스트에 대하여 1, 2 를 반복한다.

 

소스코드[Java]

 

package sdk.java.example.sort;

import java.util.Random;

public class QuickSort {

    /**
     * 퀵 소트 처리
     * 
     * @param array
     * @param left
     * @param right
     */
    public void sort(Integer[] array, int left, int right) {

        if(left >= right){
            printArray(array);
            return;
        } 
        
       int low = left + 1; // low 는 left 의 한칸 옆
        int high = right;   // high 는 right 와 동일함
        int pivot = array[left];
        
        while (low <= high) {
            while (low <= right && array[low] <= pivot) {
                low++;
            }

            while (left + 1 <= high && pivot <= array[high]) {
                high--;
            }

            if (low <= high) {
                int temp = array[low];
                array[low] = array[high];
                array[high] = temp;
            } else {
                array[left] = array[high];
                array[high] = pivot;
            }
        }

        sort(array, left, high - 1 );
        sort(array, high + 1, right );
    }

    /**
     * 배열 출력
     * 
     * @param array
     */
    public <E> void printArray(E[] array) {
        for (E value : array) {
            System.out.print(value);
            System.out.print(" ");
        }
        System.out.println("");
    }
    
    /**
     * 무작위 Int 배열 생성
     * 
     * @param capacity
     * @param randomBound
     * @return
     */
    public Integer[] initArray(int capacity, int randomBound) {
        Integer[] array = new Integer[capacity];
        Random random = new Random();
        for (int i = 0; i < capacity; i++)
            array[i] = random.nextInt(randomBound);
        
        return array;
    }

    public static void main(String[] args) {

        int capacity = 10;
        int randomBound = 100;
        QuickSort quick = new QuickSort();
        
        // 정렬 대상 생성
        Integer[] array = quick.initArray(capacity, randomBound);
        quick.printArray(array);
        
        System.out.println("------------ start -------------");
        
        quick.sort(array, 0, array.length - 1);
    }
}

 

참고

http://navercast.naver.com/contents.nhn?rid=2871&contents_id=90163