QuickSort là gì? Cách triển khai thuật toán sắp xếp trên nhiều ngôn ngữ

/* low  –> Starting index,  high  –> Ending index */
quickSort(arr[], low, high) {
    if (low < high) {
        /*  pi là partitioning index, arr [pi] hiện ở đúng vị trí  */
        pi = partition(arr, low, high);
        quickSort(arr, low, pi – 1);  // Trước pi
        quickSort(arr, pi + 1, high); // Sau pi
    }
}

partition (arr[], low, high)
{
    // pivot (Phần tử được đặt đúng vị trí)
pivot = arr[high];  
 i = (low – 1)  // Index của smaller element và indicates the 
// vị trí bên phải của pivot được tìm thấy cho đến nay
for (j = low; j <= high- 1; j++){
 // Nếu element hiện tại nhỏ hơn pivot
if (arr[j] < pivot){
i++;    // chỉ số increment index của smaller element
 hoán đổi arr[i] và arr[j]
     }
 }
    swap arr[i + 1] and arr[high])
return (i + 1)
}

Consider: arr[] = {10, 80, 30, 90, 40, 50, 70}
 Indexes:  0   1   2   3   4   5   6 
 low = 0, high =  6, pivot = arr[h] = 70
 Khởi tạo index của smaller element, i = -1

Traverse elements from j = low to high-1
 j = 0: Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
 i = 0 
arr[] = {10, 80, 30, 90, 40, 50, 70} // Không hay đổi gì vì i và j giống nhau
 j = 1: Since arr[j] > pivot, do nothing

j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // Hoán đổi 80 và 30 

/* C++ implementation of QuickSort */
#include <bits/stdc++.h>
using namespace std;
//Một utility function để hoán đổi 2 elements
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
/* Hàm này nhận element cuối cùng làm pivot, địa điểm pivot element xoay 
ở vị trí chính xác của nó trong được sắp xếp mảng và đặt tất cả nhỏ hơn (nhỏ hơn pivot) 
ở bên trái của pivot và tất cả các phần tử lớn hơn ở bên phải pivot*/
int partition (int arr[], int low, int high)
{
    int pivot = arr[high]; // pivot
    int i = (low - 1); // Index của smaller element và indicates 
                       //vị trí bên phải pivot được tìm thấy
    for (int j = low; j <= high - 1; j++)
    {
        // Nếu current element là nhỏ hơn pivot
        if (arr[j] < pivot)
        {
            i++; // increment index của element nhỏ hơn
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
/* Main function của implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
        at right place */
        int pi = partition(arr, low, high);
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
// Driver Code
int main()
{
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

// Java implementation of QuickSort
import java.io.*;
class GFG{
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
/* Hàm này nhận phần tử cuối cùng làm pivot, địa điểm phần tử xoay ở vị trí chính xác của nó trong được sắp xếp mảng và đặt tất cả nhỏ hơn (nhỏ hơn pivot) ở bên trái của pivot và tất cả các phần tử lớn hơn ở bên phải pivot */
static int partition(int[] arr, int low, int high)
{
    // pivot
    int pivot = arr[high];
    // Index of smaller element and
    // indicates the right position
    // of pivot found so far
    int i = (low - 1);
    for(int j = low; j <= high - 1; j++)
    {
        // If current element is smaller
        // than the pivot
        if (arr[j] < pivot)
        {
            // Increment index of
            // smaller element
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return (i + 1);
}
/* Chức năng chính thực hiện QuickSort
          arr[] --> Array to be sorted,
          low --> Starting index,
          high --> Ending index
 */
static void quickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        // pi is partitioning index, arr[p]
        // is now at right place
        int pi = partition(arr, low, high);
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
// Function to print an array
static void printArray(int[] arr, int size)
{
    for(int i = 0; i < size; i++)
        System.out.print(arr[i] + " ");
    System.out.println();
}
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 10, 7, 8, 9, 1, 5 };
    int n = arr.length;
    quickSort(arr, 0, n - 1);
    System.out.println("Sorted array: ");
    printArray(arr, n);
}
}

# Python3 implementation of QuickSort 
# Chức năng tìm vị trí phân vùng phân vùng def (mảng, thấp, cao):
  # Chọn phần tử ngoài cùng bên phải làm pivot
  pivot = array[high]
  # Con trỏ cho phần tử lớn hơn
  i = low - 1
  # Đi qua tất cả các yếu tố
  # So sánh từng phần tử với pivot
  for j in range(low, high):
    if array[j] <= pivot:
      # If element smaller than pivot is found
      # swap it with the greater element pointed by i
      i = i + 1
      # Swapping element at i with element at j
      (array[i], array[j]) = (array[j], array[i])
  # Hoán đổi phần tử pivot với phần tử lớn hơn chỉ định
  (array[i + 1], array[high]) = (array[high], array[i + 1])
  # Trả lại vị trí từ nơi phân vùng được thực hiện
  return i + 1
# Chức năng thực hiện QuickSort
def quick_sort(array, low, high):
  if low < high:
    #Tìm phần tử trục sao cho
    # element smaller than pivot are on the left
    # element greater than pivot are on the right
    pi = partition(array, low, high)
    # Recursive call on the left of pivot
    quick_sort(array, low, pi - 1)
    # Recursive call on the right of pivot
    quick_sort(array, pi + 1, high)
# Driver code
array = [ 10, 7, 8, 9, 1, 5]
quick_sort(array, 0, len(array) - 1)
print(f'Sorted array: {array}')

// C# implementation of QuickSort
using System;
class GFG
{
  // A utility function to swap two elements
  static void swap(int[] arr, int i, int j)
  {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  /* Hàm này nhận phần tử cuối cùng làm pivot, địa điểm phần tử xoay ở vị trí chính xác của nó trong được sắp xếp mảng và đặt tất cả nhỏ hơn (nhỏ hơn pivot) ở bên trái của pivot và tất cả các phần tử lớn hơn ở bên phải pivot*/
  static int partition(int[] arr, int low, int high)
  {
    // pivot
    int pivot = arr[high];
    // Index of smaller element and
    // indicates the right position
    // of pivot found so far
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++)
    {
      // If current element is smaller
      // than the pivot
      if (arr[j] < pivot)
      {
        // Increment index of
        // smaller element
        i++;
        swap(arr, i, j);
      }
    }
    swap(arr, i + 1, high);
    return (i + 1);
  }
  /* Chức năng chính thực hiện QuickSort
              arr[] --> Array to be sorted,
              low --> Starting index,
              high --> Ending index
     */
  static void quickSort(int[] arr, int low, int high)
  {
    if (low < high)
    {
      // pi is partitioning index, arr[p]
      // is now at right place
      int pi = partition(arr, low, high);
      // Separately sort elements before
      // partition and after partition
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
    }
  }
  // Function to print an array
  static void printArray(int[] arr, int size)
  {
    for (int i = 0; i < size; i++)
      Console.Write(arr[i] + " ");
    Console.WriteLine();
  }
  // Driver Code
  public static void Main()
  {
    int[] arr = { 10, 7, 8, 9, 1, 5 };
    int n = arr.Length;
    quickSort(arr, 0, n - 1);
    Console.Write("Sorted array: ");
    printArray(arr, n);
  }
}

<script>
// Javascript implementation of QuickSort
// A utility function to swap two elements
function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
/* Hàm này nhận phần tử cuối cùng làm pivot, địa điểm phần tử xoay ở vị trí chính xác của nó trong được sắp xếp mảng và đặt tất cả nhỏ hơn (nhỏ hơn pivot) ở bên trái của pivot và tất cả các phần tử lớn hơn ở bên phải pivot*/
function partition(arr, low, high) {
    // pivot
    let pivot = arr[high];
    // Index of smaller element and
    // indicates the right position
    // of pivot found so far
    let i = (low - 1);
    for (let j = low; j <= high - 1; j++) {
        // If current element is smaller
        // than the pivot
        if (arr[j] < pivot) {
            // Increment index of
            // smaller element
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return (i + 1);
}
/* Chức năng chính thực hiện Quick Sort
          arr[] --> Array to be sorted,
          low --> Starting index,
          high --> Ending index
 */
function quickSort(arr, low, high) {
    if (low < high) {
        // pi is partitioning index, arr[p]
        // is now at right place
        let pi = partition(arr, low, high);
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
// Function to print an array
function printArray(arr, size) {
    for (let i = 0; i < size; i++)
        document.write(arr[i] + " ");
    document.write("<br>");
}
// Driver Code
let arr = [10, 7, 8, 9, 1, 5];
let n = arr.length;
quickSort(arr, 0, n - 1);
document.write("Sorted array: <br>");
printArray(arr, n);

#include <iostream>
#include <algorithm>
using namespace std;
int partition(int arr[], int low, int high)
{
    int i = low;
    int j = high;
    int pivot = arr[low];
    while (i < j)
    {
        while (pivot >= arr[i])
            i++;
        while (pivot < arr[j])
            j--;
        if (i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[low], arr[j]);
    return j;
}
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}
void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main()
{
    int arr[] = {4, 2, 8, 3, 1, 5, 7,11,6};
    int size = sizeof(arr) / sizeof(int);
      cout<<"Before Sorting"<<endl;
    printArray(arr, size);
    quickSort(arr, 0, size - 1);
      cout<<"After Sorting"<<endl;
    printArray(arr, size);
    return 0;
}

# Chức năng tìm vị trí phân vùng
def partition(arr, l, h):
  low, high = l, h
  if l != h and l < h:
    # Chọn phần tử ngoài cùng bên trái làm trục
    pivot = arr[l]
    low = low+1
    # Qua tất cả các yếu tố
    # So sánh từng phần tử với pivot
    while low <= high:
      if arr[high] < pivot and arr[low] > pivot:
        arr[high], arr[low] = arr[low], arr[high]
      if not arr[low] > pivot:
        low += 1
      if not arr[high] < pivot:
        high -= 1
  arr[l], arr[high] = arr[high], arr[l]
  # Trả lại vị trí từ nơi phân vùng được thực hiện
  return high
# Chức năng thực hiện quicksort
def quick_sort(array, low, high):
  if low < high:
      # Find pivot element such that
      # element smaller than pivot are on the left
      # element greater than pivot are on the right
      pi = partition(array, low, high)
      # Recursive call on the left of pivot
      quick_sort(array, low, pi - 1)
      # Recursive call on the right of pivot
      quick_sort(array, pi + 1, high)
# Driver code
array = [ 1, 7, 8, 9, 1, 2]
quick_sort(array, 0, len(array) - 1)
print(f'Sorted array: {array}')

Before Sorting
4 2 8 3 1 5 7 11 6 
After Sorting
1 2 3 4 5 6 7 8 11

T(n) = T(k) + T(n-k-1) + (n)

T(n) = T(0) + T(n-1) + (n)which is equivalent to  T(n) = T(n-1) + (n)

T(n) = 2T(n/2) + (n)

T(n) = T(n/9) + T(9n/10) + (n)