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

 

 

퀵 정렬은 분할 정복 알고리즘(Divide and Conquer)의 하나이면서, 매우 중요하게 다뤄지는 정렬 방법입니다.

 

 

 

퀵 정렬 알고리즘

퀵 정렬은 불안정 정렬(중복된 값이 입력 순서 혹은 정렬 전 순서와 동일하게 정렬되지 않음)에 속하며,
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬입니다.

 

알고리즘은 대략 다음과 같이 이루어집니다.

1.  리스트 안에 있는 하나의 요소를 선택합니다. 해당 요소는 Pivot 이라 부릅니다. (아무 원소나 선택해도 됩니다.)
2.  Pivot을 기준으로 Pivot보다 작은 원소는 모두 Pivot의 왼쪽으로, 큰 원소들은 모두 Pivot의 오른쪽으로 옮깁니다.(Divide)
3.  Pivot을 제외한 왼쪽과 오른쪽 부분의 리스트에 대해 다시 1,2 의 과정을 반복합니다. (Conquer)
4.  위의 과정을 부분 리스트들이 더 이상 분할이 불가능할 때까지(크기가, 0 또는 1이 될 때까지) 반복합니다
5.  정렬된 부분 리스트들을 하나의 배열로 합칩니다. (Combine)

 

 

 

 

 

 

 

 

퀵 정렬의 과정 살펴보기

주어진 배열에 대하여 Pivot을 설정합니다

저는 첫번째 원소를 Pivot으로 설정하겠습니다.

(Pivot을 첫번째 원소로 정하지 않았다면, 첫번째 원소와 Pivot의 값을 교체해주어 Pivot을 배열의 첫 위치로 옮겨줍니다.)

 

주어진 배열은 다음과 같습니다.

 

 

 

 

 

 

 

두 변수(toRight, toLeft)를 설정합니다.

toRight : 배열의 처음에서 시작하여 배열의 끝까지 오른쪽으로 움직이는 변수입니다.

toLeft : 배열의 끝에서 시작하여 배열의 처음까지 왼쪽으로 움직이는 변수입니다.

 

 

 

 

 

 

 

 

toRight 부터 움직이기 시작합니다.

toRight는 pivot 값보다 큰 값을 찾기 전까지 계속 오른쪽으로 이동합니다.

큰 값을 찾았다면 이동을 멈춥니다.

첫 이동부터 큰 값을 만나서 이동을 바로 멈추었습니다.

 

 

 

toRight의 움직임이 끝났다면 toLeft를 움직입니다.

toLeft는 pivot 값보다 작거나 같은 값을 찾기 전까지 계속 왼쪽으로 이동합니다.

작거나 같은 값을 찾았다면 이동을 멈춥니다.

 

 

 

 

 

toRight와 toLeft의 이동이 끝났다면 다음 과정을 수행합니다.


toRight와 toLeft를 비교합니다.

1. toRight <  toLeft : 두 값을 교환한 후 toRight와 toLeft를 이동시키는 과정을 반복합니다.

2. toRight > toLeft  : 두 값을 교환하지 않고 반복을 빠져나옵니다. 이후 추가적인 작업을 진행합니다.

3. toRight == toLeft : 발생하지 않습니다.

추가적인 작업은 이후 다시 설명하겠습니다.

 

 

위의 예시에서는 toRight가 toLeft보다 작으므로 두 값을 교환합니다.

 

toRight가 더 작으므로 두 위치를 교환합니다.

이후 다시 toRight와 toLeft를 옮겨주는 작업을 반복합니다.

 

 

 

 

 

 

toRight를 옮겨줍니다.

 

 

 

 

 

 

 

 

toLeft를 옮겨줍니다.

 

 

toRight와 toLeft의 이동이 끝났다면 다음 과정을 수행합니다.

toRight와 toLeft를 비교합니다.

위의 경우에는 toRight가 toLeft보다 큽니다.

 

toRight가 toLeft보다 큰 경우  : 두 값을 교환하지 않고 반복을 빠져나옵니다. 이후 추가적인 작업을 진행합니다.

 

 

 

추가적인 작업은 다음과 같습니다.

Pivot의 값과 toLeft를 교체해줍니다.
(Pivot은 항상 배열의 첫 원소가 되어야 하므로, 배열의 첫 원소와 바꾸어 주는것과 동일합니다.)

이후 toLeft의 인덱스를 기준으로 배열이 두 부분으로 나뉩니다.

두 부분으로 나뉜 배열에 대하여 다시 각각 정렬을 수행합니다.

 

 

 

 

 

 

 

이제부터 설명은 생략하고 과정을 나열하도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

알고리즘

배열이 주어지면 재귀적으로 QuickSort를 진행합니다.

QuickSort는 배열과 배열의 시작 인덱스, 끝 인덱스를 매개변수로 받습니다.

배열의 시작 인덱스가 끝 인덱스보다 같거나 크다면 작업을 수행하지 않고 return합니다.

그렇지 않은 경우 다음을 반복합니다.

주어진 배열에 대해 Partition 작업을 진행합니다.

Partition은 배열과 시작 인덱스, 끝 인덱스를 입력받아 배열을 두 부분으로 나누는 함수입니다.
입력받은 배열을 두 부분으로 나눈 후, 나누어진 기준이 되는 값(Pivot)의 인덱스를 반환합니다.

반환받은 인덱스를 기준으로
배열의 시작 ~ 반환 인덱스 -1,
반환 인덱스 + 1 ~ 배열의 끝
각각 범위로 하여 재귀적으로 QuickSort를 호출합니다.

 

즉 다음과 같습니다.

public void quickSort(int[] arr, int left, int right) {
   if(left >= right) return;

   int mid = partition(arr, left, right);
   quickSort(arr ,left, mid-1);
   quickSort(arr ,mid+1, right);

}

 

 

 

 

Partition 알고리즘

그림으로 살펴보았던 과정이며, 다음과 같습니다.

1. 배열의 첫 원소를 Pivot으로 지정합니다.

2. toRight, toLeft를 지정합니다.

3. toRight부터 이동을 수행합니다.

toRight는 pivot 값보다 큰 값을 찾기 전까지 계속 오른쪽으로 이동합니다.
큰 값을 찾거나 배열의 끝에 도착했다면 이동을 멈춥니다.

toLeft는 pivot 값보다 작거나 같은 값을 찾기 전까지 계속 왼쪽으로 이동합니다.
작거나 같은 값을 찾거나 배열의 끝에 도착했다면 이동을 멈춥니다.



4. 이동을 멈추었다면 toRight와 toLeft를 비교합니다. 

toRight < toLeft인 경우 : toRight와 toLeft의 값을 교체한 후 다시 이동을 시작합니다.

toRight > toLeft인 경우 : 반복을 종료한 뒤 pivot과 toLeft를 교체합니다. 이후 toLeft를 반환합니다

 

즉 다음과 같습니다.

public int partition(int[] arr, int left, int right) {

   
   
   int pivot = arr[left]; //1. 배열의 첫 원소를 Pivot으로 지정합니다.

   int toRight = left; //2. toRight, toLeft를 지정합니다.
   int toLeft = right;


   while (toRight < toLeft) {//4. toRight > toLeft인 경우 : 반복을 종료한 뒤 pivot과 toLeft를 교체합니다. 이후 toLeft를 반환합니다


      /**
       * 3. toRight는 pivot 값보다 큰 값을 찾기 전까지 계속 오른쪽으로 이동합니다.
       * 큰 값을 찾거나 배열의 끝에 도착했다면 이동을 멈춥니다.
       */
      while ( toRight <= right && arr[toRight] <= pivot ){
         toRight ++;
      }



      /**
       * 3. toLeft는 pivot 값보다 작거나 같은 값을 찾기 전까지 계속 왼쪽으로 이동합니다.
       * 작거나 같은 값을 찾거나 배열의 끝에 도착했다면 이동을 멈춥니다.
       * pivot이 left 이므로 toLeft >= left 조건은 필요 없습니다
       */
      while (arr[toLeft] > pivot ){
         toLeft--;
      }



      if(toRight < toLeft){//4. 이동을 멈추었다면 toRight와 toLeft를 비교합니다.
         swap(arr, toRight, toLeft);// toRight < toLeft인 경우 : toRight와 toLeft의 값을 교체한 후 다시 이동을 시작합니다.
      }

      
   }

   // 4. toRight > toLeft인 경우 : 반복을 종료한 뒤 pivot과 toLeft를 교체합니다. 
   swap(arr, left, toLeft);

   //이후 toLeft를 반환합니다
   return toLeft;
}

 

 

 

 

 

 

 

 

자바로 구현한 전체 코드

public void quickSort(int[] arr) {
   quickSort(arr, 0, arr.length - 1);
}


public void quickSort(int[] arr, int left, int right) {
   if(left >= right) return;

   int mid = partition(arr, left, right);
   quickSort(arr ,left, mid-1);
   quickSort(arr ,mid+1, right);

}



public int partition(int[] arr, int left, int right) {



   int pivot = arr[left]; //1. 배열의 첫 원소를 Pivot으로 지정합니다.

   int toRight = left; //2. toRight, toLeft를 지정합니다.
   int toLeft = right;


   while (toRight < toLeft) {//4. toRight > toLeft인 경우 : 반복을 종료한 뒤 pivot과 toLeft를 교체합니다. 이후 toLeft를 반환합니다


      /**
       * 3. toRight는 pivot 값보다 큰 값을 찾기 전까지 계속 오른쪽으로 이동합니다.
       * 큰 값을 찾거나 배열의 끝에 도착했다면 이동을 멈춥니다.
       */
      while ( toRight <= right && arr[toRight] <= pivot ){
         toRight ++;
      }



      /**
       * 3. toLeft는 pivot 값보다 작거나 같은 값을 찾기 전까지 계속 왼쪽으로 이동합니다.
       * 작거나 같은 값을 찾거나 배열의 끝에 도착했다면 이동을 멈춥니다.
       */
      while ( toLeft >= left && arr[toLeft] > pivot ){
         toLeft--;
      }



      if(toRight < toLeft){//4. 이동을 멈추었다면 toRight와 toLeft를 비교합니다.
         swap(arr, toRight, toLeft);// toRight < toLeft인 경우 : toRight와 toLeft의 값을 교체한 후 다시 이동을 시작합니다.
      }


   }

   // 4. toRight > toLeft인 경우 : 반복을 종료한 뒤 pivot과 toLeft를 교체합니다.
   swap(arr, left, toLeft);

   //이후 toLeft를 반환합니다
   return toLeft;
}


private void swap(int[] arr, int left, int toLeft) {
   int temp = arr[left];
   arr[left] = arr[toLeft];
   arr[toLeft] = temp;
}

 

 

 

 

 

 

 

---

 

 

 

 

 

 

퀵 정렬 알고리즘의 특징

퀵 정렬 알고리즘을 속도가 매우 빠릅니다.

퀵 정렬의 평균 시간 복잡도는 O(nlog n)이지만, 이와 같은 시간 복잡도를 가지는 다른 정렬 알고리즘들보다도 빠릅니다.

 

그러나 이미 정렬된 리스트에 대해서는 최악의 시간복잡도를 가집니다.

 

 

 

 

 

 

다른 정렬 알고리즘과의 시간복잡도 비교

	최선의 경우	평균적인 경우	최악의 경우
선택정렬	$$O(n^{2})$$	$$O(n^{2})$$	$$O(n^{2})$$
버블정렬	$$O(n^{2})$$	$$O(n^{2})$$	$$O(n^{2})$$
삽입정렬	$$O(n)$$	$$O(n^{2})$$	$$O(n^{2})$$
퀵 정렬	$$O(n \; log(n))$$	$$O(n \; log(n))$$	$$O(n^{2})$$
힙 정렬	$$O(n \; log(n))$$	$$O(n \; log(n))$$	$$O(n \; log(n))$$
병합정렬	$$O(n \; log(n))$$	$$O(n \; log(n))$$	$$O(n \; log(n))$$

 

 

 

 

 

 

 

병합 정렬(Merge Sort)과의 차이점

병합 정렬(혹은 합병 정렬)에서는, 리스트를 균등하게 분할하여 정렬을 수행하지만, 퀵 정렬에서는 리스트가 균등하게 나누어지지 않습니다.