[알고리즘] 정렬 알고리즘 - 퀵 정렬(QuickSort) 기본 알고리즘

 퀵 정렬

퀵 정렬(quicksort)은 분할 정복(divide and conquer) 기법을 사용한 정렬 방법의 하나

 

퀵 정렬의 단계

1. 배열 a[1:r]에서 가장 오른쪽에 있는 원소를 피봇(pivot)으로 선정한다.

   피봇은 분할 원소(partitioning element)라고도 부른다.

2. 이 피봇을 기준으로 a[]의 원소들은 두 개의 파티션(partition)으로 분할는데,

   분할되는 파티션은 아래의 성질을 만족해야 한다.

    (1) 분할 후 피봇은 a[i]에 들어가게 되는데, 이곳은 정렬 후 피봇이 들어가는 정확한 위치가 된다.

    (2) 왼쪽 파티션에 있는 원소 a[1], ... , a[i-1] 중 피봇보다 큰 원소는 없다.

    (3) 으론쪽 파티션에 있는 원소 a[i+1], ... , a[r] 중 피봇보다 작은 원소는 없다.

 

퀵 정렬은 왼쪽 파티션과 오른쪽 파티션에 대해 다시 QuickSort()를 순환적으로 적용한다.

이 순환 반복은 각 파티션이 하나의 원소 이하로 될 때까지 계속된다.

순환 실행이 끝나면 결국 원래의 배열 a[]에 있는 모든 원소는 오름차순으로 정렬된다.

 

실행 시간은 입력자료의 순서에 민감

불안정적 알고리즘

제자리 정렬 알고리즘

 

 

 

퀵 정렬 알고리즘(Quicksort)

QuickSort(a[], l, r)      // 배열 a[]의 부분 배열 a[l:r]을 오름차순으로 정렬     if ( r > l ) then {         i <- partition(a[], l, r); // i는 파티션이 끝난 뒤에 사용된 피봇의 인덱스         QuickSort(a[], l, i-1);         QuickSort(a[], i+1, r);     }  end QuickSort()

QuickSort() 알고리즘은 주어진 배열 a[]를 두 개의 파티션으로 분할하기 위해,

서브 프로그램 partition()을 호출한다.

그 후, 다시 각 파티션을 정렬하기 위해 다시 QuickSort() 자신을 순환적으로 호출한다.

따라서 QuickSort() 알고리즘의 핵심은 partition()알고리즘이라고 할 수 있다.

 

분할 알고리즘(partitionsort)

partition(a[], l, r)     // 가장 오른쪽 원소 a[r]을 피봇으로 하여 a[]를 분할     v <- a[r]; // 가장 오른쪽 원소를 피봇으로 정함     i <- l-1;    // 왼쪽에서 오른쪽으로 움직이는 포인터     j <- r;       // 오른쪽에서 왼쪽으로 움직이는 포인터     for ( ; ; ) do {         do { i <- i+1; } while ( a[i] < v ); // 피봇 값보다 작으면 i 값 증가         do { j <- j-1; } while ( a[j] > v ); // 피봇 값보다 크면 j 값 감소         if ( i >= j ) then break;         temp <- a[i]; a[i] <- a[r]; a[r] <- temp;  // a[i]와 a[r] 교환, a[i]와 a[j] 교환         return i;  end partition()

이 알고리즘의 목적은 부분 배열 a[1:r]의 가장 오른쪽 원소 a[r]을 피봇 값으로 정하고,

왼쪽과 오른쪽 파티션으로 분할하는 것이다.

 

분할은 아래의 단계로 수행된다.

1. a[l:r]의 가장 오른쪽 값인 a[r]을 분할의 기준값인 피봇으로 정한다.

   이 피봇은 변수 v에 저장된다.

2. a[l]부터 시작하여 오른쪽으로 이동하며 피봇보다 큰 값을 가진 원소를 찾는다.

   이렇게 되면 i는 피봇보다 큰 값을 가진 원소의 인덱스를 가지고 있게 된다.

3. a[r-1]부터 시작하여 오른쪽으로 이동하며 피봇보다 큰 값을 가진 원소를 찾는다.

   이렇게 되면 j는 피봇보다 작은 값을 가진 원소의 인덱스를 가지고 있게 된다.

4. i가 j보다 커지면, 

   즉, 왼쪽과 오른쪽 포인터가 서로 교차하게 되면 for루프를 벗어나 단계 6으로 간다.

5. a[i]와 a[j]를 서로 교환하고 단계 2로 이동한다.

6. a[i]와 a[j]를 서로 교환한다.

   이렇게 되면 피봇 값은 정렬 후 들어가게 될 정확한 위치에 있게 된다.

7. i 값을 반환한다.

 

퀵 정렬의 최선의 경우 시간 복잡도는 O(N log N)

평균적인 경우 2N ln N

최악의 경우 O(N^2)