Công ty TNHH TMĐT Công nghệ LP

4.0/5 (913 Reviews)

Một trong những thuật toán phổ biến nhất được sử dụng trong lập trình không thể không nhắc đến Quick short. Đây là một thuật toán hỗ trợ, có chức năng chính là sắp xếp và phân loại dữ liệu. Tuy nhiên, để hiểu rõ thuật toán này và biết cách sử dụng nó đòi hỏi người dùng phải dành thời gian phân tích kỹ lưỡng. Ở bài viết hôm nay, LPTech sẽ hướng dẫn đến bạn các khái niệm cơ bản về Quick sort. Cùng tìm hiểu nhé!

Quick sort là gì?

Quick sort là một thuật toán dùng trong ngôn ngữ lập trình C++, dùng để sắp xếp, phân loại nhanh. Quick sort hoạt động theo cơ chế: Chọn một phần tử bất kỳ làm điểm đánh dấu và chia mảng thành hai mảng con bằng cách so sánh các phần tử trong cùng mảng với điểm đã đánh dấu. Lúc này, mảng 1 sẽ chia ra làm các phần tử nhỏ hơn hoặc bằng điểm đánh dấu, mảng 2 sẽ chia ra làm các phần tử lớn hơn điểm đánh dấu.

Tùy theo mỗi người là thuật ngữ "điểm đánh dấu" quan trọng trong Quick sort sẽ có những cách gọi khác nhau như pivot hoặc phần tử chốt. Trong bài viết này, pivot hay phần tử chốt cũng đều được hiểu là điểm đánh dấu.

Hiện nay Quick sort được ứng dụng để sắp xếp dữ liệu vì nó có hiệu suất cao và có thể xử lý được tệp dữ liệu lớn. Thuật toán này cũng được sử dụng trong việc tìm kiếm danh sách sắp xếp. Bằng cách sắp xếp danh sách trước khi thực hiện thao tác tìm kiếm, qua đó, thuật toán sẽ được thực hiện nhanh chóng hơn.

> Xem thêm: Regex là gì? Ứng dụng và cách viết Regex chi tiết nhất

Quick sort là gì?

Cách chọn pivot (phần tử chốt)

Quick sort áp dụng cách thức Divide and Conquer để sắp xếp dữ liệu. Vì vậy nên tốc độ sắp xếp dữ liệu phụ thuộc vào khá nhiều vào kĩ thuật chọn pivot. Tùy theo từng trường hợp cụ thể mà ta sẽ có những cách chọn như sau:

  • Chọn phần tử đầu tiên trong mảng làm pivot.
  • Chọn phần tử cuối cùng trong mảng làm pivot.
  • Chọn phần tử có giá trị nằm giữa mảng làm pivot.
  • Chọn random một phần tử bất kỳ trong mảng làm pivot. Tuy nhiên nên hạn chế cách này vì sẽ dễ làm chúng ta rơi vào các trường hợp đặc biệt nơi các vòng lặp vô hạn diễn ra.

Cách 1: Cách chọn phần tử đầu làm pivot

Để chọn phần tử đầu làm pivot, bạn thực hiện lệnh sau:

quickSort = (unSortedArr) => {

        // nếu mảng không quá 1 phần tử thì mảng đó đã được sản xuất

        if (unSortedArr.length < 2) return unSortedArr;

        const pivot = unSortedArr[0]; //lấy phần tử đầu của mảng làm phần tử chốt

        const leftArr = []; // mảng chứa phần tử nhỏ hơn pivot

        const rightArr = []; // mảng chứa phần tử lớn hơn pivot

        let currentItem; // phần tử đang được xét

        // loop các phần tử còn lại trong mảng trừ phần tử chốt.

        // Do pivot là ptu đầu tiên nên i sẽ bắt đầu từ 1

        for (let i = 1; i < unSortedArr.length; i++) {     

            currentItem = unSortedArr[i];

            if (currentItem < pivot) {

                leftArr.push(currentItem);

            } else {

                rightArr.push(currentItem);

            }

        }

        return […this.quickSort(leftArr), pivot, …this.quickSort(rightArr)];

    }

Cách 2: Cách chọn phần tử cuối làm pivot

Đối với cách chọn phần tử chốt làm điểm đánh dấu, bạn áp dụng câu lệnh dưới đây nhé:

quickSort = (unSortedArr) => {

        if (unSortedArr.length < 2) return unSortedArr;

       

        const pivot = unSortedArr[unSortedArr.length – 1]; //phần tử cuối mảng làm chốt

        const leftArr = []; 

        const rightArr = []; 

        let currentItem;

        

        // Do pivot là ptu cuối nên length sẽ trừ đi 1 

        for (let i = 0; i < unSortedArr.length – 1; i++) {

            currentItem = unSortedArr[i];

            if (currentItem < pivot) {

                leftArr.push(currentItem);

            } else {

                rightArr.push(currentItem);

            }

        }

    

        return […this.quickSort(leftArr), pivot, …this.quickSort(rightArr)];

    }

Cách 3: Cách chọn phần tử giữa làm pivot

Với cách áp dụng chọn phần tử giữa làm pivot, cách thức thực hiện như sau:

quickSort = (unSortedArr) => {

        if (unSortedArr.length < 2) return unSortedArr;

        

        // lấy phần tử giữa làm chốt

        const pivotIndex = Math.floor(unSortedArr.length / 2);

        const pivot = unSortedArr[pivotIndex]; 

        const leftArr = []; 

        const rightArr = []; 

        let currentItem;

        

        unSortedArr.splice(pivotIndex, 1); // loại bỏ ptu pivot trong mảng

        

        for (let i = 0; i < unSortedArr.length; i++) {

            currentItem = unSortedArr[i];

            if (currentItem < pivot) {

                leftArr.push(currentItem);

            } else {

                rightArr.push(currentItem);

            }

        }

    

        return […this.quickSort(leftArr), pivot, …this.quickSort(rightArr)];

    }

Cách triển khai thuật toán Quick sort

Quick sort có độ phức tạp như thế nào?

Độ phức tạp của thuật toán Quick Sort phụ thuộc rất nhiều vào cách chọn phần tử chốt (pivot) và cấu trúc dữ liệu ban đầu. Quick sort có công thức tính thời gian như sau:

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

Trong đó:

  • T(k) và T(n-k-1): Thời gian cho 2 cuộc gọi đệ quy.
  • θ(n): Tiến trình phân vùng.
  • k: Số phần tử nhỏ hơn phần tử chốt

Lưu ý: Thời gian của thuật toán Quick sort phụ thuộc vào mảng đầu và chiến lược chia trong mảng.

Từ công thức tính thời gian trong quick sort trên, chúng ta có thể suy ra được mức độ phức tạp của các trường hợp khi sử dụng quick sort. Cụ thể:

  • Trường hợp tốt nhất: Khi mỗi lần phân hoạch chia mảng thành hai phần có kích thước gần bằng nhau, độ phức tạp của Quick Sort là O(n log n). Đây là trường hợp lý tưởng và thường xảy ra khi dữ liệu đầu vào phân bố ngẫu nhiên.
  • Trường hợp trung bình: Trong hầu hết các trường hợp, độ phức tạp của Quick Sort cũng là O(n log n).
  • Trường hợp xấu nhất: Khi mảng đã được sắp xếp hoặc gần như sắp xếp, và việc chọn pivot luôn là phần tử nhỏ nhất hoặc lớn nhất, độ phức tạp sẽ lên đến O(n^2). Điều này xảy ra vì mỗi lần phân hoạch chỉ tạo ra một phần tử con có kích thước n-1.

Quick sort có độ phức tạp như thế nào?

Ưu, nhược điểm của quick sort

Là một thuật toán được sử dụng phổ biến trong ngôn ngữ lập trình, Quick sort có những ưu và nhược điểm cụ thể.

Ưu điểm của Quick sort

Quick sort là thuật toán được sử dụng rất phổ biến bởi nó mang theo những ưu điểm nổi bật như sau:

  • Quick sort là một trong những thuật toán sắp xếp và phân bố nhanh nhất, đặc biệt là khi áp dụng với những tệp dữ liệu lớn. Quick sort có độ phức tạp trung bình O(n log n) với tốc độ chạy nhanh dù cho đó là bộ dữ liệu lớn.
  • Thuật toán quick sort có thiết kế đơn giản, dễ triển khai và cũng rất dễ hiểu. Việc này hỗ trợ quá trình cài đặt và sử dụng Quick sort nhanh hơn khi so với những thuật toán còn lại.
  • Quick sort có khả năng tự sắp xếp trong chính nó, nghĩa là nó không cần dùng thêm mảng phụ để lưu trữ giá trị trung gian. Từ đó, Quick sort giúp hạn chế việc sử dụng bộ nhớ và gia tăng hiệu suất.
  • Thuật toán này có thể tùy biến theo từng tình huống khác nhau cho phù hợp với dữ liệu thực tế bằng cách chọn pivot hoặc xử lý phần tử bị trùng lặp.

Nhược điểm của Quick sort

Dù có nhiều ưu điểm, Quick sort vẫn là thuật toán tồn tại hạn chế nhất định. Nhược điểm lớn nhất của Quick sort đó là trong trường hợp xấu nhất, khi mảng đã bị đảo ngược, thuật toán sẽ hoạt động chậm và hao tốn nhiều bộ nhớ hơn.

Vì thế, khi dùng Quick sort, bạn cần cân nhắc kết hợp thêm những thuật toán khác để đảm bảo được hiệu suất tối ưu nhất.

Ưu, nhược điểm của quick sort

Minh họa thuật toán quick sort trong C++

Để hiểu rõ về thuật toán Quick sort và cách hoạt động của nó, hãy cùng LPTech phân tích qua ví dụ minh họa trong C++ sau đây. Các bước thực hiện bao gồm: Chọn phần tử chốt (Pivot) > Phân hoạch mảng (Partition) > Di chuyển chỉ số  > Đặt pivot vào đúng vị trí > Gọi đệ quy

Cho một mã triển khai của Quick Sort như sau:

#include <bits/stdc++.h>

using namespace std;

int partition(vector<int>& arr, int low, int high) {

  

    //Chọn pivot 

    int pivot = arr[high];

  

    // Chỉ số của phần tử nhỏ hơn và chỉ ra vị trí đúng của pivot đã tìm thấy cho đến nay

    int i = low - 1;

    // Duyệt qua mảng arr từ low đến high và di chuyển tất cả các phần tử nhỏ hơn về phía bên trái. Các phần tử từ low đến i sẽ nhỏ hơn sau mỗi lần lặp

    for (int j = low; j <= high - 1; j++) {

        if (arr[j] < pivot) {

            i++;

            swap(arr[i], arr[j]);

        }

    }

    

    // Di chuyển pivot đến sau các phần tử nhỏ hơn và trả về vị trí của nó

    swap(arr[i + 1], arr[high]);  

    return i + 1;

}

// Thực hiện hàm sắp xếp nhanh QuickSort

void quickSort(vector<int>& arr, int low, int high) {

  

    if (low < high) {

      

        // pi là chỉ số trả về của pivot sau khi phân hoạch

        int pi = partition(arr, low, high);

        // Gọi đệ quy cho các phần tử nhỏ hơn và các phần tử lớn hơn hoặc bằng

        quickSort(arr, low, pi - 1);

        quickSort(arr, pi + 1, high);

    }

}

int main() {

    vector<int> arr = {10, 7, 8, 9, 1, 5};

    int n = arr.size();

    quickSort(arr, 0, n - 1);

    cout << "Sorted Array\n";

    for (int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

    return 0;

}

Đầu ra

Mảng được sắp xếp

1 5 7 8 9 10

Minh họa thuật toán quick sort

Ứng dụng của quick sort

Quick Sort được sử dụng trong nhiều lĩnh vực của khoa học máy tính, từ các hệ thống cơ sở dữ liệu đến các thuật toán tìm kiếm và đồ họa.

Trong lĩnh vực thiết kế app và thiết kế website chuyên nghiệp, quick sort hỗ trợ lập trình viên rất nhiều trong các công việc như sắp xếp danh sách, tìm kiếm nhị phân, phân tích dữ liệu và các thuật toán khác. Cụ thể:

  • Ứng dụng thương mại điện tử: Quick sort lúc này sẽ sắp xếp danh sách sản phẩm theo giá từ thấp đến cao hoặc ngược lại để người dùng dễ dàng tìm thấy sản phẩm phù hợp.
  • Ứng dụng quản lý danh bạ: Quick sort sắp xếp danh bạ theo tên, số điện thoại hoặc địa chỉ để thuận tiện cho việc tìm kiếm.
  • Ứng dụng bản đồ: Các điểm đánh dấu trên bản đồ được quick sort sắp xếp theo khoảng cách đến vị trí hiện tại của người dùng.

Bài viết trên đây đã mang đến những thông tin hữu ích về thuật toán sắp xếp Quick sort. Có thể nhận thấy được rằng, đây là thuật toán hữu ích và phổ biến được sử dụng trong ngôn ngữ lập trình C++. Hy vọng bài viết đã mang đến cho bạn những kiến thức cơ bản cần thiết về thuật toán Quick sort và phục vụ cho quá trình học tập, làm việc thật hiệu quả nhé!

Liên hệ tư vấn - LPTech

Thông tin liên hệ

Nếu bạn có thắc mắc gì, có thể gửi yêu cầu cho chúng tôi, và chúng tôi sẽ liên lạc lại với bạn sớm nhất có thể .

Công ty TNHH TMĐT Công nghệ LP

Giấy phép kinh doanh số 0315561312/GP bởi Sở Kế Hoạch và Đầu Tư TP. Hồ Chí Minh.

Văn phòng: Lầu 4, Toà nhà Lê Trí, 164 Phan Văn Trị, Phường 12,Quận Bình Thạnh, HCMC

Hotline: 0338 586 864

Mail: sales@lptech.asia

Zalo OA:LP Tech Zalo Official

Zalo Sales:033 85 86 86 64 (Sales)


Bài viết cùng chuyên mục

Props là gì? Bí quyết sử dụng Props sao cho hợp lý nhất

Props là gì? Bí quyết sử dụng Props sao cho hợp...

Props là gì? Đây là một khái niệm quan trọng trong React giúp truyền tải dữ liệu giữa các component. Cùng tìm hiểu chi tiết cách sử dụng...

Quy hoạch động là gì? Cách giảm thời gian chạy của các thuật toán

Quy hoạch động là gì? Cách giảm thời gian chạy...

Quy hoạch động l(Dynamic Programming) à một thuật toán quan trọng dùng để giải quyết các bài toán và nhiệm vụ lập trình. Tìm hiểu nguyên...

Clean Architecture là gì? Kiến trúc ứng dụng tư tưởng độc lập

Clean Architecture là gì? Kiến trúc ứng dụng tư...

Clean Architecture là phương pháp thiết kế phần mềm đề cao tính độc lập để project không bị phụ thuộc vào bất kì bộ công cụ hay framework...

Hibernate ORM là gì? Khi nào nên dùng hibernate thay cho JDBC?

Hibernate ORM là gì? Khi nào nên dùng hibernate...

Hibernate ORM là một khung làm việc mã nguồn mở hoạt động như một tầng trung gian giữa ứng dụng và cơ sở dữ liệutrong Java dùng để ánh...

Markdown là gì? Tìm hiểu tất cả cách sử dụng markdown

Markdown là gì? Tìm hiểu tất cả cách sử dụng...

Markdown là dạng ngôn ngữ đánh dấu được sử dụng khá thông dụng hiện nay. Thứ bạn viết sẽ là thứ được hiển thị WYSIWYG (What You See Is...

cURL là gì? Các câu lệnh cơ bản để sử dụng cURL

cURL là gì? Các câu lệnh cơ bản để sử dụng cURL

cURL là công cụ mạnh mẽ giúp bạn gửi và nhận dữ liệu qua nhiều giao thức khác nhau. Tìm hiểu chi tiết về cURL và các tính năng, giao thức...

Sứ mệnh của LPTech ?

LPTech luôn đặt mình vào khách hàng để hiểu được bạn đang gặp khó khăn gì? Các doanh nghiệp hiện nay đang gặp khó khăn về việc quản lý vận hành website của mình. Chưa tìm được đối tác ưng ý và an toàn để giao trọn trọng trách quản lý website cho của bạn.

Thiết kế website nhưng lại không thể tăng thu nhập cũng như chưa có đối tác làm Dịch vụ SEO uy tín tin cậy. Chúng tôi hiểu được điều đó nên dành cả tâm huyết của mình để có thể hỗ trợ các doanh nghiệp một cách tốt nhất.