Sortir Gabung Generik dalam C# .NET

Niels Swimberghe


– .NET

Ikuti saya di Indonesia, belikan aku kopi

Awal tahun ini, saya memutuskan untuk memoles algoritme dan pengetahuan struktur data saya. Saya mengambil dua kursus hebat ini (1, 2) di PluralSight oleh Robert Horvick.
Untuk mempraktikkan apa yang saya pelajari dalam kursus ini, saya memutuskan untuk membuat versi generik dari berbagai algoritma dan struktur data.

Apa yang saya maksud dengan versi generik? Jenis kursus ini selalu menggunakan bilangan bulat atau string untuk mendemonstrasikan algoritme. Alih-alih menggunakan tipe data primitif itu, saya mengimplementasikan kembali algoritme dan struktur data menggunakan parameter tipe generik C#.

Berikut adalah aplikasi konsol dengan metode generik MergeSort untuk melakukan pengurutan gabungan pada enumerable:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var randomNumbers = new int[] { 5, 4, 5, 7, 6, 9, 4, 1, 1, 3, 4, 50, 56, 41 };

        var sortedNumbers = MergeSort(randomNumbers.AsEnumerable());
        Console.WriteLine("Merge Sort:");
        PrintList(sortedNumbers);
        Console.ReadKey();
        Console.Clear();
    }

    private static IEnumerable<T> MergeSort<T>(IEnumerable<T> list) where T : IComparable
    {
        T[] items = list.ToArray();
        return InternalMergeSort(items);
    }

    private static T[] InternalMergeSort<T>(T[] items) where T : IComparable
    {
        int listLength = items.Length;

        if (listLength == 1)
        {
            return items;
        }

        int median = listLength / 2;

        T[] left = new T[median];
        T[] right = new T[listLength - median];
        Array.Copy(items, left, left.Length);
        Array.Copy(items, median, right, 0, right.Length);

        InternalMergeSort(left);
        InternalMergeSort(right);

        return Merge(items, left, right);
    }

    private static T[] Merge<T>(T[] items, T[] left, T[] right) where T : IComparable
    {
        int leftIndex = 0;
        int rightIndex = 0;

        int leftLength = left.Length;
        int rightLength = right.Length;
        int totalItems = leftLength + rightLength;

        for (int targetIndex = 0; targetIndex < totalItems; targetIndex++)
        {
            if(leftIndex >= leftLength)
            {
                items[targetIndex] = right[rightIndex];
                rightIndex++;
            }
            else if(rightIndex >= right.Length)
            {
                items[targetIndex] = left[leftIndex];
                leftIndex++;
            }
            else if(left[leftIndex].CompareTo(right[rightIndex]) < 0)
            {
                items[targetIndex] = left[leftIndex];
                leftIndex++;
            }
            else
            {
                items[targetIndex] = right[rightIndex];
                rightIndex++;
            }
        }

        return items;
    }

    private static void PrintList<T>(IEnumerable<T> list)
    {
        foreach (var item in list)
        {
            Console.WriteLine(item);
        }
    }
}

Dengan menggunakan parameter tipe generik dengan batasan bahwa tipe harus mengimplementasikan IComparable antarmuka, Anda dapat melakukan algoritme pengurutan gabungan tanpa mengetahui jenis persisnya yang sedang Anda kerjakan.

Jika Anda ingin memahami logika di balik algoritma merge sort, saya sarankan untuk memeriksa kursus yang disebutkan sebelumnya. Ada juga banyak sumber daya hebat lainnya di luar sana online!

Penafian: Kode ini berfungsi, tetapi hanya dikembangkan untuk kepentingan latihan. Gunakan dengan risiko Anda sendiri atau cukup gunakan perpustakaan penyortiran. Jika Anda melihat beberapa ruang untuk perbaikan, kemungkinan besar ada, saya siap mendengarkan ~

Topik

Pengarang

Niels Swimberghe

Niels Swimberghe

Niels Swimberghe adalah Pengembang Full Stack Belgia yang memecahkan masalah dan memberikan nilai kepada pelanggan menggunakan teknologi .NET untuk sistem back-end, dan teknologi JavaScript modern untuk front-end.

Apakah artikel ini bermanfaat? Ikuti saya di
Indonesia, belikan saya kopi, tambahkan blog ini ke pembaca feed Anda!