[JAVA/알고리즘]
Quicksort 큌정렬을 알아보자!
우선 아래 홈페이지
https://opentutorials.org/course/543/2723
오픈튜토리얼에서 각각의 정렬 원리를 잘 설명한
동영상을 보실 수 있습니다.
퀵 정렬이란?
퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다.
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O번의 비교를 수행하고, 평균적으로 O번의 비교를 수행한다.
퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고,
대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다고 합니다.
소스코드를 짜기 전에 설명하자면
1. 퀵정렬은 임의의 pivot 값을 기준으로 pivot 의 좌측에는 pivot 보다 작은값을 두고 우측에는 pivot 보다 큰 값을 두고자 한다.
2. 이 행위는 pivot을 기준으로 좌 우로 이분화 된 리스트를 재귀적으로 반복했을 때 결국 정렬이 완성 된다는 방법 론이다.
3. 보다 쉽게 설명하면 pivot보다 큰 값을 pivot index 보다 왼쪽에서 찾고 ( 큰 값 이 나타날 때까지 i index 를 증가시키도록 한다.)
4. pivot 보다 작은 값을 pivot index 보다 오른쪽에서 찾는다 ( 작은 값이 나타날 때까지 j index를 감소시키도록 한다. )
5. pivot을 기준으로 값 비교가 완료되었다면 index 결과 i , j 를 비교 해본다.
6. i 값이 j 값 보다 작거나 같다면 분명 pivot 을 기준으로 교환을 해야할 값이 있다는 뜻이 된다.
7. 교환한 뒤 i 인덱스는 증가 j 인덱스는 감소 연산을 수행한다.
8. i 인덱스가 j 인덱스보다 작거나 같다면 계속 반복해서 수행한다.
9. 위 와 같은 과정은 pivot을 기준으로 왼쪽으로 정렬된 list 에서는 최초 Left 값이 감소된 j 보다 작다면 계속 재귀하면되고,
9. pivot을 기준으로 오른쪽으로 정렬된 list 에서는 최초 Right 값이 증가된 i 값보다 크다면 계속 재귀하면된다.
위키백과 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
그럼 소스코드를 보도록 합시다.
public class quicksort {
public static void quick(int left, int right, int[] arr) {
int pivot = left;
int j = pivot;
int i = left+1;
int temp; // swap 하기위한 변수
if(left < right) {
// i를 right까지 반복
for(; i<=right; i++) {
// swap 과정
if(arr[i] < arr[pivot]) {
j++;
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
temp = arr[left];
arr[left] = arr[j];
arr[j] = temp;
pivot = j; // 분할
// 정렬과정
quick(left, pivot-1, arr);
quick(pivot+1,right, arr);
}
}
public static void main(String[] args) {
int[] arr = {3,1,4,5,7,9,2,6,8};
quick(0,8,arr);
for(int i=0; i<9; i++) {
System.out.print(arr[i]);
}
}
}
동영상과 위 설명대로 보면서 이해하시면 되겠습니다.
중간에 프린트문을 넣어 돌려봤습니다.
재귀가 많아서 숫자가 변하는 부분을 보시면 됩니다.
아래는 위키백과에서 제공하는 JAVA 코드 입니다.
public void quickSort(int[] arr, int left, int right) { int i, j, pivot, tmp; if (left < right) { i = left; j = right; pivot = arr[left]; //분할 과정 while (i < j) { while (arr[j] > pivot) j--; // 이 부분에서 arr[j-1]에 접근해서 익셉션 발생가능함 while (i < j && arr[i] <= pivot) i++; tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } arr[left] = arr[i]; arr[i] = pivot; //정렬 과정 quickSort(arr, left, i - 1); quickSort(arr, i + 1, right); } }
[JAVA/알고리즘] Quicksort 큌정렬을 알아보자!
이상으로 포스팅을 마치겠습니다.
