Сортировка квадратичным выбором - 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.