자바로 구현한 퀵 소트(quick sort), 자바 소스 코드

퀵 소트(quick sort)

 

1. 퀵 소트의 디자인 패턴

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

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

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

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

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

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

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

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

(3) combine: 다시 초기의 배열 S에 L, 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...

---