Nội dung chính
Thuật toán Quicksort
Thuật toán quicksort sắp xếp một mảng bằng cách chọn một phần tử làm giá trị chốt (pivot) và phân chia mảng thành hai phần, sao cho các phần tử bên trái pivot đều nhỏ hơn hoặc bằng pivot, các phần tử bên phải pivot đều lớn hơn hoặc bằng pivot, sau đó sắp xếp các phần tử bên trái và bên phải pivot đệ quy. Quá trình đệ quy được thực hiện đến khi các phần tử con chỉ còn một phần tử hoặc không còn phần tử nào để sắp xếp.
Cài đặt thuật toán Quicksort với Pascal
procedure quicksort(var arr: array of integer; left, right: integer);
var
i, j, pivot, temp: integer;
begin
i := left;
j := right;
pivot := arr[left + (right - left) div 2];
while i <= j do
begin
while arr[i] < pivot do
i := i + 1;
while arr[j] > pivot do
j := j - 1;
if i <= j then
begin
temp := arr[i];
arr[i] := arr[j];
arr[j] := temp;
i := i + 1;
j := j - 1;
end;
end;
if left < j then
quicksort(arr, left, j);
if i < right then
quicksort(arr, i, right);
end;
Cài đặt thuật toán Quicksort với một ví dụ cụ thể
program QuicksortExample;
type
TIntArray = array of Integer;
procedure QuickSort(var arr: TIntArray; left, right: Integer);
var
i, j, pivot, temp: Integer;
begin
i := left;
j := right;
pivot := arr[left + (right - left) div 2];
while i <= j do
begin
while arr[i] < pivot do
i := i + 1;
while arr[j] > pivot do
j := j - 1;
if i <= j then
begin
temp := arr[i];
arr[i] := arr[j];
arr[j] := temp;
i := i + 1;
j := j - 1;
end;
end;
if left < j then
QuickSort(arr, left, j);
if i < right then
QuickSort(arr, i, right);
end;
procedure PrintArray(const arr: TIntArray);
var
i: Integer;
begin
for i := Low(arr) to High(arr) do
Write(arr[i], ' ');
Writeln;
end;
var
arr: TIntArray;
i: Integer;
begin
SetLength(arr, 10);
arr[0] := 5;
arr[1] := 2;
arr[2] := 9;
arr[3] := 3;
arr[4] := 7;
arr[5] := 8;
arr[6] := 1;
arr[7] := 6;
arr[8] := 4;
arr[9] := 0;
Writeln('Before sorting:');
PrintArray(arr);
QuickSort(arr, Low(arr), High(arr));
Writeln('After sorting:');
PrintArray(arr);
Readln;
end.