Каталог | Индекс раздела |
Назад | Оглавление | Вперед |
Ознакомление с алгоритмами сортировок статических структур данных.
Статические структуры данных. Поиск. Сортировка.
Разработать программу, которая выполняет сортировку набора данных.
Номер п/п |
Задание | Вариант алгоритма сортировки |
---|---|---|
1 |
В массиве A[1..n] каждый элемент равен 0, 1 или 2. Отсортировать по возростанию. | 1 |
2 |
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания. | 2 |
3 |
Дано N целых чисел. Упорядочить их по возростанию | 3 |
4 |
Дан одномерный массив целых чисел. Проверить, является ли он упорядоченным по убыванию. | 4 |
5 |
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по убыванию. | 5 |
6 |
В массиве A[1..n] каждый элемент изменяется в пределах от 0..20. Отсортировать по возростанию. | 6 |
7 |
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания. | 7 |
8 |
Дано N целых чисел от -50 до 50. Упорядочить их по возростанию | 8 |
9 |
Дан одномерный массив целых чисел > 43. Проверить, является ли он упорядоченным по убыванию. | 9 |
10 |
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по возростанию. | 10 |
11 |
В массиве A[1..30] каждый элемент равен 0, 7 или 14. Отсортировать по возростанию. | 11 |
12 |
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания. | 12 |
13 |
Дано N целых чисел. Упорядочить их по возростанию | 13 |
14 |
Дан одномерный массив целых чисел. Проверить, является ли он упорядоченным по убыванию. | 14 |
15 |
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по убыванию. | 15 |
16 |
В массиве A[1..n] каждый элемент изменяется в пределах от 0..15. Отсортировать по возростанию. | 15 |
17 |
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания. | 14 |
18 |
Дано N целых чисел от 3 до 14. Упорядочить их по возростанию | 13 |
19 |
Дан одномерный массив целых чисел > 10. Проверить, является ли он упорядоченным по убыванию. | 12 |
20 |
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по возростанию. | 11 |
21 |
В массиве A[1..n] каждый элемент равен 5, 7 или 9. Отсортировать по возростанию. | 10 |
22 |
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания. | 9 |
23 |
Дано N целых чисел. Упорядочить их по возростанию | 8 |
24 |
Дан одномерный массив целых чисел. Проверить, является ли он упорядоченным по убыванию. | 7 |
25 |
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по убыванию. | 6 |
26 |
В массиве A[1..n] каждый элемент изменяется в пределах от 0..50. Отсортировать по возростанию. | 5 |
27 |
Написать программу, которая располагает элементы одномерного массива A[1..n] в зависимости от значения параметра q либо в порядке возрастания, либо в порядке убывания. | 4 |
28 |
Дано N целых чисел от -100 до 0. Упорядочить их по возростанию | 3 |
29 |
Дан одномерный массив целых чисел > 0. Проверить, является ли он упорядоченным по убыванию. | 2 |
30 |
Одномерный массив целых чисел задан случайным образом. Проверить, является ли он упорядоченным по возростанию. | 1 |
Номер сортировки по вариантам:
5.1. Разработка алгоритма решения
Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке.
Цель сортировки - облегчение последующего поиска элементов в отсортированном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах.
Основное требование к методам сортировки массивов - экономное использование памяти. Это означает, что переупорядочивание элементов нужно выполнять на том же месте и что методы, которые пересылают элементы из массива A в массив B, не представляют для нас интереса.
Проблема сортировки неупорядоченного массива относится в вычислительной технике к классическим. Она кажется простой, ведь всем приходилось выполнять какую-либо механическую сортировку, была ли то раскладка игральных карт, гардеробных номерков, карточек из библиотечного каталога или денежных счетов. Простота эта иллюзорна. Хотя первые программы сортировки были написаны фон Нейманом в 1945 г., какого-либо значительного продвижения в теории сортировки не наблюдалось в течение последующих двадцати лет [Грогоно,1982].
5.2. Выбор метода
Сортировка обменом - метод, при котором все соседние элементы массива попарно сравниваются друг с другом и меняются местами в том случае, если предшествующий элемент больше последующего. В результате этого максимальный элемент постепенно смещается вправо и в конце концов занимает крайнее правое место в массиве, после чего он исключается из дальнейшей обработки. Затем процесс повторяется и свое место занимает второй по величине элемент, который также исключается из дальнейшего рассмотрения. Так продолжается до тех пор, пока вся последовательность не будет упорядочена. Сортировку обменом называют еще "пузырьковой" (сравнение с всплытием пузырьков воздуха в жидкости).
Совершенно ясно, что если на очередном проходе массива не будет сделано ни одного обмена, то массив уже упорядочен. Если мы будем фиксировать этот факт, то несущественное усложнение процедуры сортировки может дать существенный выигрыш в скорости. Приведем вариант, учитывающий это обстоятельство.
PROCEDURE BubbleSort (var a: Integer); var i,j: Integer; f : Boolean; { Если был обмен, то f=TRUE, } { если не было обмена f=FALSE } BEGIN f := TRUE; i := N-1; While (i>=1) AND f do begin f := FALSE; For j:=1 to i do If a[j]>a[j+1] then begin f := TRUE; Swap (a[j],a[j+1]) end i := i-1 end END;
Необходима также процедура, обеспечивающая обмен местами двух элементов - найденного при i-м просмотре минимального элемента и элемента с индексом i.
PROCEDURE Swap (var a,b: Integer); var c: Integer; BEGIN c := a; a := b; b := c END;
Приведем еще одну реализацию алгоритма простого выбора.
PROGRAM B_u_b_b_l_e_S_o_r_t (Input,Output); const N=8; type index = 1..N; massiv = Array[0..N] of Integer; var x : Integer; a : massiv; i,j: index; BEGIN For i:=1 to N do ReadLn (a[i]); For i:=2 to N do For j:=n downto i do If a[j-1]>a[j] then begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x end; For i:=1 to N do Write (a[i],' ') END.
При этом методе сортировки в неупорядоченной последовательности выбирается минимальный элемент, который исключается из дальнейшей обработки, а оставшаяся последовательность элементов принимается за исходную. Процесс повторяется до тех пор, пока все элементы не будут выбраны. Очевидно, что все выбранные элементы образуют упорядоченную последовательность.
Выбранный в исходной последовательности минимальный элемент размещается на предназначенном ему месте упорядоченной последовательности несколькими способами:
а) Минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) другого специально созданного массива, а в старом, исходном, на месте выбранного размещается какое-то очень большое число, превосходящее по величине любой элемент сортируемого массива. Измененный таким образом массив принимается за исходный, и осуществляется следующий просмотр.
б) Минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) заданного массива, а элемент с i-го места - на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т.е. размер каждого последующего обрабатываемого массива на единицу меньше размера предыдущего.
В этом случае программа сортировки выбором нуждается во вспомогательной функции поиска индекса минимального элемента из списка переменной длины - от элемента с некоторым индексом start до последнего элемента массива.
FUNCTION I_m_i_n (start: Integer; a: tarray): Integer; { Ищет минимальный элемент правее start (включая start) } { и возвращает его номер } var m: Integer; i: Integer; BEGIN m := start; For i:=start+1 to N do If a[i]<a[m] then m := i; I_m_i_n :=m END;
Необходима также процедура, обеспечивающая обмен местами двух элементов - найденного при i-м просмотре минимального элемента и элемента с индексом i.
PROCEDURE Swap (var a,b: Integer); var c: Integer; BEGIN c := a; a := b; b := c END;
Процедура сортировки выбором имеет вид:
PROCEDURE sort_choice (var t:array); var i: Integer; BEGIN For i:=1 to N-1 do Swap (a[I_m_i_n(i,a)],a[i]) END;
Приведем еще одну реализацию алгоритма простого выбора.
PROGRAM Sort (Input,Output); { Сортировка простым выбором } const N=8; type index = 0..N; massiv = Array[0..N] of Integer; var x : Integer; a : massiv; i,j,k: index; BEGIN For i:=1 to N do readln(a[i]); For i:=1 to N-1 do begin k := i; x := a[i]; For j:=i+1 to N do If a[j]<x then begin k := j; x := a[j] end; a[k] := a[i]; a[i] := x end; For i:=1 to N do Write (a[i],' ') END.
При сортировке включениями из неупорядоченной последовательности элементов поочередно выбирается каждый элемент, сравнивается с предыдущим (уже упорядоченным) списком и помещается на соответствующее место в последнем.
Для сортировки включениями необходима вспомогательная процедура, которая обеспечивает перемещение элемента с индексом i на место элемента с индексом j и смещение всех элементов с индексами от j до i на одну позицию вправо.
Приведем реализацию алгоритма сортировки включениями на языке Pascal (диалект TURBO Pascal).
PROGRAM S_o_r_t (Input,Output); { Сортировка простыми включениями } const N=8; type index=0..N; massiv = Array[0..N] of Integer; var x: Integer; a: massiv; i,j: index; BEGIN For i:=1 to N do ReadLn (a[i]); For i:=2 to N do begin x := a[i]; a[0] := x; j := i-1; While x<a[j] do begin a[j+1] := a[j]; j := j-1 end; a[j+1] := x end; For i:=1 to N do Write (a[i],' ') END. PROGRAM Sort (Input,Output); { Сортировка бинарными включениями } const N=8; type index=0..N; massiv = Array[0..N] of Integer; var x : Integer; a : massiv; i,j,l,r,m: index; BEGIN For i:=1 to N do Readln (a[i]); For i:=2 to N do begin x := a[i]; l := 1; r := i-1; While l<=r do begin m := (l+r) DIV 2; If x<a[m] then r := m-1 else l := m+1 end; For j:=i-1 downto l do a[j+1] := a[j]; a[l] := x; end; For i:=1 to N do Write (a[i],' ') END.
PROGRAM Q_u_i_c_k_S_o_r_t (Input,Output); const N = 7; type index = 0..N; massiv = Array [0..N] of Integer; var a: massiv; i: index; { ------------------------------ } PROCEDURE S_O_R_T (l,r: index); var i,j: index; x,w: Integer; BEGIN i := l; j := r; x := a[(l+r) DIV 2]; Repeat While a[i]<x do i := i+1; While x<a[j] do j := j-1; If i<=j then begin w := a[i]; a[i] := a[j]; a[j] := w; i := i+1; j := j-1 end until i>j; If l<j then S_O_R_T (l,j); If i<r then S_O_R_T (i,r) END; { --- } BEGIN For i:=1 to N do Readln (a[i]); S_O_R_T (1,N); For i:=1 to N do Write (a[i],' ') END.
PROGRAM NonRecursiveQuickSort (Input,Output); { Обратите внимание на то, что в программе использован тип Record } const N = 8; M = 12; type index = 0..N; massiv = Array [0..N] of Integer; zapis = Record L,R: index end; var x,w : Integer; a : massiv; i,j,L,R: index; s : 0..M; stack : Array [1..M] of zapis; BEGIN For i:=1 to N do ReadLn (a[i]); s := 1; stack[1].L := 1; stack[s].R := N; Repeat { Выбор из стека последнего запроса } L := stack[s].L; R := stack[s].R; s := s-1; Repeat { Разделение a[L],...,a[R] } i := L; j := R; x := a[(L+R) DIV 2]; Repeat While a[i]<x do i := i+1; While x<a[j] do j := j-1; If i<=j then begin w := a[i]; a[i] := a[j]; a[j] := w; i := i+1; j := j-1 end; until i>j; If i<R then { Запись в стек запроса из правой части } begin s := s+1; stack[s].L := i; stack[s].R := R end; R := j {Теперь L и R ограничивают левую часть} until L>=R; until s=0; For i:=1 to N do Write (a[i],' ') END.
PROGRAM S_h_e_l_l_s_o_r_t (Input,Output); const N = 780; t = 4; type Index = 0..N; Massiv = Array [-9..N] of Integer; Mas = Array [1..t] of Integer; var x : Integer; a : Massiv; h : Mas; i,j,k,s: Index; m : 1..t; L : Index; { --- } BEGIN Writeln ('Введите исходный массив...'); For L:=1 to N do begin a[L] := Random (23); Write (a[L],' ') end; WriteLn; h[1] := 9; h[2] := 5; h[3] := 3; h[4] := 1; For m:=t downto 1 do begin k := h[m]; s := -k; { Место барьера } For i:=k+1 to n do begin x := a[i]; j := i-k; If s=0 then s := -k; s := s+1; a[s] := x; While x<a[j] do begin a[j+k] := a[j]; j := j-k end; a[j+k] := x end; end; Writeln ('Результаты сортировки...'); For L:=1 to N do Write (a[L],' '); WriteLn END.
PROGRAM S_h_a_k_e_S_o_r_t (Input,Output); const N=8; type index = 0..N; massiv = Array[0..N] of Integer; var x: Integer; a: massiv; i,j,k,l,r: index; BEGIN For i:=1 to N do ReadLn (a[i]); l := 2; r := n; k := n; Repeat For j:=r downto l do If a[j-1]>a[j] then begin x := a[j-1]; a[j-1] := a[j]; a[j] := x; k := j end; l := k + 1; For j:=l to r do If a[j-1]>a[j] then begin x:=a[j-1];a[j-1]:=a[j];a[j]:=x; k:=j end; r := k - 1; until l>r; For i:=1 to N do Write (a[i],' ') END.
PROGRAM Heapsort (Input,Output); const N=8; type index=0..N; massiv = Array[0..N] of Integer; var x: Integer; a: massiv; i,l,r: index; { -------------------- } PROCEDURE sift; label metka; var i,j: index; BEGIN i := l; j := 2*i; x := a[i]; While j<=r do begin If j<r then If a[j]<a[j+1] then j := j+1; If x>=a[j] then Goto metka; a[i] := a[j]; i := j; j := 2*i end; metka: a[i] := x END; { --- } BEGIN For i:=1 to N do ReadLn (a[i]); l := (n DIV 2)+1; r := n; While l>1 do begin l := l-1; sift end; While r>1 do begin x := a[1]; a[1] := a[r]; a[r] := x; r := r-1; sift end; For i:=1 to N do Write (a[i],' ') END.
В отчет включить:
Оценка времени выполнения сортировки
void main() { struct time t; int t1,t2; clrscr(); input(); gettime(&t); t1=t.ti_hund; sort(); gettime(&t); t2=t.ti_hund; printf("\nвремя выполнение сортировки %d секунд \n",t2-t1); vivod(); getch(); }
Каталог | Индекс раздела |
Назад | Оглавление | Вперед |