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.
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 doanh nghiệp với Java. Khóa học có giá chỉ 400K, 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 chị Thu, trợ lý anh Tuyền để hỗ trợ thanh toán qua mã QR ngân hàng Việt Nam, fb: https://www.facebook.com/Thule.59
Anh Tuyền, tác giả khóa học, là cựu sinh viên chương trình đào tạo kĩ sư tài năng của đại học Bách Khoa Hà Nội với hơn 5 năm kinh nghiệm đi làm thực tế doanh nghiệp và cũng là Founder website vietjack.com, web giáo dục phổ biến nhất Việt Nam hiện tại (năm 2024). Java cũng là ngôn ngữ lập trình dễ đi xin việc nhất hiện tại, với mức lương cao, hãy nâng cao kiến thức IT của bản thân mình vì một Việt Nam giàu mạnh.
Loạt bài hướng dẫn của chúng tôi dựa một phần trên nguồn tài liệu của: Tutorialspoint.com
Bài học Bài tập C# phổ biến tại vietjack.com:
