definition
Quicksort is a sorting algorithm developed by C. A. R. Hoare that, on average, makesO(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makesO(n2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices that minimize the probability of requiringquadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Although quicksort is usually not implemented as an in-place sort, it is possible to create such an implementation. (
algorithm of quick sort
quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
The steps are:
- Pick an element, called a pivot, from the list.
- Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which never need to be sorted.
example
here is my source code (on pascal), I have made it because my laboran has gave me a homework XD, just wanna share with u guys :
uses crt;
type datatipe = array [1..100] of integer;
procedure input (var x:datatipe; n:integer);
var i: integer;
begin
for i:=1 to n do begin
write('data ke-',i,' : '); readln(x[i]);
end;
writeln;
end;
procedure tampil (x:datatipe; n:integer);
var i:integer;
begin
for i:=1 to n do
write (x[i],' ');
end;
procedure tukar(var a,b:integer);
var temp:integer;
begin
temp:=a;
a:=b;
b:=temp;
end;
Procedure QSortAsc(var numbers : datatipe; left : Integer; right : Integer);
Var pivot, l_ptr, r_ptr : Integer;
Begin
l_ptr := left;
r_ptr := right;
pivot := numbers[left];
While (left < right) do
Begin
While ((numbers[right] >= pivot) AND (left < right)) do
right := right - 1;
If (left <> right) then
Begin
Tukar(numbers[left],numbers[right]);
left := left + 1;
End;
While ((numbers[left] <= pivot) AND (left < right)) do
left := left + 1;
If (left <> right) then
Begin
Tukar(numbers[right],Numbers[left]);
right := right - 1;
End;
End;
numbers[left] := pivot;
pivot := left;
left := l_ptr;
right := r_ptr;
If (left < pivot) then
QSortAsc(numbers, left, pivot-1);
If (right > pivot) then
QSortAsc(numbers, pivot+1, right);
End;
Procedure QuickSortAsc(var numbers : datatipe; size : Integer);
Begin
QSortAsc(numbers, 1, size);
End;
Procedure QSortDesc(var numbers : datatipe; left : Integer; right : Integer);
Var pivot, l_ptr, r_ptr : Integer;
Begin
l_ptr := left;
r_ptr := right;
pivot := numbers[left];
While (left < right) do
Begin
While ((numbers[right] <= pivot) AND (left < right)) do
right := right - 1;//2930
If (left <> right) then
Begin
numbers[left] := numbers[right];
Tukar(numbers[left],numbers[right]);
left := left + 1;
End;
While ((numbers[left] >= pivot) AND (left < right)) do
left := left + 1;
If (left <> right) then
Begin
numbers[right] := numbers[left];
Tukar(numbers[right],Numbers[left]);
right := right - 1;
End;
End;
numbers[left] := pivot;
pivot := left;
left := l_ptr;
right := r_ptr;
If (left < pivot) then
QSortDesc(numbers, left, pivot-1);
If (right > pivot) then
QSortDesc(numbers, pivot+1, right);
End;
Procedure QuickSortDesc(var numbers : datatipe; size : Integer);
Begin
QSortDesc(numbers, 1, size);
End;
var data : datatipe;
i,batas : integer;
begin
clrscr();
writeln;
write('masukkan banyaknya data : '); readln(batas);
writeln;
input(data,batas);
QuicksortAsc(data,batas);
write('data setelah diurutkan secara ascending : ');
tampil(data,batas);
writeln;
QuicksortDesc(data,batas);
write('data setelah diurutkan secara Descending: ');
tampil(data,batas);
readln();
end.
