퀵 정렬 (quick sort)

주제(Subject)
--------------------------------------------------------
한글(약어) : 퀵 정렬()
영어(약어) : quick sort()


관련개념(Related Concepts)
--------------------------------------------------------
정렬
알고리즘
분할정복


개요(Summary)
--------------------------------------------------------
- 불안정적
- 제자리 정렬
- C.A.R. Hoare가 고안한 알고리즘
- 평균 수행시간 : O(n log n)
- 최악 수행시간 : O(n^2)
- 분할 정복(divide and conquer)방식


본문(Body)
--------------------------------------------------------
1. 알고리즘
   1) 정렬 키를 나누는 조건 : 아래의 두 조건을 만족하는 키는 정렬과정에서 서로 다른 배열에 있는 키들과 섞이지 않게 된다.
      (1) 왼쪽 배열의 모든 키들은 오른쪽 배열의 가장 작은 키보다 작다
      (2) 오른쪽 배열의 모든 키들은 왼쪽 배열의 가장 큰 키보다 크다.

2. 소스
   1) Java (from Wanginator : Quick Sort)

public class QuickSort {
    public static void quicksort (int[] a) {
        quicksort(a, 0, a.length-1);
    }

    private static void quicksort (int[] a, int l, int r) {
        //base case: list is empty
        if (l>=r) return;

        //recursion step: make partition and sort recursively
        int m = partition(a, l, r);
        quicksort(a,l,m-1);
        quicksort(a,m+1,r);
    }

    //partition the array from l+1 to r with pivot a[l]
    private static int partition (int[] a, int l, int r) {
        int i=l+1; //pointer on left side
        int j=r;   //pointer on right side
        int p = a[l]; //pivot element

        //move pointer to center or swap if on wrong sides
        while (i<=j) {
            if (a[i]<=p) i++;
            else if (a[j]>p) j--;
            else swap(a,i,j);
        }
        //swap pivot element between partitions
        swap(a,l,j);
        //return position of pivot element
        return j;
    }

    //swap two elements in the array
    private static void swap (int[] a, int i, int j) {
        int h = a[i];
        a[i] = a[j];
        a[j] = h;
    }
}

   2) 더 많은 소스 참고하기
      Wikibooks : Algorithm implementation/Sorting/Quicksort
      http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Quicksort

3. 시뮬레이션
   1) GIF

An animation of the quicksort algorithm sorting an array of randomized values. Author: User:RolandH Created with: Ruby 1.8.4, RMagick

모임,단체(Commutities)
--------------------------------------------------------


블로그,개인 홈페이지 등(Humanities)
--------------------------------------------------------


참고문서(References)
--------------------------------------------------------
* 한국어(Korean)
저자. 역자. "제목". 출판사. 출판년도. (ISBN:)

* 영어(English)
저자. 제목, 판, 출판사. 출판년도. (ISBN:)
1. Wikipedia : Quick Sort
   http://en.wikipedia.org/wiki/Quicksort

2. Wanginator : Quick Sort
   http://www.wanginator.de/studium/applets/quicksort_en.html

3. Recursive Sorting (Stephen Y. Chen, Associate Professor,School of Information Technology, Atkinson Faculty of Liberal and Professional Studies, York University)
   http://www.atkinson.yorku.ca/~sychen/research/sorting/sortingHome.html