퀵소트 ( QuickSort) Java로 구현하기

이번엔 가장 빠르다는 퀵퀵소트에 대해 알아보자.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다. 또한 퀵 정렬은 불안정 정렬에 속한다.

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

물론 위 출처는 위키다. 

위키에서 개념 잡는게 제일 좋다... 뭐 블로그가 다 그렇지... 다만 이제 소스 구현은 편한데로 하면 된다.

자 그럼 Java로 퀵소트를 구현해보자.

public static void main(String[] args) {

int[] arr = {4,7,1,2,3,10,23,13,19,100};

quickSort(arr, 0, arr.length-1);

System.out.println(Arrays.toString(arr));

}

public static void quickSort(int[] arr, int low, int high) {

if( low >= high) return;    // 왼쪽 인덱스 값이 더 클경우 끝낸다.

int left = low;

int right = high;

int pivot = arr[(left+right)/2];

// left 값이 right 값보다 작을 경우 계속 수행해준다. 

while(left < right ) {

while( arr[left] < pivot ) left++;    // 왼쪽배열 값이 pivot 보다 작을 경우 pivot 보다 큰 수를 찾기 위해 계속 이동한다.

while( arr[right] > pivot ) right--;    // 오른쪽배열 값이 pivot 보다 클 경우 pivot보다 작은 수를 찾기 위해 계속 이동한다.

// left 값이 right 값과 같거나 작을 경우 swap 실행 해준다 

if( left <= right ) {

int temp = arr[left];

arr[left] = arr[right];

arr[right] = temp;

left++;

right--;

}

}

// left 배열과 right 배열로 나눠질 것이다. pivot을 이제 바꿔준다

if ( low < right) quickSort(arr, low, right);

if ( high > left ) quickSort(arr, left, high) ;

}

이해가 안가시는 분은 댓글을...최대한 설명을...해주겠다.