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