NỘI DUNG

Hosting tốc độ cao Vietnix - tốc độ tải trang trung bình dưới 1 giây
VPS siêu tốc Vietnix - trải nghiệm mượt mà, ổn định
22/09/2022
Lượt xem

Tìm hiểu thuật toán QuickSort là gì? Cách triên khai trên nhiều ngôn ngữ

22/09/2022
21 phút đọc
Lượt xem

Đánh giá

5/5 - (192 bình chọn)

Thuật toán Quick Sort là một trong các thuật toán sắp xếp cực hiệu quả, có khả năng ứng dụng cao nhất hiện nay. Hãy cùng Vietnix tìm hiểu chi tiết về Quick Sort là gì và cách triển khai Quick Sort trong các môi trường ngôn ngữ lập trình khác nhau từ C++14, Java, Python cho đến C#, Javascript.

Thuật toán QuickSort là gì?

Thuật toán QuickSort là một dạng thuật toán sắp xếp, được xây dựng dựa trên nguyên tắc thuật toán chia để trị. QuickSort hoạt động dựa trên việc phân chia các mảng dữ liệu thành các nhóm phần tử nhỏ hơn. Tuy nhiên, các lập trình viên sẽ cần một thời gian đáng kể để làm quen, nghiên cứu và học cách “làm chủ” Thuật toán QuickSort. Các phiên bản QuickSort khác nhau sẽ chọn pivot theo những cách khác nhau.

  • Luôn chọn phần tử đầu tiên làm trục.
  • Luôn chọn phần tử cuối cùng làm trục.
  • Chọn một phần tử ngẫu nhiên làm trục quay.
  • Chọn trung vị làm trục.
Thuật toán QuickSort là gì?
Thuật toán QuickSort là gì?

Quá trình đóng vai trò quan trọng trong QuickSort là phân vùng (). Phân vùng là việc đặt một mảng và một phần tử x của mảng làm trụ, đặt x vào đúng vị trí của nó trong mảng đã sắp xếp và đặt tất cả các phần tử nhỏ hơn x và trước x, đặt tất cả các phần tử lớn hơn x và sau x. 

Minh họa cách triển khai thuật toán QuickSort

Dưới đây sẽ là minh họa chung cho khả năng sắp sếp của thuật toán QuickSort.

Thuật toán phân vùng

Có nhiều cách để thực hiện thuật toán phân vùng. Chúng ta bắt đầu từ phần tử ngoài cùng bên trái và theo dõi chỉ số của các phần tử nhỏ hơn (hoặc bằng) là i. Trong quá trình duyệt, nếu tìm thấy một phần tử nhỏ hơn, bạn cần hoán đổi phần tử hiện tại với arr [i]. Nếu không, bạn nên bỏ qua phần tử hiện tại.

Pseudo code cho hàm QuickSort function:

/* 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
    }
}

Pseudo code cho phân vùng ()

/* Hàm này nhận phần tử cuối cùng làm pivot, đặt phần tử pivot vào đúng vị trí và đặt tất cả các phần tử nhỏ hơn (nhỏ hơn pivot) ở bên trái của pivot, còn các phần tử lớn hơn ở bên phải của pivot*/.

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

Minh họa phân vùng – partition()

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
Minh họa phân vùng quick sort
Tìm hiểu thuật toán QuickSort là gì? Cách triên khai trên nhiều ngôn ngữ 27
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
minh hoa phan vung 2
Tìm hiểu thuật toán QuickSort là gì? Cách triên khai trên nhiều ngôn ngữ 28
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 
minh hoa phan vung 8
Tìm hiểu thuật toán QuickSort là gì? Cách triên khai trên nhiều ngôn ngữ 29
  • j = 3 : Since arr[j] > pivot, do nothing // Không thay đổi i và arr[]
  • j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
  • i = 2
  • arr[] = {10, 30, 40, 90, 80, 50, 70} // Hoán đổi 80 và 40
minh hoa phan vung 3
Tìm hiểu thuật toán QuickSort là gì? Cách triên khai trên nhiều ngôn ngữ 30
  • j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j] 
  • i = 3 
  • arr[] = {10, 30, 40, 50, 80, 90, 70} // Hoán đổi 90 và 50
minh hoa phan vung 4
Tìm hiểu thuật toán QuickSort là gì? Cách triên khai trên nhiều ngôn ngữ 31
  • Thoát khỏi vòng lặp vì j cao hơn -1.
  • Cuối cùng, bạn đặt trục ở vị trí chính xác bằng cách hoán đổi arr[i+1] and arr[high] (or pivot) arr[] = {10, 30, 40, 50, 70, 90, 80} // Hoán đổi 80 và 70
minh hoa phan vung 5
Tìm hiểu thuật toán QuickSort là gì? Cách triên khai trên nhiều ngôn ngữ 32
  • Giờ phần tử 70 đã ở đúng vị trí, tất cả các phần tử < 70 nằm trước nó còn các phần tử > 70 nằm đằng sau.
  • Vì QuickSort là một hàm đệ quy, ta gọi lại hàm phân vùng ở các phân vùng bên trái và bên phải.
minh hoa phan vung 6
Tìm hiểu thuật toán QuickSort là gì? Cách triên khai trên nhiều ngôn ngữ 33
  • Gọi chức năng ở phần bên phải và hoán đổi 80, 90.
minh hoa phan vung 7
Tìm hiểu thuật toán QuickSort là gì? Cách triên khai trên nhiều ngôn ngữ 34

Cách triển khai QuickSort cho 5 ngôn ngữ lập trình phổ biến nhất hiện nay

Dưới đây là cách triển khai QuickSort cho một số ngôn ngữ lập trình phổ biến.

Triển khai QuickSort trong C++14

/* 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;
}

QuickSort trong Java

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

Bạn có thể tìm hiểu thêm về ngôn ngữ này trong bài tìm hiểu ngôn ngữ lập trình Java cho người mới của Vietnix.

Triển khai QuickSort trong Python 3

# 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}')

Nếu bạn đang tìm hiểu về Python có thể tham khảo bài viết về Python là gì và ứng dụng của ngôn ngữ lập trình Python.

Triển khai QuickSort trong C#

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

Triển khai QuickSort trong Javascript

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

Triển khai QuickSort bằng cách sử dụng phần tử đầu tiên làm trụ:

C++

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

Python3

# 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}')

   Output

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

Phân tích QuickSort

Thời gian thực hiện bởi QuickSort có thể được viết như sau:

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

Hai thuật ngữ đầu tiên dành cho hai cuộc gọi đệ quy, thuật ngữ cuối dành cho tiến trình phân vùng. (Trong đó: k là số phần tử nhỏ hơn pivot).

Thời gian thực hiện bởi QuickSort phụ thuộc vào mảng đầu vào và chiến lược phân vùng. Sau đây là ba trường hợp:

Trường hợp xấu nhất

Trường hợp xấu nhất xảy ra khi tiến trình phân vùng luôn chọn phần tử lớn nhất hoặc nhỏ nhất làm trục. Nếu xem xét chiến lược phân vùng trong đó phần tử cuối cùng luôn được chọn làm trục xoay, trường hợp xấu nhất sẽ xảy ra khi mảng đã được sắp xếp theo thứ tự tăng hoặc giảm. Sau đây là sự tái diễn cho trường hợp xấu nhất.  

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

Giải pháp cho sự tái diễn trên là (n2)

Trường hợp tốt nhất

Trường hợp tốt nhất xảy ra khi quá trình phân vùng luôn chọn phần tử ở giữa làm trục. Sau đây là sự tái diễn cho trường hợp tốt nhất. 

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

Giải pháp cho sự lặp lại ở trên là (nLogn). Nó có thể được giải quyết bằng cách sử dụng trường hợp 2 của Định lý Master.

Trường hợp trung bình

Để phân tích trường hợp trung bình, ta cần xem xét tất cả các hoán vị có thể có của mảng và tính toán thời gian thực hiện cho mỗi hoán vị trông không dễ dàng.

Ta có thể hiểu về trường hợp trung bình bằng cách xem xét trường hợp khi phân hoạch đặt O (n / 9) phần tử trong một tập hợp và O (9n / 10) phần tử trong tập hợp khác. Sau đây là sự tái diễn cho trường hợp này.  

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

Giải pháp của sự tái diễn ở trên cũng là O (nLogn):

Mặc dù độ phức tạp về thời gian trong trường hợp xấu nhất của QuickSort là O (n2), cao hơn nhiều thuật toán sắp xếp khác như Merge Sort và Heap Sort, QuickSort trong thực tế nhanh hơn vì vòng lặp bên trong của nó có thể được triển khai hiệu quả trên hầu hết các kiến ​​trúc và hầu hết các dữ liệu thế giới.

QuickSort có thể được thực hiện theo nhiều cách khác nhau bằng cách thay đổi sự lựa chọn của trục, để hạn chế tối đa trường hợp xấu nhất xảy ra đối với một loại dữ liệu nhất định. Tuy nhiên, sắp xếp hợp nhất thường được ưu tiên hơn trong trường hợp dữ liệu lớn và được lưu trữ trong bộ nhớ ngoài. 

QuickSort có ổn định không? 

Việc triển khai mặc định thường không ổn định. Tuy nhiên, bất kỳ thuật toán sắp xếp nào cũng có thể được ổn định nếu ta coi các chỉ mục là tham số so sánh. 

QuickSort có In-place không? 

Theo định nghĩa, QuickSort đủ điều kiện là một thuật toán sắp xếp In-place vì nó chỉ sử dụng thêm không gian để lưu trữ các lệnh gọi hàm đệ quy chứ không phải để thao tác đầu vào.

QuickSort 3 chiều là gì? 

Trong thuật toán QuickSort đơn giản, chọn một phần tử làm pivot, phân vùng mảng xung quanh pivot và lặp lại cho các mảng con ở bên trái và bên phải của pivot. 

Hãy xem xét một mảng có nhiều phần tử dư thừa. Ví dụ: {1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 4, 4, 4}. Nếu 4 được chọn làm trục trong Simple QuickSort, ta chỉ sửa một 4 và xử lý đệ quy các lần xuất hiện còn lại. Trong 3 Way QuickSort, một mảng arr [l..r] được chia thành 3 phần: 

  • arr [l..i] phần tử nhỏ hơn pivot.
  • arr [i + 1..j-1] các phần tử bằng pivot.
  • arr [j..r] phần tử lớn hơn pivot. 

Tại sao QuickSort được ưu tiên hơn MergeSort trong sắp xếp Mảng?

QuickSort là thuật toán sắp xếp tại chỗ (tức là không yêu cầu thêm dung lượng) trong khi MergeSort yêu cầu thêm O (N) bộ nhớ, N biểu thị kích thước mảng có thể khá lớn. Việc phân bổ và loại bỏ không gian thừa được sử dụng để sắp xếp hợp nhất làm tăng thời gian chạy của thuật toán.

So sánh độ phức tạp trung bình, ta thấy rằng cả hai kiểu sắp xếp đều có độ phức tạp trung bình O (NlogN) nhưng các hằng số khác nhau. Đối với mảng, sắp xếp hợp nhất bị mất do sử dụng thêm không gian lưu trữ O (N).

Hầu hết các triển khai thực tế của QuickSort đều sử dụng phiên bản ngẫu nhiên. Phiên bản ngẫu nhiên có độ phức tạp thời gian dự kiến ​​là O (nLogn). Trường hợp xấu nhất cũng có thể xảy ra trong phiên bản ngẫu nhiên, nhưng trường hợp xấu nhất không xảy ra đối với một mẫu cụ thể (như mảng được sắp xếp) và QuickSort ngẫu nhiên hoạt động tốt trong thực tế.

QuickSort cũng là một thuật toán sắp xếp thân thiện với bộ nhớ cache vì nó có vị trí tham chiếu tốt khi được sử dụng cho các mảng. QuickSort cũng là đệ quy đuôi, do đó tối ưu hóa cuộc gọi đuôi được thực hiện.

Tại sao MergeSort được ưu tiên hơn QuickSort cho các Danh sách được Liên kết? 

Trong trường hợp danh sách liên kết, trường hợp này khác nhau chủ yếu do sự khác biệt trong phân bổ bộ nhớ của mảng và danh sách liên kết. Trong danh sách liên kết, chúng ta có thể chèn các mục vào giữa trong O (1) không gian phụ và O (1) thời gian. Do đó hoạt động hợp nhất của sắp xếp hợp nhất có thể được thực hiện mà không có thêm dung lượng cho danh sách được liên kết.

Trong mảng, chúng ta có thể thực hiện truy cập ngẫu nhiên vì các phần tử liên tục trong bộ nhớ. Giả sử chúng ta có một mảng A số nguyên (4 byte) và đặt địa chỉ của A [0]x thì để truy cập A [i], chúng ta có thể truy cập trực tiếp vào bộ nhớ tại (x + i * 4).

Không giống như mảng, chúng ta không thể thực hiện truy cập ngẫu nhiên trong danh sách liên kết. QuickSort yêu cầu rất nhiều loại quyền truy cập. Trong danh sách liên kết để truy cập chỉ mục thứ i, chúng ta phải di chuyển từng nút từ đầu đến nút thứ i vì chúng ta không có khối bộ nhớ liên tục. Do đó, chi phí tăng lên để sắp xếp nhanh chóng. MergeSort truy cập dữ liệu một cách tuần tự và nhu cầu truy cập ngẫu nhiên là thấp. 

QuickSort được đánh giá là có hiệu năng mạnh mẽ nhất trong tất cả các loại thuật toán sắp xếp phổ biến hiện nay như Bubble Sort, Insertion Sort, Selection Sort,… Nó cung cấp khả năng sắp xếp danh sách dữ liệu cực nhanh và chính xác. Bởi vậy mà khi nhắc đến các thuật toán quen thuộc trong lập trình, người ta nhớ ngay tới cái tên QuickSort. 

Câu hỏi thường gặp

Tại sao Quick Soft được gọi là thuật toán sắp xếp nhanh?

Cái tên “Quick Soft” xuất phát từ thực tế là, sắp xếp nhanh có khả năng sắp xếp danh sách các phần tử dữ liệu nhanh hơn đáng kể (nhanh hơn hai lần hoặc ba lần) so với bất kỳ thuật toán sắp xếp thông thường nào .

Tại sao QuickSort không ổn định?

QuickSort là một thuật toán không ổn định 
vì chúng ta hoán đổi các phần tử theo vị trí của trục (mà không xem xét vị trí ban đầu của chúng)

Lời kết

Trên đây, Vietnix đã cùng bạn tìm hiểu về cách triển khai Thuật toán sắp xếp nhanh Quick Sort cho các môi trường ngôn ngữ lập trình khác nhau từ C++14, Java, Python cho đến C#, Javascript. Mong rằng qua bài viết này, bạn sẽ hiểu hơn về Quick Sort và sớm “nắm” thuật toán này trong lòng bàn tay.

THEO DÕI VÀ CẬP NHẬT CHỦ ĐỀ BẠN QUAN TÂM

Đăng ký ngay để nhận những thông tin mới nhất từ blog của chúng tôi. Đừng bỏ lỡ cơ hội truy cập kiến thức và tin tức hàng ngày

Chọn chủ đề :

Cao Lê Viết Tiến

Kết nối với mình qua

Kết nối với mình qua

Tăng tốc độ website - Nâng tầm giá trị thương hiệu

Tăng tốc tải trang

95 điểm

Nâng cao trải nghiệm người dùng

Tăng 8% tỷ lệ chuyển đổi

Thúc đẩy SEO, Google Ads hiệu quả

Tăng tốc ngay

SẢN PHẨM NỔI BẬT

7 NGÀY DÙNG THỬ HOSTING

NẮM BẮT CƠ HỘI, THÀNH CÔNG DẪN LỐI

Cùng trải nghiệm dịch vụ hosting tốc độ cao được hơn 100,000 khách hàng sử dụng

Chỉ số tăng trưởng

Điểm Desktop

100 (+39)

Điểm Mobile

100 (+67)

Core Web Vitals

Passed

Lĩnh vực

Ecommerce

Chỉ số tăng trưởng

Điểm Desktop

99 (+28)

Điểm Mobile

100 (+50)

Core Web Vitals

Passed

Lĩnh vực

SEO

Chỉ số tăng trưởng

Điểm Desktop

99 (+26)

Điểm Mobile

98 (+59)

Core Web Vitals

Passed

Lĩnh vực

Ecommerce

Chỉ số tăng trưởng

Điểm Desktop

100 (+8)

Điểm Mobile

98 (+35)

Core Web Vitals

Passed

Lĩnh vực

Giáo Dục

Chỉ số tăng trưởng

Điểm Desktop

100 (+61)

Điểm Mobile

100 (+61)

Core Web Vitals

Passed

Lĩnh vực

Giáo Dục

Võ Thiên Tòng

25 Tháng 2 lúc 21:09

·

Mình muốn gửi lời cảm ơn chân thành đến Team Vietnix, anh Hưng Nguyễn, anh Vietnix Trung, em Quốc Huy đã hỗ trợ tối ưu Page Speed Insight (PSI) cho website vanvoiminhhoa.vn của mình.
Biết đến anh Hưng đã lâu nhưng chưa có duyên sử dụng dịch vụ bên anh. Tình cờ thấy được bài Post của anh về việc hỗ trợ tối ưu PSI miễn phí chỉ với vài Slot, thấy AE cmt khá nhiều nên cũng không nghĩ tới lượt mình. Hôm sau đánh liều inbox 1 phen xem sao thì may mắn được đưa vào danh sách. Vài ngày sau được Team Vietnix liên hệ và hỗ trợ.
Kết quả đạt được:
• Điểm xanh lè xanh lét
• Tốc độ tải trang nhanh hơn hẳn
• Các chỉ số cũng được cải thiện đáng kể
• Và mình tin rằng với việc PSI được cải thiện cũng thúc đẩy những thứ khác đi lên theo!
Mình thực sự hài lòng với dịch vụ của Vietnix và muốn giới thiệu đến tất cả mọi người:
• Dịch vụ Wordpress Hosting: Tốc độ nhanh, ổn định, bảo mật cao, hỗ trợ kỹ thuật 24/7. (https://vietnix.vn/wordpress-hosting/)
• Dịch vụ Business Hosting: Dung lượng lớn, phù hợp cho website có lượng truy cập cao, tích hợp nhiều tính năng cao cấp. (https://vietnix.vn/business-hosting/)
Đặc biệt, Vietnix đang có chương trình ưu đãi:
• Giảm giá 20% trọn đời khi nhập code THIENTONG_PAGESPEED tại trang thanh toán (Chu kỳ 12 tháng trở lên)
• Tặng 1 lần tối ưu điểm Page Speed Insight cho 1 website
Cám ơn Vietnix một lần nữa!
#Vietnix #Vanvoiminhhoa #Pagespeedinsight
Trước khi tối ưu
Sau khi tối ưu
Thiện Nguyễn - CEO SEO Dạo

5 Tháng 3 lúc 16:21

·

CORE WEB VITAL YẾU TỐ XẾP HẠNG TÌM KIẾM SEO
Core Web Vitals là một tập hợp các chỉ số đo lường hiệu suất của trang web từ góc độ người dùng, được Google sử dụng để đánh giá trải nghiệm người dùng trên các trang web. Các chỉ số chính bao gồm:
– Largest contentful paint (LCP): Tốc độ render của page. Mục tiêu là dưới 2,5 giây.
– First input delay (FID): Tốc độ phản hồi của website với tương tác của người dùng. Mục tiêu là dưới 100ms.
– Cumulative Layout Shift (CLS): Độ ổn định của bố cục trang. Mục tiêu là dưới 0.1.
Tất cả các chỉ số này đo lường các khía cạnh quan trọng của trải nghiệm người dùng trên trang web. Google đã công bố rằng từ tháng 5 năm 2021, các Core Web Vitals sẽ được sử dụng làm một trong các yếu tố đánh giá trong việc xếp hạng trang web trên kết quả tìm kiếm. Do đó, hiểu và cải thiện các Core Web Vitals là rất quan trọng đối với SEO.
Tóm lại, Core Web Vitals không chỉ giúp cải thiện hiệu suất và xếp hạng trang web trên công cụ tìm kiếm, mà còn cải thiện trải nghiệm của người dùng khi họ truy cập và tương tác với trang website.
P/s: mình đang có gói hỗ trợ đặc biệt cho anh em tối ưu tốc độ bên VIETNIX:
– Giảm 20% lifetime dịch vụ Hosting Business và Hosting Wordpress chu kỳ 12 tháng trở lên.
– Tặng 1 lần tối ưu điểm Page Speed Insight cho 1 website.
Anh em có nhu cầu đăng ký qua bạn Vietnix Trung này nhé và nhập mã SEODAO_PAGESPEED để được ưu đãi nhé.😁
Trước khi tối ưu
Sau khi tối ưu SEO Dạo
Icharm review

5 Tháng 3 lúc 15:43

·

[Mình vừa được hỗ trợ tối ưu page speed website]
Trước khi được tối ưu, web của mình điểm rất thấp, đặc biệt là mobile chỉ có 39. Cơ duyên thế nào lúc lướt face lại va phải chương trình tối ưu pagespeed bên Vietnix.
Sau khi được Trần Hoàng Phúc và team Vietnix hỗ trợ nhiệt tình, điểm web vọt lên 98 99 (như hình bên dưới). Dùng thử web thì thấy quá là mượt, 10 điểm cho team Vietnix.
Nói thật thì mình thật sự ấn tượng về sự nhiệt huyết, tận tâm và rất chuyên nghiệp bên Vietnix.
Anh em có nhu cầu về hosting hay có vấn đề về website như:
1. Web load chậm
2. Khách rời web vì đợi tải nội dung, hình ảnh lâu
3. Hay tất tần tật mọi thứ về website
THÌ LIÊN HỆ NGAY VIETNIX NHÉ!
Và đừng quên dùng pass “ICHARM_PAGESPEED” để được giảm 20% trọn đời hosting business và wp hosting. Quả code này còn được tặng 1 lần tối ưu pagespeed nữa nhé, ưu đãi chắc cũng phải nhất nhì thị trường luôn.
Trước khi tối ưu
Sau khi tối ưu
Hoàng Nguyễn

29 Tháng 2 lúc 17:04

·

Xin chào mọi người! Vừa rồi mình có sử dụng dịch vụ tối ưu website, tăng tốc độ tải trang pagespeed của Vietnix kết quả trên cả tuyệt vời nên mình viết bài này để chia sẻ thông tin với các bạn.
Lý do mình chọn dịch vụ tối ưu tốc độ website của Vietnix:
✅ Đội ngũ chuyên gia giàu kinh nghiệm: Đã tối ưu thành công cho hàng nghìn website trong nhiều lĩnh vực khác nhau. Các bạn nhân viên rất thân thiện, nhiệt tình và chủ động trong quá trình làm việc để cập nhật tiến độ.
✅ Quy trình chuyên nghiệp:
– Kiểm tra và phân tích: Vietnix sử dụng các công cụ tiên tiến để kiểm tra và phân tích tốc độ website của bạn.
– Xác định nguyên nhân: Vietnix xác định nguyên nhân khiến website tải chậm và đưa ra giải pháp tối ưu phù hợp.
– Tối ưu hóa website: Vietnix áp dụng các kỹ thuật tối ưu tiên tiến nhất để tăng tốc độ tải trang.
– Báo cáo kết quả: Vietnix cung cấp báo cáo chi tiết về kết quả tối ưu hóa website.
Công nghệ tiên tiến: Vietnix sử dụng các công nghệ tối ưu mới nhất như LiteSpeed, LSCache, Memcached, Redis, v.v.
✅ Cam kết kết quả: Vietnix cam kết tăng tốc độ website của bạn lên tối thiểu 90%.
✅ Giá cả cạnh tranh: Vietnix cung cấp dịch vụ tối ưu tốc độ website với mức giá cạnh tranh nhất trên thị trường.
📣 Để đăng ký sử dụng dịch vụ tối ưu tốc độ website và các dịch vụ khác như hosting, vps, domain… các bạn có thể đăng ký tại https://portal.vietnix.vn/aff.php?aff=57 hoặc Inbox cho sếp Vietnix Trung nhé.
Các bạn có thể kiểm tra tốc độ trang của mình https://lasan.edu.vn hoặc một vài trang khác đã sử dụng dịch vụ của Vietnix như sau:
https://pagespeed.web.dev/…/https…/v8beqewyt2…
https://pagespeed.web.dev/…/https…/etiohjvtl4…
https://pagespeed.web.dev/…/https…/yczuqpw6d1…
https://pagespeed.web.dev/…/https…/xf9y65kuzk…
https://pagespeed.web.dev/…/https…/fdrsms15en…
https://pagespeed.web.dev/…/https…/s7p9cgzeri…
Trước khi tối ưu
Sau khi tối ưu
Dũng cá xinh

30 Tháng 1 lúc 19:09

·

[Đỉnh]
Em có dùng hosting, vps, cloud vps, cloud server, dedicated server của rất nhiều bên từ trong nước đến nước ngoài để hosting khoảng 2,000+ domain. Mỗi bên đều có ưu nhược khác nhau, nhưng có 1 số bên đặc biệt “bá đạo”, trong đó có: Vietnix!!!!

Lần đầu tiên em được cả CEO Hưng Nguyễn lẫn Master về dev Vietnix Trung của 1 đơn vị hàng đầu liên quan đến Hosting, Server support từ A – Z (từ Zalo, Tele, đến FB và cả Phone)

Em có khá nhiều web dạng Big Data (bài, ảnh, database, data) lên đến hàng trăm Gb. Càng to thì nó càng có nhiều vấn đề về phần phản hồi ban đầu (nhược điểm cố hữu của php wordpress so với nativejs, reactjs, html, headless,…), và anh em Vietnix có nhã ý hỗ trợ xử lý phần Speed Insight này.

Kết quả thực sự kinh ngạc, từ cách trao đổi đến xử lý vấn đề, cut off những cái cần cut off, xử lý rất sâu vấn đề và gợi ý rất nhiều ý tưởng optimize hệ thống!!!! Thực sự quá hài lòng về kết quả cũng như cách tương tác của các đầu tầu bên Vietnix ^^!!!

Nhân cơ duyên được kết nối với những cao thủ của Vietnix, em xin chia sẻ và lan tỏa để nhiều anh em có cơ hội được sử dụng những dịch vụ tốt nhất với giá vô cùng hợp lý!!!!

1 – Với anh em chưa có hosting, em đặc biệt recommend sử dụng hosting bên Vietnix:
– Sử dụng mã DUNGCAXINH_PAGESPEED sẽ được giảm 20% trọn đời (lifetime luôn)
– Áp dụng các gói Hosting Business, Hosting wordpress và reg 1 năm trở lên
– Anh em chưa biết cách reg thì còm men hoặc ib để em hướng dẫn hoặc nhờ các bạn bên Vietnix support từ A – Z

2 – Anh em có hosting rồi và muốn build blog hoặc web = wordpress mà chưa có giao diện thì nhân tiện em đang có tài khoản Premium bên Envato, em sẽ tặng bất kỳ giao diện nào có trên Envato Themes (Link em để dưới còm men) ạ. Cả nhà còm hoặc ib em Themes mà mọi người “chim ưng”, em sẽ cho anh em tải về, up drive và gửi ạ!!! (Chương trình này kéo dài đến ngày 29 tết âm lịch ạ)

3 – BEST NHẤT luôn!!!! Anh em nào mua hosting dùng mã DUNGCAXINH_PAGESPEED sẽ được tối ưu 100 điểm tốc độ cho 1 web (đây là ưu đãi riêng của CEO Hưng Nguyễn dành cho bạn bè của #dungcaxinh ^^) (Giá trị nhất là cái vụ số 3 này anh chị em nhé ^^), cơ hội vàng để move về đơn vị hosting uy tín là đây ^^!!!!

Một lần nữa xin chân thành cám ơn 2 đồng chí em: Hưng Nguyễn và Vietnix Trung đã giải được một bài toán khó cho các trang WP Big data mà anh loay hoay bao lâu nay chưa tìm ra đáp án!!! Chúc Vietnix ngày càng phát triển và có một năm 2024 đại đại thắng nhé ^^ !!!!!
#SEO #Vietnix #dungcaxinh

Trước khi tối ưu
Sau khi tối ưu
Hiếu AI

2 Tháng 2 lúc 21:06

·

UY TÍN – TẬN TÂM – TỐC ĐỘ

3 từ trên là vẫn chưa đủ để nói về quy trình làm việc cực chuyên nghiệp của team Vietnix.Chuyện là mình có con website chính đang có lượt truy cập organic hàng ngày cũng tương đối (hình 1)

Vấn đề là, con site này đang nằm trên hosting dùng chung nên tốc độ load chưa nhanh, tốc độ load chưa nhanh thì trải nghiệm visitor chưa tốt, trải nghiệm visitor chưa tốt thì tỷ lệ chuyển đổi ra đơn hàng kiểu gì thì kiểu cũng sẽ bị ảnh hưởng.

Biết rõ là đang mất tiền nhưng không biết xử lý như lào, nghĩ mà cay.

Đang loay hoay thì vận may nó tới, hôm qua đang lướt phở bò thấy a Nguyễn Việt Dũng đăng bài, rảnh nên thả cái comment hóng hớt, ai ngờ ngoằng phát thấy ông Dũng tạo nhóm với Vietnix Trung luôn.

Ae Vietnix thì siêu tốc độ, lập tức lấy thông tin vào việc, không hỏi han lằng nhằng, không kỳ kèo chốt đơn dù lúc đấy cũng đang đêm muộn.
Sáng hôm sau dậy vẫn còn đang lơ ngơ mở điện thoại check tin nhắn thì đã thấy ae Vietnix báo xong việc, trong khi mình vẫn chưa biết có chuyện gì xảy ra @@.

Được cái bấm thử website thì thấy load siêu nhanh, chưa tới một giây là thông tin các thứ hiện hết. Quá phê, thả con ảnh trước sau (hình 2,3) để ace tiện đối chiếu nhé. Thế này thì mình gửi gắm nốt 15 em website còn lại cho team Vietnix thôi chứ không cần nghĩ ngợi gì nữa. 10/10.

Nên là:

  1. Anh chị em muốn có một con website tốc độ load nhanh như tốc độ trở mặt của nyc – Dùng ngay dịch vụ hosting của Vietnix
  2. Anh chị em có website rồi muốn tìm bên hosting uy tín, chuyên nghiệp hỗ trợ không quản ngày đêm – Liên hệ ngay Vietnix Trung
  3. Anh chị em quan tâm đến trải nghiệm khách hàng, từ những cái nhỏ nhất như tăng tốc độ website – Better call Vietnix Trung

Và đừng quên dùng pass “HIEUAI_PAGESPEED” để được giảm 20% trọn đời hosting business và wp hosting, quả code này còn được tặng 1 lần tối ưu pagespeed nữa nhé, ưu đãi chắc cũng phải nhất nhì thị trường luôn.
#SEO #Vietnix #hieuai

Website
Trước khi tối ưu
Sau khi tối ưu

Chỉ số tăng trưởng

Điểm Desktop

100 (+43)

Điểm Mobile

100 (+74)

Core Web Vitals

Passed

Lĩnh vực

AI