Thuật toán sắp xếp nào là nhanh nhất?

Thuở còn ngồi trên ghế trường đại học đại học, khi học môn “Cấu trúc Dữ liệu & Giải thuật” hay là lúc đi phỏng vấn ở 1 doanh nghiệp ABC, XYZ nào đó, mà cũng có khả năng đến tận lúc ngồi trà đá bàn luận với anh em cộng sự chuyện nghề, chuyện nghiệp … Thì hẳn là đã từng có lần anh em Dev chúng ta được hỏi hoặc là nghe thấy câu hỏi: “Thuật toán sắp xếp nào là nhanh nhất?” Và bài viết này của mình sẽ phần nào giúp các bạn tìm ra câu trả lời cho câu hỏi trên.

Các thuật toán sắp xếp cơ bản

Thuật toáns ắp xếp chèn (Insertion Sort)

Ý tưởng: Insertion Sort lấy ý tưởng nhờ việc chơi bài, dựa theo cách người chơi “chèn” thêm một quân bài mới vào bộ bài đã được bố trí trên tay.

Thuật toán:

• Tại bước k = 1, 2, …, n đưa phần tử thứ k trong mảng đã cho vào đúng vị trí trong dãy gồm k phần tử trước tiên.
• Kết quả là sau bước thứ k, sẽ có k phần tử đầu tiên được sắp xếp theo trình tự.

void insertionSort(int a[], int array_size) int i, j, last; for (i=1; i < array_size; i++) last = a[i]; j = i; while ((j > 0) && (a[j-1] > last)) a[j] = a[j-1]; j = j – 1; a[j] = last; // end for // end of isort

Đánh giá:

• Best Case: 0 hoán đổi, n-1 so sánh (khi dãy đầu vào là đã được sắp)
• Worst Case: n_2n2​/2 hoán đổi và so sánh (khi dãy đầu vào có thứ tự trái lại với thứ tự cần sắp xếp)
• Average Case: n_2n2​/4 hoán đổi và so sánh

Sắp xếp chọn lựa (Selection Sort)

Ý tưởng của Selection sort là tìm từng phần tử cho mỗi vị trí của mảng hoán vị A’ cần tìm.

Thuật toán:

• Tìm phần tử nhỏ nhất đưa vào vị trí 1
• Tìm phần tử nhỏ kế tiếp đưa vào vị trí 2
• Tìm phần tử nhỏ tiếp theo đưa vào vị trí 3
• …

voidselectionSort(int a[], int n)int i, j, min, temp;for (i =0; i < n-1; i++) 
        min = i;for (j = i+1; j < n; j++)if (a[j] < a[min]) min = j;
        swap(a[i], a[min]);
    

Đánh giá:

• Best case: 0 đổi chỗ (n-1 như trong đoạn mã), n_2n2​/2 so sánh.
• Worst case: n – 1 đổi chỗ và n_2n2​/2 so sánh.
• Average case: O(n) đổi chỗ và n_2n2​/2 so sánh.

Sắp xếp nổi bọt (Bubble Sort)

Ý tưởng: Bubble Sort, như cái tên của nó, là thuật toán đẩy phần tử lớn nhất xuống phía cuối dãy, đồng thời những phần tử có thành quả nhỏ hơn sẽ chuyển dịch dần về đầu dãy. Tựa như sự nổi bọt vậy, những phần tử nhẹ hơn sẽ nổi lên phía trên và trái lại, những phần tử lớn hơn sẽ chìm xuống dưới.

Thuật toán: Duyệt mảng từ phần tử đầu tiên. Ta sẽ so sánh mỗi phần tử với phần tử liền trước nó, nếu như chúng đứng sai vị trí, ta sẽ đổi chỗ chúng cho nhau. Chu trình này có thể được dừng nếu như gặp lần duyệt từ khi bắt đầu dãy đến cuối dãy mà không phải thực hiện đổi chỗ bất kì 2 phần từ nào (tức là toàn bộ các phần tử đã được sắp xếp đúng vị trí).

void bubbleSort(int a[], int n) int i, j; for (i = (n-1); i >= 0; i–) for (j = 1; j <= i; j++) if (a[j-1] > a[j]) swap(a[j-1],a[j]);

Đánh giá:

Tuy đơn giản nhưng Bubble là thuật toán kém hiệu quả nhất trong 3 thuật toán ở mục này

• Best case: 0 đổi chỗ, n_2n2​/2 so sánh.
• Worst case: n_2n2​/2 đổi chỗ và so sánh.
• Average case: n_2n2​/4 đổi chỗ và n_2n2​/2 so sánh.

Quick Sort

Quick Sort (QS) được phát triển bởi Hoare năm 1960. Theo tổng hợp và thống kê tính toán, QS là thuật toán sắp xếp một cách nhanh chóng ngày nay.

QS có thời gian tính trung bình là O(n*log n), tuy nhiên thời gian tính tồi nhất của nó lại là O(n_2n2​).

Chọn phần tử chốt:

Việc chọn phần tử chốt nắm vai trò quyết định đối với hiệu suất của thuật toán. Tốt nhất là chọn phần tử chốt là trung vị của danh sách. Tuy nhiên cách này cực kì khó nên ta có thể chọn phần tử chốt theo những bí quyết sau:

• Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.
• Chọn phần tử đứng giữa dãy làm phần tử chốt.
• Chọn phần tử trung vị trong 3 phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt.
• Chọn phần tử ngẫu nhiên làm phần tử chốt. (Cách này có khả năng gây ra năng lực rơi vào các trường hợp đặc biệt).

Thuật toán Phân đoạn Partition: Mục đích của hàm Partition(A, left, right) là chia A[left..right] thành hai đoạn A[left..pivot –1] và *A[pivot+1..right], sao cho:

• A[left..pivot –1] là tập hợp các phần tử có giá trị nhỏ hơn hoặc bằng A[pivot].
• A[pivot+1..right] là tập hợp các phần tử có gía trị lớn hơn A[pivot].

Tương tự như Merge sort, Quick sort là thuật toán sắp đặt được phát triển dựa trên kỹ thuật chia để trị:

1. Neo đệ qui (Base case). Nếu dãy chỉ còn một phần tử thì nó là dãy đã sắp đặt và trao lại dãy này mà không phải làm gì cả.
2. Chia (Divide):
   • Chọn một phần tử trong dãy và gọi nó là phần tử chốt p (pivot).
   • Chia dãy đã cho ra thành hai dãy con: Dãy con trái (L) gồm những phần tử không lớn hơn phần tử chốt, còn dãy con phải (R) gồm các phần tử không nhỏ hơn phần tử chốt. Thực hành các bước này được gọi là thao tác Phân đoạn (Partition).
3. Trị (Conquer): Lặp lại một cách đệ qui thuật toán đối với hai dãy con L và R.
4. Tổng hợp (Combine): Dãy được sắp xếp là L p R.

>>>Xem thêm: Mã UTM code là gì? Cách đo lường hiệu quả chiến dịch quảng cáo

Heap Sort

Định nghĩa* Heap (đống) là cây nhị phân gần hoàn chỉnh có hai tính chất: – Tính cấu trúc (Structural property): Toàn bộ các mức đều đầy đủ node con, ngoại trừ mức cuối cùng. Mức cuối được điền từ trái sang phải. – Tính có thứ tự hay thuộc tính đống (heap property): với mỗi nút x, có Parent(x) ≥ x.

Biểu diễn đống dưới dạng mảng, ta có:

• Gốc của cây là A[1]
• Con trái của A[i] là A[2i]*
• Con phải của A[i] là A[2i + 1]*
• Cha của A[i] là A[ i/2 ]
• Số lượng phần tử của heap là Heapsize[A] ≤ length[A]

Phân loại: Có 2 loại

• Max-heaps (Phần tử lớn nhất ở gốc): với mọi nút i, ngoại trừ gốc: A[parent(i)] ≥ A[i]
• Min-heaps (Phần tử nhỏ nhất ở gốc): với mọi nút i, ngoại trừ gốc: A[parent(i)] ≤ A[i]

Chúng ta sẽ xét bài toán với max-heap, min-heap cũng giống như.

Phép toán khôi phục thuộc tính max-heap (Vun lại đống)

Xét bài toán:

Giả sử có nút i với thành quả bé hơn con của nó và cây con trái và cây con phải của i đều là max-heaps

Thuật toán đệ quy:

• Đổi chỗ i với con lớn hơn
• Di chuyển xuống theo cây
• Bắt đầu các bước cho đến khi node i không để lại bé hơn con.

>>>Xem thêm: Thụât toán tìm kiếm nhị phân (Binary Search)

Kết luận

Thuật toán sắp xếp là một thuật toán rất hay được sử dụng trong khoa học máy tính. Nó giúp con người sửa đổi và cải thiện việc bố trí một đồ vật, một danh sách…

Vì thế nên không thể phủ nhận tầm quan trọng của thuật toán sắp đặt trong những bài toán thực tế mà lập trình viên cần xử lý.

Ngoài những thuật toán sắp xếp ở trên còn cực kì nhiều thuật toán sắp xếp khác vô cùng hữu ích cho hoạt động lập trình của những lập trình viên trở nên dễ dàng hơn.

Bài viết trên, mìn hđã chia sẻ tới các bạn những thuật toán sắp xếp nhanh nhất, hữu dụng nhất. Cảm ơn các bạn đã theo dõi bài viết nhé!

>>Xem thêm: Mã nguồn mở là gì? Tổng hợp các mã nguồn mở tốt nhất hiện nay

Mỹ Phượng-Tổng hợp

Tham khảo: (topdev, viblo,…)