Skip to content

Instantly share code, notes, and snippets.

@ethanwillis
Created March 21, 2013 01:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ethanwillis/5209906 to your computer and use it in GitHub Desktop.
Save ethanwillis/5209906 to your computer and use it in GitHub Desktop.
Quicksort in java
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package sorts;
import java.io.PrintStream;
import java.util.ArrayList;
/**
*
* @author Ethan
*/
public class Sorts {
private static ArrayList<Integer> list = new ArrayList<Integer>();
private static PrintStream out = System.out;
public static void main(String[] args) {
list.add(0);
list.add(-3);
list.add(7);
list.add(10);
list.add(4);
list.add(5);
list = quicksort(list);
for(int i = 0; i < list.size(); ++i)
{
out.print(", " + list.get(i));
}
}
private static ArrayList<Integer> quicksort(ArrayList<Integer> input){
if(input.size() <= 1){
return input;
}
int middle = (int) Math.ceil((double)input.size() / 2);
Integer pivot = input.get(middle);
ArrayList<Integer> less = new ArrayList<Integer>();
ArrayList<Integer> greater = new ArrayList<Integer>();
for (int i = 0; i < input.size(); i++) {
if(pivot.compareTo(input.get(i)) >= 0){
if(i == middle){
continue;
}
less.add(input.get(i));
}
else{
greater.add(input.get(i));
}
}
return concatenate(quicksort(less), pivot, quicksort(greater));
}
private static ArrayList<Integer> concatenate(ArrayList<Integer> less, Integer pivot, ArrayList<Integer> greater){
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < less.size(); i++) {
list.add(less.get(i));
}
list.add(pivot);
for (int i = 0; i < greater.size(); i++) {
list.add(greater.get(i));
}
return list;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment