Сортировка квадратичным выбором C#

486

21 декабря 2016, 01:13

Есть задание: Сгенерировать массив случайных чисел от 100-1001, и отсортировать его методом квадратичного выбора. Написал начало, которое считает сколько должно быть групп и элементов в каждой групе. Но дальше застрял.. не понимаю как разбить этот массив на группы , искать минимум в каждой группе и переносить в другой массив. Нашел в интернете пример этой сортировки на паскале, но она нереально длинная ( хотя так не должно бытъ ), и я не вьезжаю в паскаль ( нас начинают учить сразу на си шарпе ) .

Идея алгоритма: Массив А из N элементов, разделяется на "корень из N" групп, по "корень из N" элементов в каждой группе. Находится наименьший элемент в каждой группе и помещается в некоторый вспомогательный массив В. Далее во вспомогательном массиве находится минимальный элемент. Данный элемент заносится на следующую позицию выходного массива С, и в массиве В заменяется на следующий по величине элемент из этой группы массива А, из которой он поступил. Снова находится наименьший элемент во вспомогательном массиве. Этот элемент - второй по величине в исходном массиве. Процесс повторяется до тех пор, пока ис ходных массив не будет отсортирован. В данном методе используются 3 массива, А - исходный, В - вспомогательный, С - выходной. Для поиска в группе следующего по величине элемента нужно минимальный элемент заменить на очень большое число ( фиктивный максимум ) , например при пятизначиных элементах - на число 99999.

    static void Main()
    {
        int n;
        Console.WriteLine("Please enter array size");
        n = Convert.ToInt32(Console.ReadLine());
        Random rnd = new Random();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        Console.WriteLine("Unsorted array:");
        for (int i = 0; i < n; i++)
            Console.Write("{0,4}", a[i] = rnd.Next(100, 1001));
        double lastelements = 0;
        double elements = 0;
        double group = Math.Sqrt(n);
        //Определение грпп, количества элементов в них
        if (group % 1 == 0)
        {
            group = Convert.ToInt32(group);
            elements = group;
            //Для самопроверки
            Console.WriteLine();
            Console.WriteLine("Will be " + group + " groups, " + elements + " elements in each.");
        }
        else
        {
            if (group % 1 > 0.5)
            {
                //остаток > 0.5
                elements = Math.Truncate(group)+1;
                group = Math.Truncate(group) + 1;          
                lastelements = n - group*(group - 1);
                //Для самопроверки
                Console.WriteLine();
                Console.WriteLine("Will be " + group + " groups, " + elements + " elements in each. Last group with " + lastelements + " elements");
            }
            else
            {
                //остаток < 0.5
                elements = Math.Truncate(group);
                group = Math.Truncate(group) + 1;
                lastelements = n - Math.Pow(elements, 2);
                //Для самопроверки
                Console.WriteLine();
                Console.WriteLine("Will be " + group + " groups, " + elements + " elements in each. Last group with " + lastelements + " elements");
            }
        }
    }

Answer 1

Сделал Fiddle, посмотри.

Дублирую код:

    public static void Main(string[] args)
    {
        int N = 10;
        //определяем количество групп
        int groups = (int) Math.Round(Math.Sqrt(N));
        //генерируем массив случайных чисел
        Random r = new Random();
        int[] A = new int[N];
        for (int i = 0; i < N; i++)
        {
            A[i] = r.Next(100, 1001);
        }
        //создаем рабочий массив
        int[][] W = new int[groups][];
        //делим массив на группы
        int count = 0;
        for (int i = 0; i < groups; i++)
        {
            //количество элементов в группе
            int n = N/groups;
            //если есть остаток - увеличиваем n
            if (i < N%groups)
            {
                n++;
            }
            W[i] = new int[n];
            //вносим элементы в рабочий массив
            for (int j = 0; j < n; j++)
            {
                W[i][j] = A[j + count];
            }
            count += n;
        }
        //вспомогательный массив
        int[] B = new int[groups];
        //заполнение вспомогательного массива
        for (int i = 0; i < groups; i++)
        {
            //Находим наименьшее и заменяем его на int.MaxValue
            B[i] = Min(W[i]);
        }
        //выходной массив
        int[] C = new int[N];
        for (int i = 0; i < N; i++)
        {
            //находим минимум во вспомогательном массиве
            int index = MinIndex(B);
            //выводим минимум
            C[i] = B[index];
            //заполняем вспомогательный массив
            B[index] = Min(W[index]);
        }
        //вывод
        Console.WriteLine("Исходный массив:");
        Console.WriteLine(string.Join(",", A));
        Console.WriteLine("Отсортированный массив:");
        Console.WriteLine(string.Join(",", C));
    }
    private static int Min(int[] array)
    {
        int index = MinIndex(array);
        int min = array[index];
        array[index] = int.MaxValue;
        return min;
    }
    private static int MinIndex(int[] array)
    {
        int min = array[0];
        int index = 0;
        for (int i = 1; i < array.Length; i++)
        {
            if (min > array[i])
            {
                min = array[i];
                index = i;
            }
        }
        return index;
    }