Quicksort

Java/Collection 2012.01.27 13:59 |

Quicksort



public class Quicksort {
private int[] numbers;
private int number;
public void sort(int[] values) {
// check for empty or null array
if (values == null || values.length == 0) {
return;
}
this.numbers = values;
number = values.length;
quicksort(0, number -1);
}
private void quicksort(int low, int high) {
int i = low, j = high;
// Get the prvot element from the middle of the list
int pivot = numbers[low + (high - low)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (numbers[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (numbers[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange th values.
// As we are done we can increase i and j
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// Recursion
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;
}
private static void printResult(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
System.out.print(" "+numbers[i]);
}
System.out.println();
}
private static boolean validate(int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) {
if (numbers[i] > numbers[i + 1]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Quicksort sorter = new Quicksort();
int[] test = { 5, 10, 6, 15, 4, 4, 5, 18, 4, 4, 2, 6, 1, 9 };
sorter.sort(test);
if (!validate(test)) {
System.out.println("Should not happen");
}
printResult(test);
}
}






 

신고

'Java > Collection' 카테고리의 다른 글

Mergesort  (0) 2012.01.27
Quicksort  (0) 2012.01.27
LinkedList class  (0) 2012.01.19
ArrayList class  (0) 2012.01.19
Posted by jeonguk