검색트리 - 이진탐색트리

이전에 퀵 정렬에 사용했던 전반, 후반부를 나눠주는 분할방법을 선택 알고리즘에서도 똑같이 사용하며, 전체원소중 몇 번째로 작은지에 해당하는 원소를 탐색하며 찾았다.

이번에도 검색 알고리즘과 비슷한 목적인 원하는 원소를 찾아내주는 검색 알고리즘에 대해 소개하겠다. 

우리가 만약 원하는 원소를 찾고자할 때, 전체원소가 차례로 나열(정렬)이 되어있다면, 다음과 같이 차례대로 원소를 찾을 것이다.

ex) 순차적 탐색  

 1) 찾을 원소 : 4

 2) 전체원소 1~100에서 그 중 55를 찾고싶다면? 

: 위와 같이 54회의 비교를 통해서 찾을 수 있다. 

  만약에 100의 값을 찾고자 한다면, 99번을 탐색해야하는 과정을 알 수 있을것이다. 

이러한 순차적인 탐색은 전체원소의 갯수가 많을경우, 비효율적인 결과를 알 수 있다. 

그렇다면, 어떻게하면 이러한 탐색횟수를 줄일 수 있을까? 바로 우리가 지금 알아볼 이진탐색 트리를 알아본다면 쉽게 해결할 수 있다. 

먼저, 이진탐색이란?

이진탐색은 전체원소의 중간번째의 원소를 지목해서 찾고자 하는 원소보다 작으면 왼쪽으로 크면 오른쪽으로 탐색이 이루어진다. 쉽게 이해하기위해 다음 이진탐색 그림을 살펴보자.

ex) 이진탐색

 A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 11 }

 - 찾을 원소 : 8

과정1) 기준원소: 6

: 찾을 원소 8이 비교할 원소 6보다 큰 7 ~ 11사이에 있다는 것을 확인할 수 있다.

과정2) 기준원소 : 9

: 찾을 원소 8이 비교할 원소 9보다 작은 7 ~ 8 사이에 있다는 것을 확인할 수 있다.

과정3, 4) 기준원소 : 7

: 찾을 원소 8이 비교할 원소 7보다 큰 마지막 남은원소 8이라는 것을 확인할 수 있다.

  만약에 여기서 이진탐색이 아닌 순차적인 탐색을 이용했다면, 7회의 과정을 거쳐 탐색을

  완료할 수 있었을 것이다. 그리고 원소들을 보면서 "이진탐색은 이미 정렬이 되어있는 상태에서만 사용할 수 있구나" 라고 생각하며 주의하며 이진탐색트리를 살펴보자.

이진탐색트리는 위에서 살펴본 이진탐색을 트리에 얹혀 놓은거라고 생각하면 된다.이전에 힙 정렬에서도 트리에 대해 알아보았는데, 한번 더 살펴보자.

트리는 루트노드(최상위 노드) 부터 최하위의 자식노드(단말노드)까지 (나무의 뿌리처럼 펼쳐진 모양)노드들 간의 연결이 되어있다. 이 하나의 노드에는 (왼쪽자식이 연결될)Left, (오른쪽자식이 연결될)Right 그리고 자신의 (노드의 값)데이터로 다음과 같이 이루어져있다.

ex) 트리에서 사용하는 노드(Node)의 구조

값이 2인 노드

 그리고 이러한 노드들은 최대 두개의 자식들을 가질 수 있으며, 이진탐색트리에서의 노드들은 같은 값을 가질 수 없다. 또한 왼쪽의 자식은 현재 자신의 값보다 작은 값을 가질 수 있고 오른쪽의 자식은 자신보다 큰 값을 가진다. 

ex) 트리에서 사용하는 트리의 구조

 다시한번 더 이진탐색 트리에서의 노드들을 정의하면 다음과 같다.

 1) 노드들은 최대 2개의 자식을 가질 수 있다.

 2) 각각의 노드들의 값은 겹치면 안된다. (값이 같으면 X)

 3) 노드의 왼쪽자식은 자신보다 작은 값, 오른쪽자식은 자신보다 큰 값을 가져야 한다.

 4) 마지막으로 위에 그림에는 없지만, 단말노드(자식이없는, Leaf Node라고도 함)의
     왼쪽, 오른쪽자식은 모두 없으므로 NULL을 가리킨다.

이러한 3가지특성을 잘 지키면서 이진탐색트리의 생성, 삭제, 탐색을 살펴보자.

1) 이진탐색 트리의 탐색

1-1) 노드 14의 탐색

: 루트노드부터 Right한번 Left한번의 과정을 거쳐서 값이 14인 노드의 탐색완료


1-2) 노드 7의 탐색

: 노드 7을 탐색하는데 NULL값을 만나서 종료가 된다.

위의 탐색의 과정은 이진탐색트리에서 가장 중요한 역할을 한다. 또한 삭제와 삽입에서도 값을 찾는데 유용하게 이루어지는데, 만약에 탐색을하다가 NULL값을 만나게되면 종료가 된다.

2) 이진탐색 트리의 노드추가

원소 5, 3, 9, 4, 10, 7, 1 차례대로 삽입과정을 알아보자.

2-1) 노드 5 삽입 

: 최초의 삽입은 5이므로 Root노드가 된다.



2-2) 노드 3 삽입

: 5의 Left 자식은 없으므로 3은 5의 왼쪽자식이 된다.



2-3) 노드 9 삽입

: 9의 Right 자식은 없으므로 9는 5의 오른쪽자식이 된다.


2-4) 노드 4 삽입

: 3의 Right 자식은 없으므로 4는 3의 오른쪽자식이 된다.
  꽤나 복잡해보이지만, 단순한 NULL이 나올때까지 데이터를 삽입하기 위한 탐색이라고 생각하자


2-5) 노드 10 삽입

: 9의 Right 자식은 없으므로 10은 9의 오른쪽자식이 된다.



2-6) 노드 7 삽입

: 9의 Left 자식은 없으므로 7은 9의 왼쪽자식이 된다.


2-7) 노드 1 삽입

: 3의 Left 자식은 없으므로 1은 3의 왼쪽자식이 된다.


2-8) 원소 5, 3, 9, 4, 10, 7, 1 삽입완료.

: 자식이 없는 단말노드들은 NULL을 갖는다.


이제 이진탐색 트리의 삭제에 대하여 알아보자

3) 이진탐색 트리의 노드삭제

이진탐색 트리의 삭제에서는 단순히 노드를 제거하는것에만 신경쓰기보다는 해당 노드를 제거한 뒤에도 트리의 구조를 만족시키는지에 대하여 생각해 볼 필요가 있다. 이러한 이진탐색 트리에서의 삭제는 다음과 같이 세 가지 조건을 항상 염두 해 둔다.

1. 제거할 노드의 자식이 모두 없는 경우(단말노드일 경우)
2. 제거할 노드의 자식이 2개인 경우(자식이 둘 인경우)
3. 제거할 노드의 자식이 하나인 경우(자식은 Left 또는 Right에 위치할 경우)

이러한 이유를 지켜야 트리의 구조가 깨지지 않으므로 항상 유지할 필요가 있다는 것이다.
그림으로 살펴보자.


3-1) 제거할 노드의 자식이 모두 없는 경우(단말노드 일때)

: 제거할 노드가 단말노드일 경우, 단순히 노드만 제거해도 자식들이 없으므로 트리의 규칙이 깨지지 않는다.



3-2) 제거할 노드의 자식이 하나일 경우(자식은 Left, Right 관계없이 같음)

 - 원소 22제거

: 22를 제거함.
  하지만, 여기서 제거한 노드의 자식들과의 연결또한 끊어지므로, 이것을 유지해야하는 작업이 필요  하다.


 - 제거한 노드(22)의 자식들 유지

3-3) 제거할 노드의 자식이 모두 존재할 경우

 - 원소 20제거

: 자식이 모두 존재하는 경우, 제거할 노드의 오른쪽 자식에서 가장작은 노드의 값을 제거할 노드에다가 값을 복사해주는데, 그 이유는 제거할 노드의 자식들을 단순히 이어 붙일 수 가 없으며 또한 트리의 규칙을 지키는 복잡한 과정이 필요없이 나아가기에 적합하다.

하지만 여기서 오른쪽노드의 자식들 중 최소값을 붙여준 다음, 최소값의 노드는 제거된다. 왜냐? 같은 트리에 같은노드가 있을 수 없다. 그리고 최소값의 노드 또한 트리의 규칙에 맞게 제거가 되어야 한다.


 - 최소값 제거 후 자식들을 트리의 구조에 맞게 정리

이진탐색트리의 수행시간 

이진탐색트리의 수행시간은 "데이터의 분포에 따라서 달라진다" 라고 할 수 있다.
이해하기 힘들겠지만, 지금까지 위에서 살펴본 노드들이 어떠한 형태로 트리에 위치했는지 살펴보진 않았을 것이다. 데이터의 탐색을 하기 위해서는 항상 Root의 노드부터 차례로 크기 비교를통해서 탐색이 되었다. 이말은 트리의 노드들이 한쪽으로만 치우쳐져 있다면, 크기 비교하는것에 의미를 두지않고 한쪽으로만 탐색해야한다는 굉장히 비효율적인 탐색이 되는것이다.

그림으로 살펴보자.

- 트리의 노드들이 골고루 분포되어있는 경우

:위에서 살펴보듯이 트리에 데이터가 골고루 분포가 되어 있다면, 3회에 걸쳐 찾을 수 있다.
 이말은 다르게 말하면 이진탐색트리의 수행은 Theta(log n)의 시간이 소요된다.



- 트리의 노드들이 치우쳐져 있는 경우

: 이처럼 트리에서 한쪽으로만 치우쳐져있는 노드들의 구조는 최악의 경우라고 할 수 있다. 이처럼 최악의 경우에서는 전체노드들의 갯수, Theta( N )의 수행시간이 소요된다.

최종적으로 정리하면 다음과 같다.
- 최선의 탐색 수행시간 : Theta( n )
- 최악의 탐색 수행시간 : Theta( log n )
- 평균적인 탐색 수행시간 : Theta( log n) 



이진탐색 트리의 알고리즘은


- BinarySearchTree.h




- BinarySearchTree.c


- BinarySearchTreeMain.c



 ▶실행결과

선택 알고리즘

이전에 다음과 같은 정렬들에 대해 알아보았다.

1) 기초적인 정렬(삽입, 선택, 버블정렬)
2) 고급 정렬(병합, 퀵, 힙 정렬)
3) 특수 정렬(기수, 계수 정렬)

이 정렬들의 수행시간을 살펴보면,

최종적인 목표로 최악의 경우 또한 Theta(n)의 수행시간이 소요되는 계수정렬과 기수정렬까지 알아보았는데, 하지만 이 최악의 경우에서도 Theta(n)의 수행시간이 나오기까지 추가적인 메모리가 필요한 약간의 한계성이 있었다.

이러한 추가적인 메모리가 필요한 단점을 보완한 방법으로 선택알고리즘에 대해서 소개하겠다.

선택 알고리즘은 평균적으로 Theta(n)의 수행시간이 소요되며, 추가적인 메로리를 필요로 하지않는다. 그리고 정렬의 목적이 아닌 "어느 특정한 위치의 원소를 찾기 위한것인지"에 맞춘 알고리즘이다.
예를들어, 전체 원소  4, 3, 2, 8, 7중에서 n번째로 작은 값은 어느 원소인지 찾을 수 있으며, 몇 번째로 작은지 찾는 과정에서는 퀵 정렬에서 사용한 partition()을 사용을 통해서 약간의 정렬의 형태를 띄고있다.

선택 알고리즘의 과정은 퀵 정렬시 partition()을 사용하여 기준원소로 전반부와 후반부를 나누는 과정에서 전체원소 중 기준원소는 어느위치에 속하는지 알 수 있었다. 이러한 기준원소의 위치를 알 수 있다는 의미는 "그 값(기준원소)이 전체에서 몇 번째로 작은가 ?" 라는 말과 같은 의미라는 것을 눈치 챌 수있다. 정말로 partition()을 통해 해당원소가 전체에서 몇 번째로 작은지 알 수 있는지 살펴보자

선택 알고리즘 과정 

A = { 4, 3, 2, 8, 7 }에서 2번째로 작은 원소찾기.

 ▶ 과정 (1)

과정(1) partition

: 전반부 3개와 후반부 1개로 나누어졌으며 기준원소(7)보다 큰 값에 대해서는 
 졍렬의 형태를 띈다. 여기서 중요한 것은 배열 인덱스에 초점을 맞춰야 한다.
 전체 0~4의 인덱스 총 5개중에 3번째로 작은 원소의 인덱스값은 3-1인 2가 될 것이다.
 기준원소 7의 인덱스는 partition()수행을 한 결과 3이 되었다. 즉, 우리가 찾는 2보다는
 큰 값으로 기준원소보다 큰 값들에 대해 눈을 떼고 작은 값(전반부)들을 살펴보아야
 한다는 의미이다. 밑의 결과 그림을 보면 쉽게 이해 할 수 있다.

과정(1) selection

: 뒤의 원소 8은 기준원소에 해당하지 않으므로 제외 시켰으며 정렬이 된다.
  그리고 기준원소를 전반부 맨 끝으로 지정

 ▶ 과정 (2)

과정(2) partition

: 전반부 0개와 후반부2개로 나누어 졌으며, 3, 4번째 위치는 이전 과정을 통해서 기준원소  에서 제외된 것을 알 수 있으며 정렬이 된 모습을 띄고있다.

과정(2) selection

: 뒤의 원소 2는 기준원소에 해당하지 않으며, 가장 작은 맨 앞의 위치로 이동한다.
 즉, 전반부는 없으며 후반부를 호출하고 후반부의 맨 끝 4가 기준원소가 된다.


 ▶ 과정 (3)

과정(3) partition

: 후반부 0개와 전반부 1개로 나뉘었으며, 이 말은 찾고자하는 기준원소를 찾았다는 의미라  라고 생각해도 된다. 찾고자 하는 원소는 전반부에 있거나 또는 기준원소가 된다.

과정(3) selection

: 찾기 완료. 후반, 전반이 0이 되거나 기준원소에 해당하지 않을 경우, 비교할 이유가 없으  므로 제외시켰는데 이때 제외시킨 원소들은 정렬이 된 모습을 띈다. 
 (상황에 따라서 정렬이 되지는 않을 경우도 있다는 점을 유의하기)


선택 알고리즘의 수행시간을 살펴보자
1) partition()을 하는 과정에 있어서 원하는 원소를 찾는 것은 Theta(n)의 수행시간이 소요된다. 기준원소와 전체를 비교를 통해서 원하는 값을 찾고 또 기준원소의 자리를 정할 수 있게 된다. 
: 전체와 기준원소의 비교를 하는 시간은 평균 Theta(n)이 소요됨.

2) selection()을 하는 과정은 전체크기에 비례한다. partition()을 통해 기준원소를 알맞은 위치를 찾아서 전반부와 후반부를 각각 호출하는 시간이 소요된다.
: 전체를 전반과 후반부로 나누므로 이들을 호출한느 시간 n이 소요된다. (n은 상수)

위의 1, 2 두 가지 경우를 살펴보면, 계수정렬와 기수정렬때 사용하는 추가적인 메모리 사용없이 평균적인 Theta(n)인 선형시간이 소요될 수 있다. 
하지만, partition()의 경우 퀵 정렬 에서도 살펴 보았듯이 최악의 경우가 존재한다. 바로 전반이 0이되거나 혹은 후반부가 0이되는 기준원소가 한쪽으로만 치우치게 되는경우이다. 
그러므로 다음과 같이 정리할 수 있다.
- 최선의 경우 : Theta(n)
- 평균의 경우 : Theta(n)
- 최악의 경우 : theta(n의 제곱)



선택 알고리즘을 살펴보자



▶실행결과

특수 정렬 알고리즘 (2) - 계수정렬

이전과는 다른방식의 정렬인 기수정렬에 대해 살펴보았는데, 이와 비슷한 방식인 계수정렬에 대해서 소개하도록 하겠다. 

계수정렬은 기수정렬처럼 원소들끼리의 크기비교가 아닌 어느 절대적인 값들과 비교를 통해서 상당히 빠른속도로 정렬을 할 수 있다. 어떠한 절대적인 값이 있을지 생각해보면, 우리가 정렬을 프로그래밍 할때, 대부분이 배열을 사용해서 정렬되지 않은 원소들을 넣은 상태에서 진행을 했을텐데, 이때의 배열 인덱스 값을 이용한 방식이다. 

계수정렬의 방식은 정렬되지 않는 원소들을 새로운 배열에다가 저장을 할 것인데, 이 새로운 배열의 크기는 전체원소들 중 가장 큰 원소를 배열의 크기로 놓으며, 배열 인덱스에 해당 원소들이 몇 개 있는지 넣어주면 된다. 예를들어 " A = { 2, 5, 4, 2, 4, 5 } "라는 정렬되지 않은 원소들이 있다면 가장 큰 원소 5만큼 새로운 배열 " C[5]; "를 만든다. 그런다음 배열 A의 전체 값들을 새로 만든 배열 C[5]에 다음과 같이 넣어주면 된다. 

     " 배열 인덱스에 해당하는 각 숫자들이 몇 개씩 있는지 세어주면 된다 " 

ex) 2, 5, 4, 2, 4, 5의 값들이 있을경우,

C[0] = 0,   C[1] = 0,  C[2] = 2,   C[3] = 0 
 C[4] = 2,             C[5] = 2

그리고 정렬 될 값들을 저장할 " B[6] " 라는 배열에 차례로 저장하면 된다.  총 3개의 메모리가 필요하며, 중복되는 값들을 정렬 할 때는 편리하겠지만 만약에 원소들이 1, 3, 5000, 1이런식으로 존재한다면, 가장 큰 원소 5000을 C[5000]과 같이 만들어야 하므로 매우 비효율적으로 정렬 될 수도 있다. 이것은 "우리가 정렬을 하기 전 먼저 원소들의 크기가 어떠한지 고려해야 한다" 라고 말하는 의미다. 

위의 내용을 간략히 정리하면,
1.  A배열 전체에서 가장 큰 원소만큼 배열 C를 만들기
2.  A배열 원소 하나씩 C배열의 인덱스에 해당하는 것끼리 넣어주기
3.  각 원소들이 저장된 C배열을 B[N]에 하나씩 정렬시키기


ex) 계수정렬 과정
---------------------------------------------------------------------------

계수정렬 과정 ( 1 ) 

계수정렬 과정 ( 2 ) 

계수정렬 과정 ( 3 ) 

계수정렬 과정 ( 4 ) 

계수정렬 과정 ( 5 ) 

계수정렬 과정 ( 6 ) 

: 정렬이 완료 되었다. 

위에 설명한 배열C 또한 그림에 표현하면 더 좋아겠지만, C는 알고리즘을 구현 시 사용이 되며, 위에서 설명한 계수정렬을 알고리즘 위주로 쓰다보니, 계수정렬을 조금 흐릿하게 설명하여 그림으로 보다 명확한 계수정렬을 표현하고 싶었다. 

---------------------------------------------------------------------------



계수정렬의 수행시간은 다음 2가지를 고려하면 된다.
(1) 전체 A[N]의 원소들을 C[ 전체 N개중 가장 큰 원소 ]에 해당하는 원소들의 갯수만큼 정의
: (1)의 수행시간은 가장 큰 원소만큼의 수행시간이 필요하다.  ( 수행시간 C : 상수 )

(2) B[0], B[1] ... B[N]에 차례로 옮겨 정렬시키면 된다.    
: (2)의 수행시간은 전체 갯수인 N만큼의 수행시간이 걸린다. C[A[i]]에 해당하는 값들을 B[N]만큼 차례로 옮기면 되므로  ( 수행시간 N : 전체원소의 갯수 )

(1), (2)를 정리하면 계수정렬의 수행시간은 Theta(N)의 특징을 보인다. 그리고 위에서도 말했듯이 메모리를 3개나 준비해야 하는것과 비교적 큰 숫자가 등장하면 C의 메모리가 꽤 커진다는 문제가 있지만, 장점 측면에서, 예를 들어 5이하의 자연수 100개가 모여있다고 가정했을 경우, 어느 정렬방식과는 비교할 수 없는 빠른 수행을 자랑한다.



계수정렬의 알고리즘




▶ 실행결과

특수 정렬 알고리즘 (1) - 기수정렬

이전까지 우리는 Theta(n의 제곱), Theta(nlogn)의 수행시간이 소요되는 정렬들을 살펴보았는데, 이 정렬들은 (최선/최악)경우에 따라 각각 다른 수행시간이 소요되는 경우도 있었으며, 각 2개의 원소들을 기준으로만 정렬을 했었었다.

그렇다면, 최악의 경우에,

         "Theta(n의 제곱), Theta(nlogn)의 수행시간보다는 더 빠를 수는 없는가?"

이번장에서 알아 볼 기수정렬은 이 최선, 최악의 경우에 관계없는 수행시간과 같은 크기일 경우 자리를 바꾸지않는 안정성이 있는 특징과 "두개의 원소를 비교한다" 보다는 "절대적인 원소를 기준으로 값을 비교한다" 라고 할 수 있다. 이 말은,  최악의 경우에도 최선의 결과와 같은 시간이 소요된다는 것을 의미한다.

그렇다면, 이 기수정렬에 대해 알아보자.

기수정렬은 각 자릿수와 원소의 갯수들만이 수행시간에 영향을 준다.

입력이 모두 k이하의 자릿수인 자연수만을 가진 경우에 사용이 된다.(k는 상수)

각 자릿수만 비교하여 정렬을 원소의 갯수만큼 진행하면 되는데, 위에도 말했듯이 안정적인 정렬을 사용해서 이루어진다. 그림으로 살펴보면 조금 더 쉽게이해가 될 것이다.

ex) 4개의 자릿수를 갖는 1467, 2223, 3014, 1523의 기수정렬 과정

: 위의 과정에서 안정성 유지하여 정렬한 것

▶ 첫째, 둘째 자릿수 비교 시 2223, 1523 

▶ 넷째 자릿수 비교 시 1467, 1523

기수정렬의 수행시간은 어느 경우에나 Theta(n)의 수행시간이 소요되어야 한다. 어떻게 이러한 수행시간이 가능한가? 

각 자릿수의 범위는 0~9의 사이에 절대적으로 위치할 수 밖에없다. 1000의 자릿수까지 있는 5개의 값이 있다면, 각 자릿수를 0부터 9까지의 숫자 비교를 4번만 하면되지 않겠는가? 물론 안정성 유지를 해야하는 것도 잊지말자.

기수정렬의 알고리즘을 만드는2가지 방법을 살펴보자.

1) 큐를 이용한 방법
  - enqueue() : 큐 삽입 
  - dequeue() : 큐 제거
  - QueueInit() : 큐 초기화
  - QIsEmpty() : 큐 비어있는지 확인.

▶실행결과

2) 2차원 배열을 이용한 방법

▶실행결과

고급정렬 알고리즘(4) - 병합, 힙, 퀵 정렬 비교분석

기초적인 정렬(선택, 버블, 삽입)외에 고급정렬인 병합, 힙, 퀵 정렬에 대해서 알아보았다.

이제 이 3개의 고급정렬의 각 수행시간을 최선, 평균, 최악의 경우에 따라서 어떠한 특징이 있는지 살펴보자.

먼저, 3가지 정렬의 특징은

1) 병합정렬 : 분할, 합병인 분할정복을 이용한 정렬방식

▶ 주어진 값에 상관없이 분할하고 합병하므로 항상 일정한 수행시간이 소요된다.

2) 힙 정렬 : 히프 구조를 이용한 정렬방식

▶ (1)히프를 만든 뒤, (2)루트노드인 제일 작은값을 맨 뒤의 값과 교환을 하는 반복을 통해서 정렬이 되어간다. 여기서 "이미 히프구조로 되어있다면 최선의 경우가 아닐까?" 라고 생각할 수 있지만, (2)정렬과정(루트 노드와 맨 뒤의 값과 교환하는 것)에서 히프구조가 깨져서 재귀를 통해 히프를 재구성하는 과정이 전체 수행시간에 더 큰 부분을 차지하므로 (1)처음에 히프를 만들어 주는 과정은 수행시간에 크게 영향을 주지는 않는다. 그러므로 항상 일정한 수행시간이 소요되는 것을 알 수 있다.

3) 퀵 정렬 : 맨 끝의 값을 기준원소로 전체와의 비교를 반복을 통한 정렬방식

▶ 기준원소를 잡고 전체원소와 크기비교를 통해 전반, 후반부로 나누고 또 다시 기준원소를 각 부의 끝을 기준원소로 각 부의 전체와 크기비교를 통해 전반, 후반으로 나누는 과정으 을 반복해서 정렬이 된다. 이 과정에서 두 가지 경우가 수행시간에 영향을 줄 수 있다.

 (1) 맨 끝의 기준원소가 가장 큰 값일 경우 : 후반부는 하나도 존재하지 않으며 단 하나의 원소, 기준원소만 정렬이 된 상태이다. 

 (2) 맨 끝의 기준원소가 가장 작은 값일 경우 : 전반부는 하나도 없으며 단 하나의 원소, 기

준원소만 정렬이 된 상태이다.  

ex) 5, 4, 2, 1, 7의 경우를 살펴보자 

1) 기준원소 7일 때 :

7 : 가장 큰 수

2) 기준원소 1일 때 :

1 : 가장 작은 수

3) 기준원소 5일 때 :

5 : 가장 큰 수

4) 기준원소 2일 때 :

2 : 가장 작은 수

5) 기준원소 4일 때 : 

전반/후반 부의 갯수 : 0

      
6) 정렬 완료. 

정렬완료.

이처럼 각 기준 원소들이 가장 작은 값 혹은 가장 큰 값이 될 경우 변화가 거의 없으며, 전반/후반 부 또한 나눌 수 없다. 이러면 퀵 정렬의 특징이 거의 사라졌다 봐도 무방하다.

즉, 퀵 정렬의 최악의 경우는 기준원소가 가장 큰값 혹은 가장 작은 값이 되는 경우이다.



고급정렬 수행시간은, 다음과 같이 정리 할 수 있다.