• Tweet
• Sumo

• Tweet

Quick sort Algorithm in Pseudo code
from Quick sort algorithm article in Wikipedia
[javascript]
function quicksort(‘array’)
if length(‘array’) ≤ 1
return ‘array’ // an array of zero or one elements is already sorted
select and remove a pivot value ‘pivot’ from ‘array’
create empty lists ‘less’ and ‘greater’
for each ‘x’ in ‘array’
if ‘x’ ≤ ‘pivot’ then append ‘x’ to ‘less’
else append ‘x’ to ‘greater’
return concatenate(quicksort(‘less’), ‘pivot’, quicksort(‘greater’)) // two recursive calls
[/javascript]

Quick sort Algorithm in Java code
download Quick sort Algorithm in Java code
[java]
package com.djitz.sort;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
* Quick sort algorithm (simple)
* based on pseudo code on Wikipedia “Quick Sort” aricle
*
* @see http://en.wikipedia.org/wiki/Quicksort#Simple_version
* @author djitz
*
*/
public class QuickSort {

/**
* Main method.
* @param args
*/
public static void main(String[] args) {

QuickSort app = new QuickSort();

//Generate an integer array of length 7
List input = app.generateRandomNumbers(7);

//Before sort
System.out.println(input);

//After sort
System.out.println(app.quicksort(input));

}

/**
* This method sort the input ArrayList using quick sort algorithm.
* @param input the ArrayList of integers.
* @return sorted ArrayList of integers.
*/
private List quicksort(List input){

if(input.size() <= 1){ return input; } int middle = (int) Math.ceil((double)input.size() / 2); int pivot = input.get(middle); List less = new ArrayList();
List greater = new ArrayList();

for (int i = 0; i < input.size(); i++) { if(input.get(i) <= pivot){ if(i == middle){ continue; } less.add(input.get(i)); } else{ greater.add(input.get(i)); } } return concatenate(quicksort(less), pivot, quicksort(greater)); } /** * Join the less array, pivot integer, and greater array * to single array. * @param less integer ArrayList with values less than pivot. * @param pivot the pivot integer. * @param greater integer ArrayList with values greater than pivot. * @return the integer ArrayList after join. */ private List concatenate(List less, int pivot, List greater){

List list = new ArrayList();

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; } /** * This method generate a ArrayList with length n containing random integers . * @param n the length of the ArrayList to generate. * @return ArrayList of random integers with length n. */ private List generateRandomNumbers(int n){

List list = new ArrayList(n);
Random random = new Random();

for (int i = 0; i < n; i++) { list.add(random.nextInt(n * 10)); } return list; } } [/java]