퀵 정렬(Quick Sort)



- 리스트 가운데서 하나의 원소를 고름(pivot 선정)

- pivot 앞에는 pivot보다 작은 값이 오고, pivot 뒤에는 pivot보다 큰 값들이 오도록 리스트를 둘로 분할한다.

- 분할된 두 개의 리스트에 대해 재귀함수를 통해 이 과정을 반복한다.

- 시간복잡도 : 최악 O(n^2), 평균 O(nlogn)




JAVA 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Quick {
    
    public void sort(int[] data, int l, int r){
        int left = l;
        int right = r;
        int pivot = data[(l+r)/2];
        
        do{
            while(data[left] < pivot) left++;
            while(data[right] > pivot) right--;
            if(left <= right){    
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        }while (left <= right);
        
        if(l < right) sort(data, l, right);
        if(r > left) sort(data, left, r);
    }
    
    public static void main(String[] args) {
        
        int data[] = {66101345-10};
        
        Quick quick = new Quick();
        quick.sort(data, 0, data.length - 1);
        for(int i=0; i<data.length; i++){
            System.out.println("data["+i+"] : "+data[i]);
        }
    }
}
cs


'JAVA > 정렬' 카테고리의 다른 글

퀵 정렬(Quick Sort)  (4) 2015.10.26
삽입 정렬(Insertion Sort)  (3) 2015.10.26
선택 정렬(Selection Sort)  (2) 2015.10.26
버블 정렬(Bubble Sort)  (2) 2015.10.25

Tags

Read Next

  1. 좋은 글이어서 출처 명확히 하여 퍼가겠습니다.

  2. 비밀댓글입니다

  3. 좋은 자료 잘 보고 갑니다. 감사합니다.
    import java.util.Arrays;
    public class QuickSort {
    public void sort(Integer[] array, int left, int right) {
    int pivot = array[(left + right) / 2];
    do {
    for(;array[left]>pivot;left++) ; //for문 두곳의 >대소 비교 연산자를 바꾸면
    for(;array[right]<pivot;right--); //오름차순 내림차순으로 정렬가능하다.
    if (left <= right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
    left++;
    right--;
    }
    } while (left <= right);
    if (left < right)
    sort(array, left, right);
    if (right > left)
    sort(array, left, right);
    }
    public static void main(String[] args) {
    Integer[] array = { 65, 12, 1, 41, -5, -1 };
    QuickSort quick = new QuickSort();
    quick.sort(array, 0, array.length - 1);
    System.out.println(Arrays.toString(array));
    }
    }

  4. 최적화된 소스를 보고 많은 것을 배웠습니다. 감사합니다.

*

*