Shell Sort trong C#

Bài tập C#: Shell Sort

Viết chương trình C# minh họa giải thuật Shell Sort.

Shell Sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp xếp chèn (Insertion Sort). Giải thuật này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn bên trái).

Đầu tiên, giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. Khoảng cách này còn được gọi là khoảng (interval) – là số vị trí từ phần tử này tới phần tử khác. Khoảng này được tính dựa vào công thức Knuth như sau:

h = h * 3 + 1trong đó:
   h là Khoảng (interval) với giá trị ban đầu là 1

Để tham khảo chi tiết về lý thuyết cũng như hình ảnh minh họa cho giải thuật Shell Sort, mời bạn tham khảo chương: Shell Sort trong C có trên trang của chúng mình.

Chương trình C#

Dưới đây là chương trình C# minh họa giải thuật Shell Sort trong C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text; namespace VietJackCsharp
{
    class TestCsharp
    {
        static void Main(string[] args)
        {
            int[] arr = new int[] { 5, -4, 11, 0, 18, 22, 67, 51, 6 };
            int n;            n = arr.Length;
            Console.WriteLine("Shell Sort trong C#");
            Console.WriteLine("---------------------------------");            Console.WriteLine("In mang ban dau:");
            in_cac_phan_tu_mang(arr);
            shellSort(arr, n);
            Console.WriteLine("\nIn mang da qua sap xep:");
            in_cac_phan_tu_mang(arr);            Console.ReadKey();
        }        static void shellSort(int[] arr, int kich_co_mang)
        {
            int i, j, inc, temp;
            inc = 3;
            while (inc > 0)
            {
                for (i = 0; i < kich_co_mang; i++)
                {
                    j = i;
                    temp = arr[i];
                    while ((j >= inc) && (arr[j - inc] > temp))
                    {
                        arr[j] = arr[j - inc];
                        j = j - inc;
                    }
                    arr[j] = temp;
                }
                if (inc / 2 != 0)
                    inc = inc / 2;
                else if (inc == 1)
                    inc = 0;
                else
                    inc = 1;
            }
        }        static void in_cac_phan_tu_mang(int[] arr)
        {
            foreach (var phan_tu in arr)
            {
                Console.Write(phan_tu + " ");
            }
            Console.Write("\n");
        }  
    }
}

Nếu bạn không sử dụng lệnh Console.ReadKey(); thì chương trình sẽ chạy và kết thúc luôn (nhanh quá đến nỗi bạn không kịp nhìn kết quả). Lệnh này cho phép chúng ta nhìn kết quả một cách rõ ràng hơn.

Kết quả chương trình C#

Biên dịch và chạy chương trình C# trên sẽ cho kết quả: