Подсчет сортировки: минимум, максимум и частота массива

Question

Я хочу изменить сортировку подсчета, чтобы эффективно обслуживать диапазон значений, где минимальное значение не равно 0. Мои проблемы с кодом - найти минимальное значение, если оно не равно 0, минимальное значение должно быть, например,, если диапазон списка составляет 100 000 - 110 000, минимальное значение равно 100 000. Но частота (количество) массива счетчиков НЕ МОЖЕТ быть 100 001. Мой код в настоящее время вообще не работает или не выполняет сортировку для списка из 20 000целые числа и числа находятся в диапазоне от 1000 до 9999.

Работает, когда min равно 0, но это не то, как сортировочная сортировка предназначена для эффективной реализации ...

public static  int findMinValue(int[] List)
        {

            int min;
            min = List[0];
            return min;
        }

        static void countingsort(int[] List, int max)
        /* pre:  List has .Length integers in it. The maximum value in the list is max.
        * post: Using the countingsort algorithm, sort the list of integers into ascending order. */
        {

            // ADD CODE FOR METHOD countingsort BELOW
            Stopwatch timer = new Stopwatch();
                timer.Start();
            int[] countArray = new int[max + 1];
            int min = findMinValue(countArray);
            for (int i = 0; i <= max; i++)
            {
                countArray[i] = 0;

            }
            for (int x = 0; x < List.Length; x++)
            {
                countArray[List[x]] = countArray[List[x]] + min;
                // or countArray[List[x]]++;


            }
            int index = 0;
            for (int y = 0; y <= max; y++)
            {
                //List[y] = countArray[y];
                for (int j = 0; j < countArray[y]; j++)
                {
                    List[index] = y;
                    index = index + 1;
                    // or index++
                }
            }
            Display(List);
            DisplayCount(countArray);
            timer.Stop();

            Console.WriteLine("Time Taken for Basic Selection Sort is {0} milliseconds", timer.ElapsedMilliseconds);



        }
        public static void DisplayCount(int[] Array)
        {
            int count = 0;
            for (int i = 0; i < Array.Length; i++)
            {
                count++;
            }
            Console.WriteLine("Elements in count array is {0} ", count);
        }

Список несортируется и отображает элементы в массиве count как 10 000.

Answer 1

Вот что я заметил:

1. Функция поиска минимального значения берет первое значение из массива, а не фактический минимум. Вы можете использовать List.Min();.

2. В декларации countArray вы должны использовать разницу между максимальным и минимальным значениями + 1 в качестве размера.

3. Вам необходимо сместить индекс при доступе к countArray с найденным минимальным значением, поскольку элемент индекса 0 должен соответствовать минимальному значению, а не 0.

4. При переборе countArray в for (int i = 0; i <= max; i++) не следует использовать максимальное значение в условии. Если минимум не равен 0, он будет отличаться от размера массива.

5. В функции отображения количества вы можете просто использовать Array.Length, нет необходимости перебирать массив.

Я не буду предоставлять вам код для самого алгоритма, поскольку это, очевидно, задание Uni / College / HS.