Quick Sort

Quick Sort, like Merge Sort, works on the divide and conquer principle. A pivot element is selected in the array, which serves as a reference point. Values smaller than the pivot are moved to its left, and values larger than the pivot are moved to its right. Then, the same process is applied recursively to the sub-arrays on the left and right of the pivot. As a result, the array becomes sorted.

Steps:

• Select a pivot element.
• Use the pivot to partition the dataset into two sub-arrays: elements smaller than the pivot and elements greater than the pivot.
• Recursively sort the sub-arrays using Quick Sort.
• Combine the sub-arrays and the pivot.

Example:

TRObject Syntax

  var
    arr: array[0..6] of Integer;
    i: Integer;
    str: string;
  
  void swap(a, b: Integer);
  var
    temp: Integer;
  {
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
  
  function partition(low, high: Integer): Integer;
  var
    pivot, i, j: Integer;
  {
    pivot = arr[high];
    i = low - 1;
    
    for (j = low to high - 1)
    {
      if (arr[j] < pivot)
      {
        i = i + 1;
        swap(i, j);
      }
    }
    
    swap(i + 1, high);
    Result =  i + 1;
  }
  
  
  void quickSort(low, high: Integer);
  var
    pi: Integer;
  {
    if (low < high)
    {
      pi = partition(low, high);
      quickSort(low, pi - 1);
      quickSort(pi + 1, high);
    }
  }
  
  {
    arr[0] = 12;
    arr[1] = 11;
    arr[2] = 13;
    arr[3] = 5;
    arr[4] = 1;
    arr[5] = 7;
    arr[6] = 9;
    str = 'Unordered array: ';
    
    for (i = 0 to Length(arr)-1)
    {
      str = str + IntToStr(arr[i]) + ' ';
    }  
    
    ShowMessage(str);
  
    quickSort(0, Length(arr)-1);
    str = 'Array sorted from smallest to largest: ';
    
    for (i = 0 to Length(arr)-1)
    {
      str = str + IntToStr(arr[i]) + ' ';
    }
    ShowMessage(str);
  
    str = 'Array sorted from largest to smallest: ';  
    
    for (i = Length(arr)-1 downto 0)
    {
      str = str + IntToStr(arr[i]) + ' ';
    }
    ShowMessage(str);
  }

Base Syntax

  var
    arr: array[0..6] of Integer;
    i: Integer;
    str: string;
  
  procedure swap(a, b: Integer);
  var
    temp: Integer;
  begin
    temp := arr[a];
    arr[a] := arr[b];
    arr[b] := temp;
  end;
  
  function partition(low, high: Integer): Integer;
  var
    pivot, i, j: Integer;
  begin
    pivot := arr[high];
    i := low - 1;
    
    for j := low to high - 1 do
    begin
      if arr[j] < pivot then
      begin
        i := i + 1;
        swap(i, j);
      end;
    end;
    
    swap(i + 1, high);
    Result :=  i + 1;
  end;
  
  
  procedure quickSort(low, high: Integer);
  var
    pi: Integer;
  begin
    if low < high then
    begin
      pi := partition(low, high);
      quickSort(low, pi - 1);
      quickSort(pi + 1, high);
    end;
  end;
  
  begin
    arr[0] := 12;
    arr[1] := 11;
    arr[2] := 13;
    arr[3] := 5;
    arr[4] := 1;
    arr[5] := 7;
    arr[6] := 9;
    str := 'Unordered array: ';
    
    for i := 0 to Length(arr)-1 do
    begin
      str := str + IntToStr(arr[i]) + ' ';
    end;  
    
    ShowMessage(str);
  
    quickSort(0, Length(arr)-1);
    str := 'Array sorted from smallest to largest: ';
    
    for i := 0 to Length(arr)-1 do
    begin
      str := str + IntToStr(arr[i]) + ' ';
    end;
    ShowMessage(str);
  
    str := 'Array sorted from largest to smallest: ';  
    
    for i := Length(arr)-1 downto 0 do
    begin
      str := str + IntToStr(arr[i]) + ' ';
    end;
    ShowMessage(str);
  end;

See Also

• Sorting Algorithms
• TclArray
• Arrays