FullStack/21. Java
[알고리즘] 퀵정렬
by nakanara
2014. 4. 2.
퀵 정렬(Quicksort)은 C. A. R. 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.
퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에
CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른
O(
n log
n) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다. 또한 퀵 정렬은
불안정 정렬에 속한다
package com.nakanara.quick;
import java.util.Random;
/**
* User: nakanara
* Date: 14. 4. 2
* Time: 오전 10:00
*/
public class QuickSort {
private int[] numbers;
private static final int MAX_NUM = 10;
public QuickSort(){
numbers = new int[MAX_NUM];
randomNumber();
printf();
quickSort(0, MAX_NUM-1);
printf();
}
public void randomNumber(){
Random random = new Random();
for(int i=0; i < MAX_NUM; i++) {
numbers[i] = random.nextInt(100);
}
}
private void quickSort(int low, int high){
int i=low, j=high;
int pivot = numbers[ (low + (high-low)/2)];
while(i <= j) {
while(numbers[i] < pivot) {
i++;
}
while(numbers[j] > pivot) {
j--;
}
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
if(low < j) {
quickSort(low, j);
}
if(i < high){
quickSort(i, high);
}
}
private void exchange(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
public void printf() {
for(int i=0; i < MAX_NUM; i++) {
System.out.print(numbers[i] + " ");
}
System.out.println(" ");
}
public static void main(String args[]) {
QuickSort quickSort = new QuickSort();
}
}
|
관련정보 : 퀵정렬_위키