자바로 구현한 퀵 소트(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로 작성하였습니다.
import java.util.*;
public class Main {
public static void quick_sort (ArrayList S) {
if (S.size() < 2) return; // Nothing needs to be done if S has zero or one element)
// Divide: If S has at least two elements, select a specific element x from S, which is called the pivot.
ArrayList<Integer> L = new ArrayList<Integer>(); // L, storing the elements in S less than pivot
ArrayList<Integer> E = new ArrayList<Integer>(); // E, storing the elements in S equal to pivot
ArrayList<Integer> G = new ArrayList<Integer>(); // G, storing the elements in S greater than pivot
int pivot = (int)S.get(S.size() - 1);
E.add(pivot);
S.remove(S.size() - 1);
while (S.size() > 0) {
if ((int)S.get(0) < pivot) {
L.add((int)S.get(0));
} else if ((int)S.get(0) == pivot) {
E.add((int)S.get(0));
} else {
G.add((int)S.get(0));
}
S.remove(0);
}
// Divide result
System.out.print("L = ");
print_ar(L);
System.out.print("E = ");
print_ar(E);
System.out.print("G = ");
print_ar(G);
System.out.println();
// Conquer: Recursively sort sequences L and G.
quick_sort(L);
quick_sort(G);
// 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.
for (int i = 0; i < L.size(); i++) {
S.add((int)L.get(i));
}
for (int i = 0; i < E.size(); i++) {
S.add((int)E.get(i));
}
for (int i = 0; i < G.size(); i++) {
S.add((int)G.get(i));
}
// Combine S result
System.out.print("S = ");
print_ar(S);
System.out.println();
}
public static void print_ar(ArrayList S) {
for(int i = 0; i < S.size(); i++) {
System.out.print(S.get(i) + " ");
}
System.out.println();
}
public static void main (String[] args){
int[] S_temp = {85, 24, 63, 45, 17, 31, 96, 50};
ArrayList<Integer> S = new ArrayList<Integer>();
for(int i = 0; i < S_temp.length; i++) {
S.add(S_temp[i]);
}
System.out.print("ArrayList before quick-sort: ");
print_ar(S);
quick_sort(S);
System.out.print("ArrayList after quick-sort: ");
print_ar(S);
} // main
}
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