퀵 소트(quick sort)

 


1. 퀵 소트의 디자인 패턴

퀵 소트 역시 머지소트(링크:

2015/07/04 - [노트정리/알고리즘 놀이] - 자바로 구현한 머지소트(merge sort, 합병정렬), 자바 소스 코드.

)와 마찬가지로 divide-and-conquer에 따라 정렬 알고리즘을 구현할 수 있습니다. 다음 세 단계를 통해 divide-and-conquer 과정을 풀어가보겠습니다.

(1) divide: 정렬되지 않은 배열 S를 생각해봅시다. 이 배열이 최소 두 개 이상의 원소가 있다면(배열의 원소가 0 또는 1이면 이 과정은 필요없습니다.), 이 배열에서 특정한 원소 x를 정합니다. 그리고 이 xpivot이라고 합니다. 대부분 이 특정 원소는 가장 마지막 원소로 합니다. Pivot이 정해졌다면 다음의 새로운 세 배열에 S의 원소를 이동시킵니다.

(i) 배열 L: x보다 작은 값을 이동

(ii) 배열 E: x와 같은 값을 이동(만약 없다면 xE로 이동하게 됨)

(iii) 배열 G: x보다 큰 값을 이동

(2) conquer: 배열 LG에 관하여 재귀적으로 (1) divide를 반복합니다.

(3) combine: 다시 초기의 배열 SL, E, G의 배열의 모든 원소를 이 순서에 맞춰 이동시킵니다.


 

2. 퀵 소트의 동작 예시

배열 S = { 85, 24, 63, 45, 17, 31, 96, 50 } 을 퀵 소트하는 경우를 생각해봅시다.

1의 순서에 따라 divde-and-conquer 하면 그림 1과 같은 순서로 동작합니다.


      


그림 1. 퀵 소트 동작하는 과정

 


3. 퀵 소트 흐름도

퀵 소트의 divide 과정에 집중해서 흐름도를 그려보면 그림 2와 같습니다.



그림 2. 퀵 소트의 divide 단계 흐름도

 


4. 자바로 퀵 소트 구현

지난 머지 소트의 방법과 마찬가지로 재귀적 방법을 써서 퀵 소트를 자바로 구현해보았습니다. 흐름도에서는 배열을 생각해서 위와 같이 하였습니다. 그러나 재귀적인 과정에서 가변 배열이 필요하기 때문에 ArrayList로 작성하였습니다.

 

 

  1. package quick_sort;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.        
  6.         public static void quick_sort (ArrayList S) {
  7.                 if (S.size() < 2) return; // Nothing needs to be done if S has zero or one element)
  8.                
  9.                 // Divide: If S has at least two elements, select a specific element x from S, which is called the pivot.
  10.                 ArrayList<Integer> L = new ArrayList<Integer>(); // L, storing the elements in S less than pivot
  11.                 ArrayList<Integer> E = new ArrayList<Integer>(); // E, storing the elements in S equal to pivot
  12.                 ArrayList<Integer> G = new ArrayList<Integer>(); // G, storing the elements in S greater than pivot
  13.                 int pivot = (int)S.get(S.size() - 1);
  14.                 E.add(pivot);
  15.                 S.remove(S.size() - 1);
  16.                 while (S.size() > 0) {
  17.                         if ((int)S.get(0) < pivot) {
  18.                                 L.add((int)S.get(0));
  19.                         } else if ((int)S.get(0) == pivot) {
  20.                                 E.add((int)S.get(0));
  21.                         } else {
  22.                                 G.add((int)S.get(0));
  23.                         }
  24.                         S.remove(0);
  25.                 }
  26.                
  27.                 // Divide result
  28.                 System.out.print("L = ");
  29.                 print_ar(L);
  30.                 System.out.print("E = ");
  31.                 print_ar(E);
  32.                 System.out.print("G = ");
  33.                 print_ar(G);
  34.                 System.out.println();
  35.                
  36.                 // Conquer: Recursively sort sequences L and G.
  37.                 quick_sort(L);
  38.                 quick_sort(G);
  39.                
  40.                 // Combine: Put back the element into S in order by first inserting the elements of L, then those of E, and finally those of G.
  41.                 for (int i = 0; i < L.size(); i++) {
  42.                         S.add((int)L.get(i));
  43.                 }
  44.                 for (int i = 0; i < E.size(); i++) {
  45.                         S.add((int)E.get(i));
  46.                 }
  47.                 for (int i = 0; i < G.size(); i++) {
  48.                         S.add((int)G.get(i));
  49.                 }
  50.                
  51.                 // Combine S result
  52.                 System.out.print("S = ");
  53.                 print_ar(S);
  54.                 System.out.println();
  55.                
  56.         }
  57.        
  58.         public static void print_ar(ArrayList S) {
  59.                 for(int i = 0; i < S.size(); i++) {
  60.                         System.out.print(S.get(i) + " ");
  61.                 }
  62.                 System.out.println();
  63.         }
  64.        
  65.         public static void main (String[] args){
  66.                 int[] S_temp = {85, 24, 63, 45, 17, 31, 96, 50};
  67.                 ArrayList<Integer> S = new ArrayList<Integer>();
  68.                
  69.                 for(int i = 0; i < S_temp.length; i++) {
  70.                         S.add(S_temp[i]);
  71.                 }
  72.                
  73.                 System.out.print("ArrayList before quick-sort: ");
  74.                 print_ar(S);
  75.                 quick_sort(S);
  76.                 System.out.print("ArrayList after quick-sort: ");
  77.                 print_ar(S);
  78.         } // main
  79.        
  80. }

5. 자바로 구현한 퀵 소트 결과

퀵 소트를 구현한 결과는 그림 3과 같습니다.

ArrayList before quick-sort: 85 24 63 45 17 31 96 50

L = 24 45 17 31

E = 50

G = 85 63 96

 

L = 24 17

E = 31

G = 45

 

L =

E = 17

G = 24

 

S = 17 24

 

S = 17 24 31 45

 

L = 85 63

E = 96

G =

 

L =

E = 63

G = 85

 

S = 63 85

 

S = 63 85 96

 

S = 17 24 31 45 50 63 85 96

 

ArrayList after quick-sort: 17 24 31 45 50 63 85 96


참고한 책



Data Structures and Algorithms in Java. 2/E,

저자
Goodrich, Michael T. 지음
출판사
Wiley | 2000-08-01 출간
카테고리
과학/기술
책소개
Using the power of technology to go...
가격비교




Posted by 공돌이pooh
,