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 + 1

trong đó:
   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ả:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Các bạn có thể mua thêm khóa học JAVA CORE ONLINE VÀ ỨNG DỤNG cực hay, giúp các bạn vượt qua các dự án trên trường và đi thực tập Java. Khóa học có giá chỉ 300K, nhằm ưu đãi, tạo điều kiện cho sinh viên cho thể mua khóa học.

Nội dung khóa học gồm 16 chuơng và 100 video cực hay, học trực tiếp tại https://www.udemy.com/tu-tin-di-lam-voi-kien-thuc-ve-java-core-toan-tap/ Bạn nào có nhu cầu mua, inbox trực tiếp a Tuyền, cựu sinh viên Bách Khoa K53, fb: https://www.facebook.com/tuyen.vietjack

Follow facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.