Sorting algorithms/Quicksort: Difference between revisions
No edit summary |
(add Forth) |
||
Line 27: | Line 27: | ||
quick(array, array+length-1); |
quick(array, array+length-1); |
||
} |
} |
||
=={{header|Forth}}== |
|||
defer lessthan ( a@ b@ -- ? ) ' < is lessthan |
|||
: mid ( l r -- mid ) over - 2/ -cell and + ; |
|||
: exch ( addr1 addr2 -- ) dup @ >r over @ swap ! r> swap ! ; |
|||
: part ( l r -- l r r2 l2 ) |
|||
2dup mid @ >r ( r: pivot ) |
|||
2dup begin |
|||
swap begin dup @ r@ lessthan while cell+ repeat |
|||
swap begin r@ over @ lessthan while cell- repeat |
|||
2dup <= if 2dup exch >r cell+ r> cell- then |
|||
2dup > until r> drop ; |
|||
: qsort ( l r -- ) |
|||
part swap rot |
|||
\ 2over 2over - + < if 2swap then |
|||
2dup < if recurse else 2drop then |
|||
2dup < if recurse else 2drop then ; |
|||
: sort ( array len -- ) |
|||
dup 2 < if 2drop exit then |
|||
1- cells over + qsort ; |
|||
==[[IDL]]== |
==[[IDL]]== |
Revision as of 02:46, 4 October 2007
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
In this task, the goal is to sort an array of elements using the Quicksort algorithm. The elements must have a total order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers.
C
void quick(int *left, int *right) { if (right > left) { int pivot = left[(right-left)/2]; int *r = right, *l = left; do { while (*l < pivot) l++; while (*r > pivot) r--; if (l <= r) { int t = *l; *l++ = *r; *r-- = t; } } while (l <= r); quick(left, r); quick(l, right); } } void sort(int *array, int length) { quick(array, array+length-1); }
Forth
defer lessthan ( a@ b@ -- ? ) ' < is lessthan : mid ( l r -- mid ) over - 2/ -cell and + ; : exch ( addr1 addr2 -- ) dup @ >r over @ swap ! r> swap ! ; : part ( l r -- l r r2 l2 ) 2dup mid @ >r ( r: pivot ) 2dup begin swap begin dup @ r@ lessthan while cell+ repeat swap begin r@ over @ lessthan while cell- repeat 2dup <= if 2dup exch >r cell+ r> cell- then 2dup > until r> drop ; : qsort ( l r -- ) part swap rot \ 2over 2over - + < if 2swap then 2dup < if recurse else 2drop then 2dup < if recurse else 2drop then ; : sort ( array len -- ) dup 2 < if 2drop exit then 1- cells over + qsort ;
IDL
IDL has a powerful optimized sort() built-in. The following is thus merely for demonstration.
function qs, arr if (count = n_elements(arr)) lt 2 then return,arr pivot = total(arr) / count ; use the average for want of a better choice return,[qs(arr[where(arr le pivot)]),qs(arr[where(arr gt pivot)])] end
Example:
IDL> print,qs([3,17,-5,12,99]) -5 3 12 17 99