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

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

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

Есть задание: Сгенерировать массив случайных чисел от 100-1001, и отсортировать его методом квадратичного выбора. Написал начало, которое считает сколько должно быть групп и элементов в каждой групе. Но дальше застрял.. не понимаю как разбить этот массив на группы , искать минимум в каждой группе, переносить в другой массив и так далее по алгоритму.
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;
        }
        else
        {
            elements = Math.Truncate(group);
            group = Convert.ToInt32(group) + 1;
            lastelements = n - Math.Pow(elements, 2);            
        }
 
        //Для самопроверки
        Console.WriteLine();
        Console.WriteLine("Will be " + group + " groups, " + elements + " elelemnts in each. Plus 1 group with " + lastelements + " elements"); 
 
    }

Решение задачи: «Сортировка квадратичным выбором»

textual
Листинг программы
(*
Сортировка методом квадратичной выборки.
Массив, состоящий из М элементов, разбивают на SQRT(M) групп по SQRT(M)
элементов в каждой.
В результате сплошного просмотра в каждой группе находят и заносят в рабочие
переменные элементы с наименьшими значениями.
Затем просматривают переменные и переменную с наименьшим значением заносят в
выходной массивы.
После этого осуществляют поиск наименьшего элемента в той группе, из
переменной которой элемент был перенесен в выходной массив.
Процесс повторяют.
При каждом занесении элемента в переменную ее стирают в основном массиве.
Работу метода поясним примером.
В примере А обозначает исходный массив,
      В переменные,
      С выходной массив.
*)
Uses Crt, Dos;
Const     Max = 1600;  { число элементов массива }
      SqrtMax = 40;    { число групп }
       SqrtEl = 40;    { число элементов в группе }
Var I : Integer;                         { переменная цикла }
    B : Array [1..SqrtMax] Of Integer;   { массив переменных }
    W : Array [1..SqrtMax] Of Integer;   { массив "номерков" }
    A : Array [1..Max] Of Integer;       { исходный массив }
    C : Array [1..Max] Of Integer;       { выходной массив }
    P,                                   { число присваиваний }
    S,                                   { число сравнений }
    L : LongInt;                         { затраченное время }
 
Function Time:Longint;           { возвращает текущее время в долях секунды }
Var h, m, s, hund : Word;
Begin
  GetTime(h,m,s,hund);
  Time := hund + s*100 + m*60*100 + h*60*60*100;
end;
 
Procedure Sort (Var Perest, Sr, LostTime : LongInt);
                            { находит минимальный элемент в заданной группе }
          Procedure FindMinElemToSquart(E:Integer);
          Var Min : Integer;                         { минимальное значение }
                I : Integer;                             { переменная цикла }
          Begin
                Min := MaxInt;                         { минимум неизвестен }
                For I:=1 To SqrtMax Do   { перебираем все элементы в группе }
                    If (Min > A[(E-1)*4+I]) AND          { находим меньший, }
                       (A[(E-1)*SqrtEl+I] <> -1) Then Begin { положительный }
                          Min := A[(E-1)*SqrtEl+I]; { элемент, и запоминаем }
                          W[E] := I;             { его и его номер в группе }
                          Sr := Sr + 1;                { ещё одно сравнение }
                    End;
                B[E] := A[(E-1)*SqrtEl+W[E]];       { запомним этот элемент }
                Perest := Perest + 1;               { ещё одно присваивание }
          End;
                             { находит минимальный элемент среди переменных }
          Function FindMinPerem:Integer;
          Var Min : Integer;                         { минимальное значение }
                I : Integer;                             { переменная цикла }
              Temp: Integer;                         { временная переменная }
          Begin
               Min := MaxInt;                          { минимум неизвестен }
               For I:=1 To SqrtMax Do           { перебираем все переменные }
                   If (Min > B[I]) AND      { находим меньший и обязательно }
                      (B[I] <> -1) Then Begin       { положительный элемент }
                      Min := B[I];                { запоминаем его значение }
                      Temp := I;                       { и, временно, номер }
                      Sr := Sr + 1;                    { ещё одно сравнение }
                   End;
               FindMinPerem := Temp;      { функция вернёт номер переменной }
          End;
 
Var Nac, Kon : Longint;                          { время в начале и в конце }
    I, J,                                                { переменные цикла }
    Tek,                                  { сколько элементов отсортировано }
    Why : Integer;             { какую переменную запишем в выходной массив }
Begin
     Perest := 0;                                    { присваиваний не было }
     Sr := 0;                                      { сравнений тоже не было }
 
     Nac := Time;                                         { запомним время }
     Tek := 1;                          { будем записывать сначала массива }
     For I:=1 To SqrtMax Do Begin     { определим минимумы в каждой группе }
         FindMinElemToSquart(I);
     End;
 
     While Tek <= Max Do Begin
           Why := FindMinPerem;
           C[Tek] := B[Why];
           Perest := Perest + 1;
           Tek := Tek + 1;
           A[(Why-1)*SqrtEl+W[Why]] := -1;
           B[Why] := -1;
           FindMinElemToSquart(Why);
     End;
     Kon := Time;
     LostTime := Kon - Nac;
End;
 
 
Begin
     ClrScr;
     Randomize;
 
     WriteLn('Сортировка методом квадратичной выборки.');
     WriteLn;
 
     WriteLn('Массив заполненен случайными числами');
     For I:=1 to Max Do A[i]:=Random(999); { заполнение случайными числами }
     For I:=1 To Max Do C[I] := 0;
     For I:=1 To SqrtMax Do B[I] := 0;
     For I:=1 To SqrtMax Do W[I] := 0;
     Sort (P, S, L);
     WriteLn('Число элементов   ',Max:10);
     WriteLn('Число перестановок',P:10);
     WriteLn('Число сравнений   ',S:10);
     WriteLn('Затраченное время ',L:10,'ms');
 
     WriteLn;
     WriteLn('Массив отсортирован');
     For I:=1 to Max Do A[i]:=I;           { отсортирован }
     For I:=1 To Max Do C[I] := 0;
     For I:=1 To SqrtMax Do B[I] := 0;
     For I:=1 To SqrtMax Do W[I] := 0;
     Sort (P, S, L);
     WriteLn('Число элементов   ',Max:10);
     WriteLn('Число перестановок',P:10);
     WriteLn('Число сравнений   ',S:10);
     WriteLn('Затраченное время ',L:10,'ms');
 
     WriteLn;
     WriteLn('Массив обратно упорядочен');
     For I:=1 to Max Do A[i]:=(Max+1)-I;   { обратно упорядочен }
     For I:=1 To Max Do C[I] := 0;
     For I:=1 To SqrtMax Do B[I] := 0;
     For I:=1 To SqrtMax Do W[I] := 0;
     Sort (P, S, L);
     WriteLn('Число элементов   ',Max:10);
     WriteLn('Число перестановок',P:10);
     WriteLn('Число сравнений   ',S:10);
     WriteLn('Затраченное время ',L:10,'ms');
End.

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


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

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

12   голосов , оценка 4.25 из 5
Похожие ответы