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

  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);
  }

See Also

• Sorting Algorithms
• TclArray
• Arrays