Реализация карманной (блочной) сортировки - C#

Узнай цену своей работы

Формулировка задачи:

Пытаюсь реализовать на C# карманную сортировку. Суть алгоритма в том, чтобы разложить входной масив из N елементов в N карманов на отрезке [0, 1) Кормен предлагает реализацию с помощью списков. Я пока что так не умею, поэтому решил использовать двумерный рванный массив. Однако, я не могу понять сам этап разложения. Ни википедия, ни кормен, мне так и не подсказали, по какому алгоритму следует записывать эти числа в спомагательный массив. Или может это я такой тугой?
void BucketSort(int[] A)
        {
            int k = 0;
            int n = A.Length;
            int [][] B = new int[n][];
            
            for (int i = 0; i <n; i++)
                //нужно вставить А[i] в масcив B
            for (int i = 0; i<n;i++)
                Array.Sort(B[i]);
 
            for (int i = 0; i < n; i++)
                for (int j = 0; j < B[i].Length; j++)
                    A[k++] = B[i][j++];
        }

Решение задачи: «Реализация карманной (блочной) сортировки»

textual
Листинг программы
using System;
using System.Collections.Generic;
 
namespace ConsoleApp1
{
    class Program
    {
        static void BucketSort(int[] a)
        {
            // Примем, что количество корзин равно количеству элементов в массиве-источнике.
            // Тогда:
            // массив корзин
            List<int>[] aux = new List<int>[a.Length];
 
            // каждую корзину проинициализировать
            for (int i = 0; i < aux.Length; ++i)
                aux[i] = new List<int>();
 
            // найти диапазон значений в массиве-источнике
            int minValue = a[0];
            int maxValue = a[0];
 
            for (int i = 1; i < a.Length; ++i)
            {
                if (a[i] < minValue)
                    minValue = a[i];
                else if (a[i] > maxValue)
                    maxValue = a[i];
            }
 
            // эта величина будет использоваться a.Length раз, поэтому имеет смысл её сохранить.
            double numRange = maxValue - minValue;
 
            for (int i = 0; i < a.Length; ++i)
            {
                // вычисление индекса корзины
                int bcktIdx = (int)Math.Floor((a[i] - minValue) / numRange * (aux.Length - 1));
 
                // добавление элемента в соответствующую корзину
                aux[bcktIdx].Add(a[i]);
            }
 
            // сортировка корзин. Здесь я, для упрощения себе писанины, использую библиотечную сортировку
            for (int i = 0; i < aux.Length; ++i)
                aux[i].Sort();
 
            // собираем отсортированные элементы обратно в массив-источник
            int idx = 0;
 
            for (int i = 0; i < aux.Length; ++i)
            {
                for (int j = 0; j < aux[i].Count; ++j)
                    a[idx++] = aux[i][j];
            }
        }
 
        static void Main()
        {
            int[] arr = new int[15];
            Random rnd = new Random();
 
            for (int i = 0; i < arr.Length; ++i)
                arr[i] = rnd.Next(-99, 100);
 
            Console.WriteLine(String.Join(" ", arr));
            BucketSort(arr);
            Console.WriteLine(String.Join(" ", arr));
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 3.923 из 5