Презентация на тему "Сортировка обменом(Сортировка пузырьком)"

Содержание

• 
  Слайд 1

  Сортировка обменом(Сортировка пузырьком)

  МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Вятский государственный университет» (ФГБОУ ВПО «ВятГУ») Работу выполнили студенты группы ИВТ-11: Веселов РоманЖуков ДмитрийКараваев АртемМакаров АлексейПентин МаксимСеливанов ЯковШеромов Дмитрий

• 
  Слайд 2

  Преимущества и недостатки

  Сортировка пузырьком — простейший для понимания и реализации алгоритм сортировки. Эффективен он лишь для небольших массивов. Недостатком является высокая сложность алгоритма: O(n²). Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка. Алгоритм является устойчивым (не меняет взаимного расположения равных элементов). Алгоритм не использует дополнительной памяти, т.е. все действия осуществляются на одном и том же массиве.

• 
  Слайд 3

  Описание

  Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

• 
  Слайд 4

  Пример работы алгоритма

  Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе. Первый проход: (5 14 2 8) (1 54 2 8) (1 5 42 8) (1 4 5 2 8) (1 4 5 2 8) (1 4 2 5 8) (1 4 2 5 8) (1 4 2 5 8) Второй проход: (1 42 5 8) (1 42 5 8) (1 4 25 8) (1 2 45 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) Здесь алгоритм сравнивает два первых элемента и меняет их местами. Меняются местами 5 и 4, т. к. 5>4. Меняются местами 5 и 4, т. к. 5>2. Алгоритм не меняет местами элементы, т. к. 5 2. Смена позиций не нужна т. к. 4

• 
  Слайд 5

  Код и результат выполнения программы

  program sort_obmen; uses crt; vara: array [1..100] of byte; n,x,i,j:integer; begin clrscr; writeln('Введите размер массива'); readln(n); for i:= 1 to n do begin write('Введите ',i,'-й элемент массива '); read(a[i]); end; writeln('Введенный массив:'); for i:= 1 to n do write(a[i],' '); writeln; for j:=1 to n-1 do begin for i:=1 to n-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:=a[i+1]; a[i+1]:=x; end; end; writeln('Отсортированный массив:'); for i:=1 to n do write(a[i],' '); readln; end.

• 
  Слайд 6

  Спасибо за внимание!