Реализация карманной (блочной) сортировки - 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)); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д