[알고리즘-이론] 퀵 정렬 (Quick Sort)

---

퀵 소트(Quick Sort)란?

퀵 정렬은 평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘이다.

 

바로 예로 설명을 하자면

 

정렬할 배열 A={31,11,2,6,9} 가 주어진다.

 

이 때 기준 원소를 중심으로 그 값보다 큰 원소는 뒤에, 작은 원소는 앞에 배치를 하는 식으로 정렬이 이루어진다.

• 기준 원소를 잡는다.

• 기준 원소의 왼쪽은 기준 원소보다 작은 값, 오른쪽은 기준 원소보다 큰 값.

• 왼쪽에 대해서도 재귀호출을 실행한다. 오른쪽에 대해서도 재귀호출을 실행한다.

1라운드

기준 원소를 잡는다 -> 기준원소: 9 -> 기준원소를 기준으로 A[0]부터 값을 비교하며 재배치 한다. ->

A={2, 6, 9, 31, 11};

2라운드

기준 원소를 잡는다 -> 기준원소: 11 -> 기준원소를 기준으로 A[0]부터 값을 비교하며 재배치 한다. ->

A={2, 6, 9, 11, 31};

이 과정을 반복하고 기준 원소가 배열의 원소를 한번씩 훑고 지나가면 끝난다.

quickSort(A[], p, r){
    if(p<r) then {
        q <- partition(A, p, r);
        quickSort(A,p,q-1);
        quickSort(A,q+1,r);
    }
}


partition(A[], p, r){
    x <- A[r];
    i <- p - 1
       for j <- p to r-1
        if(A[j] <= x) then A[++i] <-> A[j];

    A[i+1] <-> A[r];
    return i+1;
}

---

퀵 소트(Quick Sort)의 시간 복잡도

퀵 소트는 보다싶이 재귀호출적 특성( O(log n))을 갖고있다.

---

퀵 소트(Quick Sort)의 특징

장점

• 속도가 빠르다

• 추가 메모리가 필요로 하지 않는다.

단점

• 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

---

퀵 소트(Quick Sort의 자바 코드)