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;
//퀵정렬 해보랍니다. low 는 0 그리고, high 는 배열 길이 (다시 말해 배열의 위치)
quicksort(0,number -1);
}
public void quicksort(int low, int high){
int i = low, j = high;
//Get the pivot 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 than 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 than 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 than the pivot element
// and if we have found a value in the right list which is smaller than the pivot element
// then we exchange the value.
// 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;
}
}
package com.neonex.npa.service;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import java.util.Arrays;
import org.junit.Before;
import org.junit.Test;
import scala.util.Random;
import com.neonex.npa.controller.Quicksort;
public class QuicksortTest {
private int[] numbers;
private final static int SIZE = 7;
private final static int MAX = 20;
@Before
public void setup() throws Exception{
numbers = new int[SIZE];
Random generator = new Random();
for(int i = 0; i < numbers.length ; i++){
numbers[i] = generator.nextInt(MAX);
}
}
@Test
public void testNull(){
Quicksort sorter = new Quicksort();
sorter.sort(null);
}
@Test
public void testEmpty(){
Quicksort sorter = new Quicksort();
sorter.sort(new int[0]);
}
@Test
public void testSimpleElement(){
Quicksort sorter = new Quicksort();
int[] test = new int[1];
test[0] = 5;
sorter.sort(test);
}
@Test
public void testSpecial(){
Quicksort sorter = new Quicksort();
int[] test ={ 5, 5, 6, 6, 4, 4, 5, 5, 4, 4, 6, 6, 5, 5 };
sorter.sort(test);
if(!validate(test)){
fail("Should not happen");
}
printResult(test);
}
@Test
public void testQuicksort(){
for(Integer i : numbers){
System.out.print(i + " ");
}
long startTime = System.currentTimeMillis();
Quicksort sorter = new Quicksort();
sorter.sort(numbers);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("Quicksort : " + elapsedTime);
if(!validate(numbers)){
fail("Should not happen");
}
assertTrue(true);
}
@Test
public void testStandardSort(){
long startTime = System.currentTimeMillis();
Arrays.sort(numbers);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("Standard Java sort " + elapsedTime);
if (!validate(numbers)) {
fail("Should not happen");
}
assertTrue(true);
}
private boolean validate(int[] numbers){
for(int i =0 ; i < numbers.length -1 ; i++){
if(numbers[i] > numbers[i +1]){
return false;
}
}
return true;
}
private void printResult(int[] numbers){
for( int i =0; i< numbers.length -1 ; i++){
System.out.print(numbers[i]);
}
System.out.println();
}
}
