Difference between revisions of "Quicksort"

From CodeCodex

m (forgot the template here too)
(Implementations)
Line 1: Line 1:
 
{{Template:Infobox See Also Sort}}
 
{{Template:Infobox See Also Sort}}
 
==Implementations==
 
==Implementations==
 +
 +
===Haskell===
 +
 +
quicksort [] = []
 +
quicksort (x:xs) = quicksort [ i | i <- xs, i < x ]
 +
                    ++ x :
 +
                    quicksort [ i | i <- xs, i >= x ]
 +
 
===Java===
 
===Java===
 
<pre>
 
<pre>
Line 56: Line 64:
 
}
 
}
 
</pre>
 
</pre>
 +
 +
===OCaml===
 +
 +
# let rec quicksort = function
 +
    | [] -> []
 +
    | h::t ->
 +
        quicksort (List.filter (( >= ) h) t)
 +
        @ h ::
 +
        quicksort (List.filter (( < ) h) t);;
 +
 +
For example:
 +
 +
# quicksort [1;6;4;3;2;8;9;7;5;10];;
 +
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
 +
 
[[Category:Sort algorithms]]
 
[[Category:Sort algorithms]]
 
[[Category:Java]]
 
[[Category:Java]]

Revision as of 15:24, 25 June 2007

Related content:

Implementations

Haskell

quicksort [] = []
quicksort (x:xs) = quicksort [ i | i <- xs, i < x ]
                   ++ x :
                   quicksort [ i | i <- xs, i >= x ]

Java

public class Quicksort
{
    
    static int[] values;
    
    public static void main(String[] args)
    {
    	values = new int[25];
    	for(int i = 0; i < values.length; i++)
    	{
    		values[i] = (int)(Math.random() * 50);
    	}
    	sort(0, values.length - 1);
    	for(int n : values)
    	{
    		System.out.println(n);
    	}
    }
    
    public static void sort(int beginning, int end)
    {
    	if(beginning >= end) return;
    	int pivot = split(beginning, end);
    	sort(beginning, pivot);
    	sort(pivot + 1, end);
    }
    
    private static int split(int beginning, int end)
    {
    	int x = beginning - 1;
    	int y = end + 1;
    	int pivot = values[(beginning + end) / 2];
    	while(x < y)
    	{
    		x++;
    		while(values[x] < pivot)
    			x++;
    		y--;
    		while(values[y] > pivot)
    			y--;
    		if(x < y) swap(x, y);
    	}
    	return y;
    }
    
    private static void swap(int a, int b)
    {
    	int temp = values[a];
    	values[a] = values[b];
    	values[b] = temp;
    }
}

OCaml

# let rec quicksort = function
   | [] -> []
   | h::t -> 
       quicksort (List.filter (( >= ) h) t)
       @ h ::
       quicksort (List.filter (( < ) h) t);;

For example:

# quicksort [1;6;4;3;2;8;9;7;5;10];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]