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 tất cả 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 ₵#. Dù rằng có nhiều thuật toán khác nhau trên kết cấu mảng, sắp xếp là nhóm thuật toán bổ biến nhất. Tất cả chúng ta sẽ cùng cân nhắc & nhận xét những thuật toán sắp xếp phổ biến, 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 & khó tiêu hóa, hãy bookmark nó lại (Ctrl+?) để chầm chậm 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 dễ dàng nhất. Nếu bạn chưa học bài bản về kết cấu dữ liệu & thuật toán, khi được yêu cầu sắp xếp mảng, tôi tin rằng đa số 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ử tất cả chúng ta cần sắp xếp một mảng (1 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 1 chiều. Nó phân tách mảng thành hai phần: (1) phần đã sắp xếp, & (2) phần chưa sắp xếp. Ở công đoạn bắt đầ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 thể 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 & đổi chỗ nó với phần tử trước hết của phần chưa sắp xếp. Trong lượt trước hết, thuật toán hiển nhiên sẽ tìm thấy phần tử nhỏ nhất mảng & đổi chỗ nó với phần tử trước hết của mảng (cũng là của phần chưa sắp xếp). Vì vậy, phần tử trước hết của mảng sau lượt 1 sẽ là phần tử nhỏ nhất.

Cũng để mắt 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 to hơn phần tử lớn nhất của phần đã sắp xếp. Khi này, ta có thể mang 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ử trước hết 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.

Công cuộc sẽ tiếp diễn như thế 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 bí quyết nghĩ suy thông thường của các bạn.

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

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

Giả sử tất cả chúng ta có mảng {10, 3, 1, 7, 9, 2, 0}. Giờ tất cả 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 làm.

Minh họa hoạt động của thuật toán sắp xếp chọ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ử đó là ɱ=6 (phần tử giá trị 0 có chỉ số là 6). Phần tử trước hết của vùng chưa sắp xếp lúc này cũng là phần tử trước hết của mảng, có chỉ số ι=0. Phần tử ɱ & ι giờ sẽ đổi chỗ cho nhau. Mở rộng ranh giới phần đã sắp xếp ra trước phần tử trước hết của vùng chưa sắp xếp. Như thế, 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 khởi đầu lượt 2, ranh giới đã mở rộng ra sau phần tử trước hết 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, ɱ = 2) & đổi chỗ với phần tử trước hết của vùng chưa sắp xếp (ι=1).

Khi khởi đầ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 & 1). Lại tìm phần tử nhỏ nhất của vùng chưa sắp xếp (min = 2, ɱ = 5) & đổi chỗ với phần tử trước hết của vùng chưa sắp xếp (ι = 2).

Công cuộc này cứ lặp lại như thế cho đến lượt 6, khi vùng chưa sắp xếp chỉ còn hai phần tử (9 & 10). Đơn giản tìm được ɱ = 5, min = 9, & ι = 5. Đổi chỗ cho nhau xong là thuật toán giải quyết bổ phận.

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

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 ₵# khá dễ dàng. 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 Swapvàlt;Tvàgt;(Ƭ[] array, int ι, int ɱ)
        {
            Ƭ temp = array[i];
            array[i] = array[m];
            array[m] = temp;
        }

        static void Printvàlt;Tvàgt;(Ƭ[] array)
        {
            Console.WriteLine(string.Join("t", array));
        }

        static void Sortvàlt;Tvàgt;(Ƭ[] array) where Ƭ : IComparable
        {
            for (int ι = 0; ι < array.Length - 1; ι++)
            {
                int ɱ = ι;
                Ƭ minValue = array[i];
                for (int j = ι + 1; j < array.Length; j++)
                {
                    if (array[j].CompareTo(minValue) < 0)
                    {
                        ɱ = j;
                        minValue = array[j];
                    }
                }
                Swap(array, ι, ɱ);

                Console.ForegroundColor = ConsoleColor.Yellow;
                Console.WriteLine($"Step {i+1}: i = {i}, m = {m}, min = {minValue}");
                Console.ResetColor();

                Print(array);
                Console.WriteLine();
            }
        }
    }
}

Kết quả chạy chương trình với thuật toán sắp xếp chọn

Xem Thêm  Cách sử dụng HTML để mở liên kết trong tab mới - html bấm mở tab mới

So sánh với chẳng hạn 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 bí quyết 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ỹ nội dung 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 độ cầu kỳ là Σ(n2). Thực tiễn qua code tất cả chúng ta đơn giản nhận ra 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.

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

Cũng giống như sắp xếp chọn, sắp xếp chèn cũng hoạt động trên mảng 1 chiều & là một thuật toán khá dễ dàng. 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ự độc đáo 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ử trước hết của phần chưa sắp xếp & tìm cách chèn phần tử mới này vào đúng thứ tự nó cần phải 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 bé hơn thì sẽ đổi địa điểm với phần tử đang so sánh.

Công cuộc 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

Tất cả 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 1 chiều {9, 1, 5, 2, 4, 6, 3}. Công cuộc được trổ tài qua hình dưới đây.

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

Có thể đơn giản nhận ra rằng, ở mỗi lượt, thuật toán luôn chọn phần tử trước hết 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 địa điểm mà nó nên có trong phần đã sắp xếp.

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

Minh họa cách chèn phần tử vào địa điểm thích hợp trong thuật toán sắp xếp chèn

Như thế, cách thực hiện khá dễ dàng. Đ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 bé 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 bé hơn nó nữa.

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

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 Swapvàlt;Tvàgt;(Ƭ[] array, int ι, int j)
        {
            Ƭ temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        static void Printvàlt;Tvàgt;(Ƭ[] array)
        {
            Console.WriteLine(string.Join("t", array));
        }

        static void Sortvàlt;Tvàgt;(Ƭ[] array) where Ƭ : IComparable
        {
            for(var ι = 1; ι < array.Length; ι++)
            {
                var j = ι;
                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();
            }
        }
    }
}

Kết quả chạy chương trình cho thuật toán sắp xếp chèn

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

Xem Thêm  Cách gọi một phương thức trong Java - gọi phương thức trong java

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

Thuật toán này cũng có độ cầu kỳ là Σ(n2).

Backlink 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 dễ. Sáng kiến của thuật toán đó là duyệt qua toàn bộ 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 bí quyết đó, qua mỗi lượt, phần tử có giá trị lớn nhất trong mảng sẽ được đẩy vào đúng địa điểm chúng cần phải 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 địa điểm nó cần phải có.

Hãy cùng cân nhắc chẳng hạn 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 trổ tài trong bảng dưới đây:

Lượt 1
9 1 5 2 4 6 3 Tráo 9 & 1 => 1 9 5 2 4 6 3
1 9 5 2 4 6 3 Tráo 9 & 5 => 1 5 9 2 4 6 3
1 5 9 2 4 6 3 Tráo 9 & 2 => 1 5 2 9 4 6 3
1 5 2 9 4 6 3 Tráo 9 & 4 => 1 5 2 4 9 6 3
1 5 2 4 9 6 3 Tráo 9 & 6 => 1 5 2 4 6 9 3
1 5 2 4 6 9 3 Tráo 9 & 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 mục
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 địa điểm thứ hai trong danh mục
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: để mắt là từ lượt này không có sự đảo lộ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 ₵#

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 Swapvàlt;Tvàgt;(Ƭ[] array, int ι, int ɱ)
        {
            Ƭ temp = array[i];
            array[i] = array[m];
            array[m] = temp;
        }

        static void Printvàlt;Tvàgt;(Ƭ[] array)
        {
            Console.WriteLine(string.Join("t", array));
        }

        static void Sortvàlt;Tvàgt;(Ƭ[] array) where Ƭ : IComparable
        {
            for (var ι = 0; ι < array.Length-1; ι++)
            {
                for (var j = 0; j < array.Length - ι - 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

Kết quả chạy chương trình sắp xếp nổi bọt

Cũng giống như hai thuật toán trên, sắp xếp nổi bọt có độ cầu kỳ trong cả trường hợp xấu nhất & bình quân đều là Σ(n2).

Tái tạo 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 khuyết điểm nhỏ: thuật toán sẽ phấn đấu 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 trổ tài rất rõ trong chẳng hạn minh họa ở trên. Tất cả chúng ta có thể để mắt, đến lượt 4 thì mảng đã giải quyết sắp xếp. Không những thế, thuật toán vẫn cố chạy thêm lượt 5 & lượt 6. Trong lúc hai lượt này không thực hiện thêm bất kỳ việc đảo lộn địa điểm nào nữa.

Tất cả chúng ta mang vào một tôn tạo 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 Swapvàlt;Tvàgt;(Ƭ[] array, int ι, int ɱ)
        {
            Ƭ temp = array[i];
            array[i] = array[m];
            array[m] = temp;
        }

        static void Printvàlt;Tvàgt;(Ƭ[] array)
        {
            Console.WriteLine(string.Join("t", array));
        }

        static void Sortvàlt;Tvàgt;(Ƭ[] array) where Ƭ : IComparable
        {
            for (var ι = 0; ι < array.Length-1; ι++)
            {
                var hasChanged = false;
                for (var j = 0; j < array.Length - ι - 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();
            }
        }
    }
}

Thuật toán sắp xếp nổi bọt “cải tiến”

Khi so sánh với kết quả trên có thể thấy tất cả chúng ta đã giảm thiểu đượ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 thông dụng & 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ó năng suất cao hơn hết. Độc đáo với các thuật toán trên, quicksort hoạt động theo phép tắc “chia để trị”. Về mặt thực thi, quicksort cũng cầu kỳ hơn & 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 kế tiếp). Pivot có thể chọn là giá trị của phần tử bất kỳ trong mảng. Không những thế, để dễ dàng, pivot thường được chọn là giá trị của phần tử trước hết, 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 địa điểm ban đầu của pivot không có gì độc đáo nhau.

Xem Thêm  nút - nút trên hình ảnh bootstrap 4

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 dễ dàng có bổ phận phân tách mảng thành hai vùng: một vùng chỉ chứa các giá trị bé hơn pivot, gọi là vùng lower; một vùng chỉ chứa các giá trị to hơn pivot, gọi là vùng upper. Bản thân giá trị pivot cũng được đẩy về địa điểm giao nhau giữa hai vùng này (mặc dầu 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ị to hơn pivot; (2) duyệt ngược từ cuối mảng để tìm giá trị bé hơn pivot; (3) nếu tìm ra 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 & chiều duyệt ngược gặp nhau.

Địa điểm giao nhau song song sẽ là địa điểm mới của giá trị pivot, là nơi phân chia ra phần lower & phần upper của mảng.

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

Note rằng, bước 3 đó là bước gọi đệ quy (tự nó gọi chính nó). Công cuộc gọi này tiếp tục cho đến khi chẳng thể phân tách 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 chẳng hạn này, pivot được chọn là giá trị của phần tử trước hết.

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

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ử trước hết.

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

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

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 Swapvàlt;Tvàgt;(Ƭ[] array, int ι, int ɱ)
        {
            Ƭ temp = array[i];
            array[i] = array[m];
            array[m] = temp;
        }

        static void Printvàlt;Tvàgt;(Ƭ[] array)
        {
            Console.WriteLine(string.Join("t", array));
        }

        static int Partitionvàlt;Tvàgt;(Ƭ[] array, int lower, int upper) where Ƭ : IComparable
        {
            var ι = lower;
            var j = upper;
            Ƭ pivot = array[lower];
            do
            {
                while (array[i].CompareTo(pivot) < 0) ι++;
                while (array[j].CompareTo(pivot) > 0) j--;
                if (ι >= j) break;
                Swap(array, ι, j);
            } while (ι <= j);
            return j;
        }

        static void SubSortvàlt;Tvàgt;(Ƭ[] array, int lower, int upper) where Ƭ : IComparable
        {
            if (lower < upper)
            {
                var ρ = Partition(array, lower, upper);
                SubSort(array, lower, ρ);
                SubSort(array, ρ + 1, upper);
            }
        }

        static void Sortvàlt;Tvàgt;(Ƭ[] array) where Ƭ : IComparable
        {
            SubSort(array, 0, array.Length - 1);
        }
    }
}

Trong project này tất cả chúng ta vẫn tiếp tục sử dụng lại hai bí quyết Swap & Print đã thực hiện trong các project trước đó. Tất cả chúng ta bổ sung thêm hai bí quyết mới: Partition & SubSort.

Cách thức Partition thực thi thuật toán phân vùng như đã miêu tả ở phần trên.

Cách thức SubSort thực hiện theo kiểu đệ quy tiến 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. Công cuộc đệ quy chỉ chấm dứt khi chẳng thể phân tách thành lower & upper nữa, tức là khi mỗi mảng con chỉ sót lại một phần tử.

Cách thức Sort giờ đây chỉ còn tồn tại bổ phận phân phối mảng gốc cho SubSort.

Thuật toán Quicksort có độ cầu kỳ bình quân là Σ(ɳ log(ɳ)) & Σ(n2) cho trường hợp xấu nhất.

Tổng kết

Trong bài học rất dài này tất cả chúng ta đã cùng cân nhắc cụ thể các thuật toán sắp xếp căn bản trên mảng 1 chiều & cách thực thi của chúng trên ₵#.

Cũng xin nói luôn, việc cân nhắc các thuật toán này & cách thực thi trên ₵# đưa tính học thuật nhiều hơn là tính vận dụng. Nguyên nhân là bản thân ₵# & .NET Framework đã trợ giúp 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 kế tiếp tất cả chúng ta sẽ tiếp tục làm quen với danh mục trong ₵#.

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

+ Nếu bạn thấy site hữu hiệu, trước khi rời đi hãy trợ giúp site bằng một hành động nhỏ để site có thể lớn mạnh & phục vụ bạn tốt hơn.
+ Nếu bạn thấy nội dung hữu hiệu, hãy giúp chia sẻ tới mọi người.
+ Nếu có khúc mắc hoặc cần thỏa thuận thêm, mời bạn viết trong phần bàn bạc dưới cùng của trang.
Cảm ơn bạn!

Viết một bình luận