Sorting Algorithms in Delphi

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms but is not the most efficient. Its basic idea is repeatedly stepping through the list to be sorted and comparing adjacent elements. If they are in the wrong order, the elements are swapped. This process continues until the entire list is sorted.

procedure BubbleSort(var Arr: array of Integer; Size: Integer);
var
  i, j, Temp: Integer;
begin
  for i := Size - 1 downto 1 do
  begin
    for j := 0 to i - 1 do
    begin
      if Arr[j] > Arr[j + 1] then
      begin
        Temp := Arr[j];
        Arr[j] := Arr[j + 1];
        Arr[j + 1] := Temp;
      end;
    end;
  end;
end;

Time Complexity: The time complexity of Bubble Sort is O(n^2) in all cases, where 'n' is the number of elements in the array. It performs two nested loops, and each iteration swaps adjacent elements until the array is sorted.

Space Complexity: Bubble Sort has a space complexity of O(1) because it only requires constant additional memory to store temporary variables.

Selection Sort

Selection Sort is a simple and intuitive sorting algorithm that divides the input array into two parts: the sorted and unsorted sub-arrays. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted portion and swaps it with the first unsorted element. This process continues until the entire array is sorted.

procedure SelectionSort(var Arr: array of Integer; Size: Integer);
var
  i, j, MinIndex, Temp: Integer;
begin
  for i := 0 to Size - 2 do
  begin
    MinIndex := i;
    for j := i + 1 to Size - 1 do
    begin
      if Arr[j] < Arr[MinIndex] then
        MinIndex := j;
    end;
    if MinIndex <> i then
    begin
      Temp := Arr[i];
      Arr[i] := Arr[MinIndex];
      Arr[MinIndex] := Temp;
    end;
  end;
end;

Time Complexity: The time complexity of Selection Sort is O(n^2) in all cases, where 'n' is the number of elements in the array. It performs two nested loops, and in each iteration, it finds the minimum (or maximum) element from the remaining unsorted part.

Space Complexity: Selection Sort has a space complexity of O(1) because it only requires constant additional memory to store temporary variables.

Quick Sort

Quick Sort is a highly efficient and widely used sorting algorithm. It follows the Divide and Conquer approach, selecting a pivot element from the array and partitioning the other elements into two sub-arrays - elements less than the pivot and elements greater than the pivot. The sub-arrays are then recursively sorted.

procedure QuickSort(var Arr: array of Integer; L, R: Integer);
var
  I, J, Pivot, Temp: Integer;
begin
  I := L;
  J := R;
  Pivot := Arr[(L + R) div 2];

  repeat
    while Arr[I] < Pivot do
      Inc(I);

    while Arr[J] > Pivot do
      Dec(J);

    if I <= J then
    begin
      Temp := Arr[I];
      Arr[I] := Arr[J];
      Arr[J] := Temp;

      Inc(I);
      Dec(J);
    end;
  until I > J;

  if L < J then
    QuickSort(Arr, L, J);
  if I < R then
    QuickSort(Arr, I, R);
end;

Time Complexity: The time complexity of Quick Sort is O(n log n) on average, where 'n' is the number of elements in the array. However, it can be O(n^2) in the worst-case scenario if the pivot selection is poor.

Space Complexity: Quick Sort has a space complexity of O(log n) due to the recursive calls in its implementation. The auxiliary space required for its operation is relatively low.

Merge Sort

Merge Sort is another efficient sorting algorithm that follows the Divide and Conquer strategy. It divides the input array into two halves, recursively sorts them, and then merges the two sorted halves to produce a sorted output.

procedure Merge(var Arr: array of Integer; L, M, R: Integer);
var
  I, J, K: Integer;
  N1, N2: Integer;
  LeftArr, RightArr: array of Integer;
begin
  N1 := M - L + 1;
  N2 := R - M;

  SetLength(LeftArr, N1);
  SetLength(RightArr, N2);

  for I := 0 to N1 - 1 do
    LeftArr[I] := Arr[L + I];

  for J := 0 to N2 - 1 do
    RightArr[J] := Arr[M + 1 + J];

  I := 0;
  J := 0;
  K := L;

  while (I < N1) and (J < N2) do
  begin
    if LeftArr[I] <= RightArr[J] then
    begin
      Arr[K] := LeftArr[I];
      Inc(I);
    end
    else
    begin
      Arr[K] := RightArr[J];
      Inc(J);
    end;
    Inc(K);
  end;

  while I < N1 do
  begin
    Arr[K] := LeftArr[I];
    Inc(I);
    Inc(K);
  end;

  while J < N2 do
  begin
    Arr[K] := RightArr[J];
    Inc(J);
    Inc(K);
  end;
end;

procedure MergeSort(var Arr: array of Integer; L, R: Integer);
var
  M: Integer;
begin
  if L < R then
  begin
    M := L + (R - L) div 2;
    MergeSort(Arr, L, M);
    MergeSort(Arr, M + 1, R);
    Merge(Arr, L, M, R);
  end;
end;

Time Complexity: The time complexity of Merge Sort is always O(n log n), where 'n' is the number of elements in the array. It recursively divides the array into halves, and the merging process takes linear time.

Space Complexity: Merge Sort has a space complexity of O(n) due to the additional memory required for merging the sub-arrays.

Comparison of Sorting Algorithms:

1. Bubble Sort: While Bubble Sort is easy to understand and implement, it is inefficient for large datasets. Its O(n^2) time complexity makes it slow, especially compared to other more advanced sorting algorithms.

2. Selection Sort: Selection Sort performs better than Bubble Sort but still has a time complexity of O(n^2). It is generally more efficient in practice due to fewer swaps than Bubble Sort.

3. Quick Sort: Quick Sort is one of the most efficient sorting algorithms with an average time complexity of O(n log n). However, its worst-case time complexity is O(n^2) when the pivot selection is poor, making it less predictable.

4. Merge Sort: Merge Sort guarantees a stable O(n log n) time complexity in all cases, making it suitable for large datasets. Although it requires additional memory due to the merging process, it is often preferred for its consistent performance.

Sorting algorithms are powerful tools that every Delphi developer should be familiar with. In this article, we explored four popular sorting algorithms - Bubble Sort, Selection Sort, Quick Sort, and Merge Sort - and their implementations in Delphi. Understanding these algorithms' time and space complexities can help you make informed decisions about which one to use in different scenarios.

As you continue your journey in Delphi programming, consider experimenting with these sorting algorithms and exploring other advanced algorithms to enhance your coding skills further. Happy coding!