| ☆ 공부한 내용을 정리한 내용입니다. 잘못된 부분이 있으면 고정 위해 댓글 부탁드립니다. |
■ 퀵 정렬
원리 ) 중심점(Pivot Point)을 임의로 고른 후
이 중심점보다 작은 수를 한 쪽으로 분류하고, 큰 수들은 다른 쪽으로 분류하여 정렬하는 방법
* 분할과 정복
- 중앙값 정렬 방식을 확장하여 개발한 방식.
- 평균 정렬 결과가 필요할 때 사용하는 것이 좋다.
- 퀵 정렬은 멀리 있는 값을 서로 비교하고 교환하기 때문에 안정성은 떨어진다.
- 시간 복잡도 O(n log n)
※ 피벗을 중간 또는 마지막을 잡는 이유 :
- 피벗은 첫번째, 중간, 마지막 인덱스나 랜덤으로 선정 가능하다.
- 무엇을 피벗으로 잡느냐에 따라 처리 시간이 달라진다.
- 피벗 값이 중간 크기일 수록 더 균등하게 리스트를 분할 할 수 있다.
■ 재귀적인 퀵 정렬 (배열 사용)
package _02_정렬;
import java.util.Arrays;
public class _00_QuickSort3_안보고구현하기 {
//오름차순 퀵소트 메소드를 구현하라
private static void quickSortAsc(int[] arr, int left, int right) {
int pl = left;
int pr = right;
int pivot = arr[(pl + pr)/2];
//피봇 값을 기준으로 좌우를 정렬
while (pl <= pr) {
while (arr[pl] < pivot) pl++; //큰값이 나올때까지
while (arr[pr] > pivot) pr--; //작은값이 나올때까지
if (pl <= pr) {
swap(arr, pl, pr); //교환하고
pl++; //다시 커서 이동
pr--;
}
}
//재귀를 사용해 분할&정렬을 반복한다. (이 시점에서 pr < pl)
if (left < pr) { //1개 이상일 때
quickSortAsc(arr, left, pr);
}
if (pl < right) {
quickSortAsc(arr, pl, right);
}
}
//내림차순 퀵소트 메소드를 구현하라
private static void quickSortDes(int[] arr, int left, int right) {
int pl = left;
int pr = right;
int pivot = arr[(pl + pr)/2];
//피봇 값을 기준으로 좌우를 정렬
while (pl <= pr) {
while (arr[pl] > pivot) pl++; //작은값이 나올때까지
while (arr[pr] < pivot) pr--; //큰값이 나올때까지
if (pl <= pr) {
swap(arr, pl, pr); //교환하고
pl++; //다시 커서 이동
pr--;
}
}
//재귀를 사용해 분할&정렬을 반복한다. (이 시점에서 pr < pl)
if (left < pr) { //1개 이상일 때
quickSortDes(arr, left, pr);
}
if (pl < right) {
quickSortDes(arr, pl, right);
}
}
//교환 메소드
static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
//랜덤 메소드
public static int[] random(int[] arr) {
OUTER :
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random()*10)+1;
for (int j = 0; j < i; j++) {
if (arr[j] == arr[i]) {
i--;
continue OUTER;
}
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = new int[10];
random(arr);
System.out.println(Arrays.toString(arr));
quickSortAsc(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
quickSortDes(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
>> 결과
[1, 7, 5, 10, 2, 4, 3, 8, 9, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
더보기
//엔지니어 대한민국 방식
private static void quickSort(int[] arr) {
quickSort(arr,0,arr.length-1);
}
private static void quickSort(int[] arr, int start, int end) {
int part2 = partition(arr, start, end);
if (start < part2 - 1) { //오른쪽 파티션이 왼쪽 파티션보다 1개 보다 더 많이 차이날때
quickSort(arr, start, part2 - 1);
}
if (start < end) { //오른쪽 파티션이 1개 이상일 때
quickSort(arr, part2, end);
}
}
private static int partition(int[] arr, int start, int end) {
int pivot = arr[(start + end) / 2];
while (start <= end) {
while (arr[start] < pivot) start++;
while (arr[end] > pivot) end--;
if (start <= end) {
swap (arr, start, end);
start++;
end--;
}
}
return start;
}
private static void swap(int[] arr, int start, int end) {
int tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
}
private static void printArray(int[] arr) {
for (int data : arr) {
System.out.print(data + ",");
}
System.out.println();
}
■ 비재귀적인 퀵 정렬 (ArrayList or Stack 사용)
//알고리즘과 자료구조 방식
public static <T extends Comparable<? super T>> List<T> quicksort(List<T> list)
{
if (list.size() <= 1) return list;
int pivot = list.size() / 2;
List<T> a = new ArrayList<T>(); //lesser
List<T> b = new ArrayList<T>(); //greater
int c = 0; //same
for (T number : list) {
if (list.get(pivot).compareTo(number) < 0) //-1, number > pivot
b.add(number);
else if (list.get(pivot).compareTo(number) > 0) //+1, number < pivot
a.add(number);
else
c++;
}
a = quicksort(a);
for (int i = 0; i < c; i++) {
a.add(list.get(pivot));
}
b = quicksort(b);
List<T> sorted = new ArrayList<T>();
sorted.addAll(a);
sorted.addAll(b);
return sorted;
}
[출처]
- 부스트코스, 자바로 구현하고 배우는 자료구조
- 유투브, 엔지니어 대한민국, 퀵정렬에 대해 알아보고 자바로 구현하기
- 책, [그림으로 정리한 알고리즘과 자료구조], 조민호 지음
- 책, [do it 자료구조와 함께 배우는 알고리즘 입문]
