fork download
copy 
  1. public class Quicksort  {
  2.         private int[] numbers;
  3.         private int number;
  4.  
  5.         public void sort(int[] values) {
  6.                 // check for empty or null array
  7.                 if (values ==null || values.length==0){
  8.                         return;
  9.                 }
  10.                 this.numbers = values;
  11.                 number = values.length;
  12.                 quicksort(0, number - 1);
  13.         }
  14.  
  15.         private void quicksort(int low, int high) {
  16.                 int i = low, j = high;
  17.                 // Get the pivot element from the middle of the list
  18.                 int pivot = numbers[low + (high-low)/2];
  19.  
  20.                 // Divide into two lists
  21.                 while (i <= j) {
  22.                         // If the current value from the left list is smaller than the pivot
  23.                         // element then get the next element from the left list
  24.                         while (numbers[i] < pivot) {
  25.                                 i++;
  26.                         }
  27.                         // If the current value from the right list is larger than the pivot
  28.                         // element then get the next element from the right list
  29.                         while (numbers[j] > pivot) {
  30.                                 j--;
  31.                         }
  32.  
  33.                         // If we have found a value in the left list which is larger than
  34.                         // the pivot element and if we have found a value in the right list
  35.                         // which is smaller than the pivot element then we exchange the
  36.                         // values.
  37.                         // As we are done we can increase i and j
  38.                         if (i <= j) {
  39.                                 exchange(i, j);
  40.                                 i++;
  41.                                 j--;
  42.                         }
  43.                 }
  44.                 // Recursion
  45.                 if (low < j)
  46.                         quicksort(low, j);
  47.                 if (i < high)
  48.                         quicksort(i, high);
  49.         }
  50.  
  51.         private void exchange(int i, int j) {
  52.                 int temp = numbers[i];
  53.                 numbers[i] = numbers[j];
  54.                 numbers[j] = temp;
  55.         }
  56. }
  57.  
  58. import java.util.Arrays;
  59. import java.util.Random;
  60.  
  61. import org.junit.Before;
  62. import org.junit.Test;
  63.  
  64. import static org.junit.Assert.assertTrue;
  65. import static org.junit.Assert.fail;
  66.  
  67. public class QuicksortTest {
  68.  
  69.         private int[] numbers;
  70.         private final static int SIZE = 7;
  71.         private final static int MAX = 20;
  72.  
  73.         @Before
  74.         public void setUp() throws Exception {
  75.                 numbers = new int[SIZE];
  76.                 Random generator = new Random();
  77.                 for (int i = 0; i < numbers.length; i++) {
  78.                         numbers[i] = generator.nextInt(MAX);
  79.                 }
  80.         }
  81.  
  82.         @Test
  83.         public void testNull() {
  84.                 Quicksort sorter = new Quicksort();
  85.                 sorter.sort(null);
  86.         }
  87.  
  88.         @Test
  89.         public void testEmpty() {
  90.                 Quicksort sorter = new Quicksort();
  91.                 sorter.sort(new int[0]);
  92.         }
  93.  
  94.         @Test
  95.         public void testSimpleElement() {
  96.                 Quicksort sorter = new Quicksort();
  97.                 int[] test = new int[1];
  98.                 test[0] = 5;
  99.                 sorter.sort(test);
  100.         }
  101.  
  102.         @Test
  103.         public void testSpecial() {
  104.                 Quicksort sorter = new Quicksort();
  105.                 int[] test = { 5, 5, 6, 6, 4, 4, 5, 5, 4, 4, 6, 6, 5, 5 };
  106.                 sorter.sort(test);
  107.                 if (!validate(test)) {
  108.                         fail("Should not happen");
  109.                 }
  110.                 printResult(test);
  111.         }
  112.  
  113.         @Test
  114.         public void testQuickSort() {
  115.                 for (Integer i : numbers) {
  116.                         System.out.println(i + " ");
  117.                 }
  118.                 long startTime = System.currentTimeMillis();
  119.  
  120.                 Quicksort sorter = new Quicksort();
  121.                 sorter.sort(numbers);
  122.  
  123.                 long stopTime = System.currentTimeMillis();
  124.                 long elapsedTime = stopTime - startTime;
  125.                 System.out.println("Quicksort " + elapsedTime);
  126.  
  127.                 if (!validate(numbers)) {
  128.                         fail("Should not happen");
  129.                 }
  130.                 assertTrue(true);
  131.         }
  132.  
  133.         @Test
  134.         public void testStandardSort() {
  135.                 long startTime = System.currentTimeMillis();
  136.                 Arrays.sort(numbers);
  137.                 long stopTime = System.currentTimeMillis();
  138.                 long elapsedTime = stopTime - startTime;
  139.                 System.out.println("Standard Java sort " + elapsedTime);
  140.                 if (!validate(numbers)) {
  141.                         fail("Should not happen");
  142.                 }
  143.                 assertTrue(true);
  144.         }
  145.  
  146.         private boolean validate(int[] numbers) {
  147.                 for (int i = 0; i < numbers.length - 1; i++) {
  148.                         if (numbers[i] > numbers[i + 1]) {
  149.                                 return false;
  150.                         }
  151.                 }
  152.                 return true;
  153.         }
  154.  
  155.         private void printResult(int[] numbers) {
  156.                 for (int i = 0; i < numbers.length; i++) {
  157.                         System.out.print(numbers[i]);
  158.                 }
  159.                 System.out.println();
  160.         }
  161. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:58: error: class, interface, or enum expected
import java.util.Arrays;
^
Main.java:59: error: class, interface, or enum expected
import java.util.Random;
^
Main.java:61: error: class, interface, or enum expected
import org.junit.Before;
^
Main.java:62: error: class, interface, or enum expected
import org.junit.Test;
^
Main.java:64: error: class, interface, or enum expected
import static org.junit.Assert.assertTrue;
^
Main.java:65: error: class, interface, or enum expected
import static org.junit.Assert.fail;
^
6 errors
stdout
copy 
Standard output is empty
https://ideone.com/vZ5WyZ
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!