Простые алгоритмы сортировки. 2 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, - презентация

1 Простые алгоритмы сортировки

2 2 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Задача: переставить элементы массива в порядке возрастания. Алгоритмы: сортировка обменом – «пузырьковая» сортировка выбором сортировка вставками

3 3 Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький ("легкий") элемент перемещается вверх ("всплывает") начиная снизу, сравниваем два соседних элемента; если они стоят "неправильно", меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место ый проход 2-ой проход 3-ий проход Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

4 Программная реализация алгоритма Program C; uses crt; {пузырьковая сортировка} var a:array [1..30] of integer; i,d,l:integer; begin clrscr; randomize; writeln ('исходный массив'); for i:= 1 to 30 do begin a[i]:=random(10); write (a[i],' '); end; writeln; for l:=30 downto 2 do for i:=1 to l-1 do if a[i]>a[i+1] then begin d:=a[i]; a[i]:=a[i+1]; a[i+1]:=d; end; writeln('новый отсортированный массив'); for i:=1 to 30 do write (a[i],' '); readkey; end. исходный массив новый отсортированный массив

5 5 Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[1] ) из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2] ), и т.д

6 Программная реализация алгоритма Program C; {сортировка выбором} uses crt; var b,a:array [1..30] of integer; i,h,k,d,l:integer; begin clrscr; randomize; writeln ('исходный массив'); for i:= 1 to 30 do begin a[i]:=random(10); write (a[i],' '); end; writeln; for l:=1 to 29 do begin k:=30-l+1; h:=k; for i:=1 to 30-l do if (a[i]>a[h]) then h:=i; d:=a[k]; a[k]:=a[h]; a[h]:=d; end; writeln('новый отсортированный массив'); for i:=1 to 30 do write (a[i],' '); readkey; end. исходный массив новый отсортированный массив

7 Сортировка вставками Идея : основана на внедрении в отсортированную часть массива элемента следующего за этой частью, если он удовлетворяет условию сортировки. на первом шаге сортировки второй элемент сравнивается с первым, на втором шаге третий элемент сравнивается с двумя первыми и т. д. среди уже отсортированных i-1 элементов массива вставляют i-й элемент без нарушения порядка, т. е. при вставке i-го элемента на j-е место (j j и