Các thuật toán sắp xếp với C#: sắp xếp chọn, chèn, nổi bọt, nhanh

Trong bài học này chúng ta sẽ làm quen với nhóm thuật toán sắp xếp (sorting algorithms) trên mảng sử dụng C#. Mặc dù có nhiều thuật toán khác nhau trên cấu trúc mảng, sắp xếp là nhóm thuật toán bổ biến nhất. Chúng ta sẽ cùng xem xét và đánh giá những thuật toán sắp xếp thông dụng, bao gồm sắp xếp chọn (selection sort), sắp xếp chèn (insertion sort), sắp xếp nổi bọt (bubble sort), sắp xếp nhanh (quicksort).

Do bài học này khá dài và khó tiêu hóa, hãy bookmark nó lại (Ctrl+D) để từ từ nhâm nhi nhé!

Thuật toán Sắp xếp chọn (Selection sort)

Sắp xếp chọn là thuật toán sắp xếp đơn giản nhất. Nếu bạn chưa học bài bản về cấu trúc dữ liệu và thuật toán, khi được yêu cầu sắp xếp mảng, tôi tin rằng hầu hết các bạn sẽ tự xây dựng ra được một thuật toán rất gần với sắp xếp chọn.

Giả sử chúng ta cần sắp xếp một mảng (một chiều) theo thứ tự tăng dần.

Thuật toán sắp xếp chọn hoạt động trên các mảng một chiều. Nó phân chia mảng thành hai phần: (1) phần đã sắp xếp, và (2) phần chưa sắp xếp. Ở giai đoạn khởi đầu, phần đã sắp xếp không có phần tử nào. Phần chưa sắp xếp chứa toàn bộ các phần tử.

Trong mỗi lượt hoạt động, thuật toán này tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ nó với phần tử đầu tiên của phần chưa sắp xếp. Trong lượt đầu tiên, thuật toán dĩ nhiên sẽ tìm ra phần tử nhỏ nhất mảng và đổi chỗ nó với phần tử đầu tiên của mảng (cũng là của phần chưa sắp xếp). Do đó, phần tử đầu tiên của mảng sau lượt 1 sẽ là phần tử nhỏ nhất.

Cũng để ý rằng, với logic hoạt động như trên, phần tử nhỏ nhất của phần chưa sắp xếp sẽ luôn luôn lớn hơn phần tử lớn nhất của phần đã sắp xếp. Khi này, ta có thể đưa phần tử này vào phần đã sắp xếp. Hiểu theo cách khác, là ta đã mở rộng phần đã sắp xếp đến phần tử đầu tiên của phần chưa sắp xếp (tức là mở thêm một ô về phía chưa sắp xếp). Qua mỗi lượt, phần đã sắp xếp sẽ mở rộng dần, phần chưa sắp xếp sẽ thu hẹp dần.

Quá trình sẽ tiếp diễn như vậy cho đến khi phần đã sắp xếp mở rộng ra chiếm hết số phần tử của mảng.

Thuật toán này rất gần với cách thức suy nghĩ thông thường của chúng ta.

Ví dụ minh họa hoạt động của thuật toán sắp xếp chọn

Để dễ dàng hình dung hoạt động của thuật toán này, chúng ta cùng thực hiện (bằng tay) một số ví dụ. Code minh họa trên C# sẽ trình bày ở mục tiếp theo.

Giả sử chúng ta có mảng {10, 3, 1, 7, 9, 2, 0}. Giờ chúng ta cần sắp xếp các phần tử của mảng này theo thứ tự tăng dần. Hình dưới đây minh họa các bước thực hiện.

Ở lượt 1, thuật toán sẽ tìm phần tử nhỏ nhất ở vùng chưa sắp xếp (cũng có nghĩa là phần tử nhỏ nhất mảng, giá trị min = 0). Chỉ số của phần tử này là m=6 (phần tử giá trị 0 có chỉ số là 6). Phần tử đầu tiên của vùng chưa sắp xếp hiện tại cũng là phần tử đầu tiên của mảng, có chỉ số i=0. Phần tử m và i giờ sẽ đổi chỗ cho nhau. Mở rộng ranh giới phần đã sắp xếp ra trước phần tử đầu tiên của vùng chưa sắp xếp. Như vậy, phần đã sắp xếp giờ có một phần tử (giá trị 0). Chuyển tiếp sang lượt 2.

Khi bắt đầu lượt 2, ranh giới đã mở rộng ra sau phần tử đầu tiên của mảng (chứa phần tử giá trị 0). Tiếp tục tìm phần tử nhỏ nhất của vùng chưa sắp xếp (min = 1, m = 2) và đổi chỗ với phần tử đầu tiên của vùng chưa sắp xếp (i=1).

Khi bắt đầu lượt 3, ranh giới giờ đã mở rộng đến sau phần tử thứ hai của mảng. Cũng có nghĩa là phần đã sắp xếp giờ có hai phần tử (giá trị 0 và 1). Lại tìm phần tử nhỏ nhất của vùng chưa sắp xếp (min = 2, m = 5) và đổi chỗ với phần tử đầu tiên của vùng chưa sắp xếp (i = 2).

Quá trình này cứ lặp lại như vậy cho đến lượt 6, khi vùng chưa sắp xếp chỉ còn hai phần tử (9 và 10). Dễ dàng tìm được m = 5, min = 9, và i = 5. Đổi chỗ cho nhau xong là thuật toán hoàn thành nhiệm vụ.

Thực thi thuật toán sắp xếp chọn trong C#

Khi các bạn đã hiểu được hoạt động của thuật toán này, việc thực thi nó trong C# khá đơn giản. Hãy cùng thực hiện lại chương trình dưới đây.

using System;
namespace P01_SelectionSort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Title = "Selection Sort";
            var numbers = new[] {10, 3, 1, 7, 9, 2, 0};
            Sort(numbers);
            Console.ReadKey();
        }
        static void Swap<T>(T[] array, int i, int m)
        {
            T temp = array[i];
            array[i] = array[m];
            array[m] = temp;
        }
        static void Print<T>(T[] array)
        {
            Console.WriteLine(string.Join("\t", array));
        }
        static void Sort<T>(T[] array) where T : IComparable
        {
            for (int i = 0; i < array.Length - 1; i++)
            {
                int m = i;
                T minValue = array[i];
                for (int j = i + 1; j < array.Length; j++)
                {
                    if (array[j].CompareTo(minValue) < 0)
                    {
                        m = j;
                        minValue = array[j];
                    }
                }
                Swap(array, i, m);
                Console.ForegroundColor = ConsoleColor.Yellow;
                Console.WriteLine($"Step {i+1}: i = {i}, m = {m}, min = {minValue}");
                Console.ResetColor();
                Print(array);
                Console.WriteLine();
            }
        }
    }
}

So sánh với ví dụ minh họa đã thực hiện ở mục trước.

Các thuật toán trong bài này đều sử dụng kỹ thuật lập trình generic. Kỹ thuật này giúp các phương thức có thể làm việc với bất kỳ kiểu dữ liệu nào có thể so sánh được (thực thi giao diện IComparable). Hãy đọc kỹ bài viết trên nếu bạn chưa nắm chắc kỹ thuật này.

Tính toán theo lý thuyết, thuật toán sắp xếp chọn là một thuật toán không hiệu quả lắm với độ phức tạp là O(n²). Thực tế qua code chúng ta dễ dàng nhận thấy nó có hai vòng lặp lồng nhau. Một vòng lặp để di chuyển ranh giới vùng, một vòng lặp để tìm giá trị nhỏ nhất trong vùng chưa sắp xếp.

Link tải mã nguồn solution để ở phần cuối của bài học.

Thuật toán sắp xếp chèn (Insertion sort)

Tương tự như sắp xếp chọn, sắp xếp chèn cũng hoạt động trên mảng một chiều và là một thuật toán khá đơn giản. Thuật toán này cũng chia mảng thành hai phần: (1) phần đã sắp xếp, (2) phần chưa sắp xếp. Sự khác biệt với thuật toán sắp xếp chọn ở chỗ, phần đã sắp xếp ngay từ đầu đã chứa một phần tử (là phần tử chỉ số 0 của mảng gốc).

Trong mỗi lượt, thuật toán này sẽ mở rộng phần sắp xếp ra phần tử đầu tiên của phần chưa sắp xếp và tìm cách chèn phần tử mới này vào đúng thứ tự nó cần có trong phần đã sắp xếp. Khi được chèn vào đúng thứ tự về giá trị, vùng đã sắp xếp luôn duy trì được đúng trật tự của các phần tử.

Việc chèn phần tử mới vào đúng thứ tự được thực hiện bằng cách lần lượt so sánh nó với các phần tử của vùng đã sắp xếp. Nếu phần tử mới nhỏ hơn thì sẽ đổi vị trí với phần tử đang so sánh.

Quá trình tiếp diễn cho đến khi vùng đã sắp xếp mở rộng ra chiếm hết vùng chưa sắp xếp.

Minh họa hoạt động của thuật toán sắp xếp chèn

Chúng ta cùng xem minh họa hoạt động của thuật toán sắp xếp chèn trên mảng một chiều {9, 1, 5, 2, 4, 6, 3}. Quá trình được thể hiện qua hình dưới đây.

Có thể dễ dàng nhận thấy rằng, ở mỗi lượt, thuật toán luôn chọn phần tử đầu tiên của phần chưa sắp xếp, sau đó tìm cách “nhét” phần tử này vào đúng vị trí mà nó nên có trong phần đã sắp xếp.

Vấn đề nằm ở chỗ làm thế nào để chèn phần tử vào đúng vị trí của nó để giữ được thứ tự của phần đã sắp xếp. Hãy cùng xem ví dụ ở bước 6 khi chúng ta cần chèn phần tử giá trị 3 vào giữa phần tử giá trị 2 và 4.

Như vậy, cách thực hiện khá đơn giản. Đem phần tử đó lần lượt so sánh với các phần tử của phần đã sắp xếp theo thứ tự. Nếu phần tử cần chèn nhỏ hơn thì đổi chỗ hai anh này. Tiếp tục thực hiện cho đến khi không còn tìm được anh nào nhỏ hơn nó nữa.

Thực thi thuật toán sắp xếp chèn trong C#

using System;
namespace P02_InsertionSort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Title = "Insertion Sort";
            var numbers = new[] { 9, 1, 5, 2, 4, 6, 3 };
            Sort(numbers);
            Console.ReadKey();
        }
        static void Swap<T>(T[] array, int i, int j)
        {
            T temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        static void Print<T>(T[] array)
        {
            Console.WriteLine(string.Join("\t", array));
        }
        static void Sort<T>(T[] array) where T : IComparable
        {
            for(var i = 1; i < array.Length; i++)
            {
                var j = i;
                while( j > 0 && array[j].CompareTo(array[j-1]) < 0)
                {
                    Swap(array, j, j - 1);
                    j--;
                }
                Console.ForegroundColor = ConsoleColor.Yellow;
                Console.Write($"Step {i}:\t");
                Console.ResetColor();
                Print(array);
                Console.WriteLine();
            }
        }
    }
}

Các kỹ thuật thực thi thuật toán sắp xếp chèn không có gì khác biệt so với sắp xếp chọn ở phần trước.

Hãy tự so sánh phần thực thi với phần minh họa ở trên để hiểu rõ hơn về thuật toán này.

Thuật toán này cũng có độ phức tạp là O(n²).

Link tải mã nguồn solution để ở phần cuối của bài học.

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

Sắp xếp nổi bọt (Bubble sort) cũng là một thuật toán sắp xếp rất đơn giản. Ý tưởng của thuật toán này là duyệt qua tất cả các cặp phần tử liền kề. Nếu phát hiện cặp phần tử nào sắp xếp sai trật tự thì sẽ đổi chỗ chúng. Với cách thức đó, qua mỗi lượt, phần tử có giá trị lớn nhất trong mảng sẽ được đẩy vào đúng vị trí chúng cần có. Qua đó có thể tưởng tượng là các phần tử, theo giá trị, sẽ lần lượt được đẩy dần lên đầu mảng vào đúng vị trí nó cần có.

Hãy cùng xem xét ví dụ sau:

Giả sử cần sắp xếp mảng {9, 1, 5, 2, 4, 6, 3} theo thứ tự tăng dần. Trình tự thực hiện thể hiện trong bảng dưới đây:

Lượt 1
9 1 5 2 4 6 3 Tráo 9 và 1 => 1 9 5 2 4 6 3
1 9 5 2 4 6 3 Tráo 9 và 5 => 1 5 9 2 4 6 3
1 5 9 2 4 6 3 Tráo 9 và 2 => 1 5 2 9 4 6 3
1 5 2 9 4 6 3 Tráo 9 và 4 => 1 5 2 4 9 6 3
1 5 2 4 9 6 3 Tráo 9 và 6 => 1 5 2 4 6 9 3
1 5 2 4 6 9 3 Tráo 9 và 3 => 1 5 2 4 6 3 9
1 5 2 4 6 3 9 => không còn gì để tráo nữa
Kết quả lượt 1: giá trị lớn nhất (9) được nổi lên đầu danh sách
1 5 2 4 6 3 9

Lượt 2
1 5 2 4 6 3 9
1 5 2 4 6 3 9
1 2 5 4 6 3 9
1 2 4 5 6 3 9
1 2 4 5 6 3 9
1 2 4 5 3 6 9
Kết quả lượt 2: giá trị lớn thứ hai (6) nổi lên vào vị trí thứ hai trong danh sách
1 2 4 5 3 6 9

Lượt 3
1 2 4 5 3 6 9
1 2 4 5 3 6 9
1 2 4 5 3 6 9
1 2 4 5 3 6 9
1 2 4 3 5 6 9
Kết quả lượt 3
1 2 4 3 5 6 9

Lượt 4
1 2 4 3 5 6 9
1 2 4 3 5 6 9
1 2 4 3 5 6 9
1 2 3 4 5 6 9
Kết quả lượt 4
1 2 3 4 5 6 9

Lượt 5: để ý là từ lượt này không có sự xáo trộn nào nữa nhưng thuật toán vẫn tiếp tục chạy
1 2 3 4 5 6 9
1 2 3 4 5 6 9
1 2 3 4 5 6 9
Kết quả lượt 5
1 2 3 4 5 6 9

Lượt 6
1 2 3 4 5 6 9
1 2 3 4 5 6 9
Kết quả lượt 6
1 2 3 4 5 6 9

Thực thi thuật toán sắp xếp nổi bọt trong C#

using System;
namespace P03_BubbleSort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Title = "Bubble Sort";
            var numbers = new[] { 9, 1, 5, 2, 4, 6, 3 };
            Sort(numbers);
            Console.ReadKey();
        }
        static void Swap<T>(T[] array, int i, int m)
        {
            T temp = array[i];
            array[i] = array[m];
            array[m] = temp;
        }
        static void Print<T>(T[] array)
        {
            Console.WriteLine(string.Join("\t", array));
        }
        static void Sort<T>(T[] array) where T : IComparable
        {
            for (var i = 0; i < array.Length-1; i++)
            {
                for (var j = 0; j < array.Length - i - 1; j++)
                {
                    if (array[j].CompareTo(array[j + 1]) > 0)
                    {                        
                        Swap(array, j, j + 1);
                    }
                }
                Console.ForegroundColor = ConsoleColor.Yellow;
                Console.Write($"Step {i+1}:\t");
                Console.ResetColor();
                Print(array);
                Console.WriteLine();
            }
        }
    }
}

Kết quả chạy chương trình như dưới đây

Tương tự như hai thuật toán trên, sắp xếp nổi bọt có độ phức tạp trong cả trường hợp xấu nhất và trung bình đều là O(n²).

Cải tiến thuật toán sắp xếp nổi bọt

Thuật toán sắp xếp nổi bọt nguyên gốc có một nhược điểm nhỏ: thuật toán sẽ cố gắng chạy hết các vòng lặp, ngay cả khi mảng đã được sắp xếp hoàn chỉnh.

Vấn đề này thể hiện rất rõ trong ví dụ minh họa ở trên. Chúng ta có thể để ý, đến lượt 4 thì mảng đã hoàn thành sắp xếp. Tuy nhiên, thuật toán vẫn cố chạy thêm lượt 5 và lượt 6. Trong khi hai lượt này không thực hiện thêm bất kỳ việc xáo trộn vị trí nào nữa.

Chúng ta đưa vào một cải tiến nhỏ để khi các phần tử đã được sắp xếp đúng thứ tự thì thuật toán sẽ dừng lại. Qua đó tiết kiệm được một số lượt tính toán.

using System;
namespace P03_BubbleSort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Title = "Bubble Sort";
            var numbers = new[] { 9, 1, 5, 2, 4, 6, 3 };
            Sort(numbers);
            Console.ReadKey();
        }
        static void Swap<T>(T[] array, int i, int m)
        {
            T temp = array[i];
            array[i] = array[m];
            array[m] = temp;
        }
        static void Print<T>(T[] array)
        {
            Console.WriteLine(string.Join("\t", array));
        }
        static void Sort<T>(T[] array) where T : IComparable
        {
            for (var i = 0; i < array.Length-1; i++)
            {
                var hasChanged = false;
                for (var j = 0; j < array.Length - i - 1; j++)
                {
                    if (array[j].CompareTo(array[j + 1]) > 0)
                    {
                        hasChanged = true;
                        Swap(array, j, j + 1);
                    }
                }
                if (!hasChanged)
                {
                    break;
                }
                Console.ForegroundColor = ConsoleColor.Yellow;
                Console.Write($"Step {i+1}:\t");
                Console.ResetColor();
                Print(array);
                Console.WriteLine();
            }
        }
    }
}

Khi so sánh với kết quả trên có thể thấy chúng ta đã giảm bớt được hai lượt thực hiện.

Thuật toán sắp xếp nhanh (Quicksort)

Thuật toán sắp xếp nhanh (quicksort) là một trong những thuật toán sắp xếp phổ biến và hiệu quả nhất. Nếu so sánh với 3 thuật toán sắp xếp đã trình bày thì quicksort có hiệu suất cao hơn cả. Khác biệt với các thuật toán trên, quicksort hoạt động theo nguyên tắc “chia để trị”. Về mặt thực thi, quicksort cũng phức tạp hơn và phải dùng đến đệ quy.

Thuật toán

Bước 1. Chọn một giá trị trục (pivot) trên mảng.

Giá trị trục (pivot) đóng vai trò là một giá trị trung gian để phân vùng mảng (trong bước tiếp theo). Pivot có thể chọn là giá trị của phần tử bất kỳ trong mảng. Tuy nhiên, để đơn giản, pivot thường được chọn là giá trị của phần tử đầu tiên, phần tử cuối cùng, hoặc phần tử nằm giữa mảng. Vì mảng sẽ được phân vùng nên việc chọn vị trí ban đầu của pivot không có gì khác biệt nhau.

Bước 2. Sử dụng pivot để phân vùng mảng

Phân vùng (partition) là một thuật toán đơn giản có nhiệm vụ phân chia mảng thành hai vùng: một vùng chỉ chứa các giá trị nhỏ hơn pivot, gọi là vùng lower; một vùng chỉ chứa các giá trị lớn hơn pivot, gọi là vùng upper. Bản thân giá trị pivot cũng được đẩy về vị trí giao nhau giữa hai vùng này (mặc dù ban đầu pivot có thể ở đầu, cuối, hoặc ở giữa mảng).

Thuật toán phân vùng hoạt động theo logic sau: (1) duyệt xuôi từ đầu mảng để tìm giá trị lớn hơn pivot; (2) duyệt ngược từ cuối mảng để tìm giá trị nhỏ hơn pivot; (3) nếu tìm thấy cả hai thì đổi chỗ hai phần tử này với nhau; (4) lặp lại (1)-(2)-(3) cho đến khi chiều duyệt xuôi và chiều duyệt ngược gặp nhau.

Vị trí giao nhau đồng thời sẽ là vị trí mới của giá trị pivot, là nơi phân tách ra phần lower và phần upper của mảng.

Bước 3. Xem vùng lower là một mảng riêng, áp dụng lại bước 1, 2 và 3 cho mảng này; Xem vùng upper là một mảng riêng, áp dụng lại bước 1, 2 và 3 cho mảng này.

Lưu ý rằng, bước 3 này là bước gọi đệ quy (tự nó gọi chính nó). Quá trình gọi này tiếp tục cho đến khi không thể phân chia ra các mảng con được nữa.

Minh họa hoạt động của thuật toán Quicksort

Để minh họa, hãy cùng xem cách Quicksort thực hiện trên mảng {-11, 12, -42, 0, 1, 90, 68, 6, -9}. Trong ví dụ này, pivot được chọn là giá trị của phần tử đầu tiên.

Dưới đây là một cách khác để sắp xếp mảng trên. Pivot giờ sẽ là phần tử ở giữa (median) của mảng, thay vì phần tử đầu tiên.

Thực thi thuật toán Quicksort trong C#

Dưới đây là full mã nguồn của project thực thi thuật toán Quicksort trong C#.

using System;
namespace P04_QuickSort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Title = "Quick Sort";
            var numbers = new[] { -11, 12, -42, 0, 1, 90, 68, 6, -9 };
            Console.WriteLine("Original");
            Print(numbers);
            Sort(numbers);
            Console.WriteLine("Sorted:");
            Print(numbers);
            Console.ReadKey();
        }
        static void Swap<T>(T[] array, int i, int m)
        {
            T temp = array[i];
            array[i] = array[m];
            array[m] = temp;
        }
        static void Print<T>(T[] array)
        {
            Console.WriteLine(string.Join("\t", array));
        }
        static int Partition<T>(T[] array, int lower, int upper) where T : IComparable
        {
            var i = lower;
            var j = upper;
            T pivot = array[lower];
            do
            {
                while (array[i].CompareTo(pivot) < 0) i++;
                while (array[j].CompareTo(pivot) > 0) j--;
                if (i >= j) break;
                Swap(array, i, j);
            } while (i <= j);
            return j;
        }
        static void SubSort<T>(T[] array, int lower, int upper) where T : IComparable
        {
            if (lower < upper)
            {
                var p = Partition(array, lower, upper);
                SubSort(array, lower, p);
                SubSort(array, p + 1, upper);
            }
        }
        static void Sort<T>(T[] array) where T : IComparable
        {
            SubSort(array, 0, array.Length - 1);
        }
    }
}

Trong project này chúng ta vẫn tiếp tục sử dụng lại hai phương thức Swap và Print đã thực hiện trong các project trước đây. Chúng ta bổ sung thêm hai phương thức mới: Partition và SubSort.

Phương thức Partition thực thi thuật toán phân vùng như đã mô tả ở phần trên.

Phương thức SubSort thực hiện theo kiểu đệ quy quá trình (1) phân vùng mảng đầu vào, (2) gọi lại chính nó để thực hiện cho vùng lower, (3) gọi lại chính nó để thực hiện cho vùng upper. Quá trình đệ quy chỉ kết thúc khi không thể phân chia thành lower và upper nữa, tức là khi mỗi mảng con chỉ còn lại một phần tử.

Phương thức Sort lúc này chỉ còn có nhiệm vụ cung cấp mảng gốc cho SubSort.

Thuật toán Quicksort có độ phức tạp trung bình là O(n log(n)) và O(n²) cho trường hợp xấu nhất.

Kết luận

Trong bài học rất dài này chúng ta đã cùng xem xét chi tiết các thuật toán sắp xếp cơ bản trên mảng một chiều và cách thực thi của chúng trên C#.

Cũng xin nói luôn, việc xem xét các thuật toán này và cách thực thi trên C# mang tính học thuật nhiều hơn là tính ứng dụng. Lý do là bản thân C# và .NET Framework đã hỗ trợ sẵn việc sắp xếp trên dữ liệu tập hợp thông qua thư viện LINQ.

Trong bài học tiếp theo chúng ta sẽ tiếp tục làm quen với danh sách trong C#.

Chúc bạn học tốt!

[wpdm_package id=’10265′]

+ Nếu bạn thấy site hữu ích, trước khi rời đi hãy giúp đỡ site bằng một hành động nhỏ để site có thể phát triển và phục vụ bạn tốt hơn.
+ Nếu bạn thấy bài viết hữu ích, hãy giúp chia sẻ tới mọi người.
+ Nếu có thắc mắc hoặc cần trao đổi thêm, mời bạn viết trong phần thảo luận cuối trang.
Cảm ơn bạn!