퀵 정렬(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)  (9) 2015.10.26
삽입 정렬(Insertion Sort)  (5) 2015.10.26
선택 정렬(Selection Sort)  (5) 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. 최적화된 소스를 보고 많은 것을 배웠습니다. 감사합니다.

  5. 스킨깔끔하네요 사신건가요?

  6. 비밀댓글입니다

  7. 지금까지 본 소스중에 제일 깔끔하고 이해하기 쉽네요.. 잘봤습니다.

  8. 다른 블로그에서 봐왔던 유사 퀵정렬이랑은 다르게 성능이 정말 좋네여.. ㄷㄷ
    정말 대단합니다..ㄷㄷ

  9. 선생님 안녕하세요. 퀵 정렬 공부 중에 좋은 자료 보고 갑니다!

    한 가지 궁금한 점이 있는데 아래 코드에서 스왑 하기전에 left <= right 비교를 하는 이유가 무엇인지 좀 헷갈립니다 ..ㅠㅠ

    if(left <= right){
    int temp = data[left];
    data[left] = data[right];
    data[right] = temp;
    left++;
    right--;
    }

*

*