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

• 1 слайд

  Сортировка методом пузырька, выбором (Pascal)
  Кокарева Светлана Ивановна
  

• 2 слайд

  Общее понятие о массивах
  Предположим, что программа работает с большим количеством однотипных данных. Скажем около ста разных целых чисел нужно обработать, выполнив над ними те или иные вычисления. Как вы себе представляете 100 переменных в программе? И для каждой переменной нужно написать одно и тоже выражение вычисления значения? Это очень неэффективно.
  
  Есть более простое решение. Это использование такой структуры (типа) данных как массив. Массив представляет собой последовательность ячеек памяти, в которых хранятся однотипные данные. При этом существует всего одно имя переменной связанной с массивом, а обращение к конкретной ячейке происходит по ее индексу (номеру) в массиве.
  
  Нужно четко понимать, что индекс ячейки массива не является ее содержимым. Содержимым являются хранимые в ячейках данные, а индексы только указывают на них. Действия в программе над массивом осуществляются путем использования имени переменной, связанной с областью данных, отведенной под массив.
  

• 3 слайд

  Массив -
  это именованная группа однотипных данных, хранящихся в последовательных ячейках памяти. Каждая ячейка содержит элемент массива. Элементы нумеруются по порядку, но необязательно начиная с единицы (хотя в языке программирования Pascal чаще всего именно с нее). Порядковый номер элемента массива называется индексом этого элемента.
  

• 4 слайд

  Общее понятие о массивах
  Помним, все элементы определенного массива имеют один и тот же тип. У разных массивов типы данных могут различаться. Например, один массив может состоять из чисел типа integer, а другой – из чисел типа real.
  
  Индексы элементов массива обычно целые числа, однако могут быть и символами, а также описываться другими порядковыми типами.
  
  Массив можно создать несколькими способами.
  
  Обращение к определенному элементу массива осуществляется путем указания имени переменной массива и в квадратных скобках индекса элемента.
  
  Простой массив является одномерным. Он представляет собой линейную структуру.
  

• 5 слайд

  Способы создания одномерных массивов
  var ch: array [1..11] of char;
  h: char;
  i: integer;
  
  begin
  for i := 1 to 11 do read (ch[i]);
  
  for i := 1 to 11 do write (ch[i]:3);
  
  readln
  end.
  В примере выделяется область памяти под массив из 11 символов. Их индексы от 1 до 11. В процессе выполнения программы пользователь вводит 11 любых символов (например, ‘q’, ’w’, ’e’, ’2’, ’t’, ’9’, ’u’, ’I’, ’I’, ’o’, ’p’), которые записываются в ячейки массива. Текущее значение переменной i в цикле for используется в качестве индекса массива. Второй цикл for отвечает за вывод элементов массива на экран.
  

• 6 слайд

  Сортировка методом пузырька
  Задача:
  
  При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания. Это значит, что элементы того же нужно расположить строго по порядку. Например, в случае сортировки по возрастанию предшествующий элемент должен быть меньше последующего (или равен ему).
  

• 7 слайд

  Сортировка методом пузырька
  Алгоритм решения задачи:
  
  Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"?
  
  Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).
  

• 8 слайд

  Сортировка методом пузырька
  Алгоритм и особенности этой сортировки таковы:
  При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
  Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
  При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
  На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
  В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
  После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.
  Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
  При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.
  

• 9 слайд

  Сортировка
  

• 10 слайд

  Сортировка
  

• 11 слайд

  Сортировка
  

• 12 слайд

  Сортировка
  

• 13 слайд

  Алгоритм сортировки методом пузырька
  

• 14 слайд

  Программа на языке Паскаль:
  
  
  const
  m = 10;
  
  var
  arr: array[1..m] of integer;
  i, j, k: integer;
  
  begin
  randomize;
  
  write ('Исходный массив: ');
  for i := 1 to m do begin
  arr[i] := random(256);
  write (arr[i]:4);
  end;
  writeln; writeln;
  
  
  
  for i := 1 to m-1 do
  for j := 1 to m-i do
  if arr[j] > arr[j+1] then begin
  k := arr[j];
  arr[j] := arr[j+1];
  arr[j+1] := k
  end;
  
  write ('Отсортированный массив: ');
  for i := 1 to m do
  write (arr[i]:4);
  
  writeln;
  
  readln
  end
  
  

• 15 слайд

  Сортировка выбором
  Задача:
  
  Требуется отсортировать массив по возрастанию.
  Алгоритм решения задачи:
  
  Для этого можно воспользоваться следующим алгоритмом.
  Найти максимальный элемент (max) в массиве (arr).
  Поместить его на последнее место (j).
  Элемент, находившийся в конце массива переместить на место, где прежде находился max.
  Уменьшить просматриваемую область массива на единицу (j – 1).
  Снова найти максимальный элемент в оставшейся области.
  Поместить его в конец просматриваемой области массива.
  и т.д.
  

• 16 слайд

  Программа на языке Pascal
  const n = 10;
  
  var
  arr: array[1..n] of byte;
  max, id_max, i, j: byte;
  
  begin
  randomize;
  for i := 1 to n do begin
  arr[i] := random(256);
  write(arr[i]:4)
  end;
  writeln;
  
  j := n;
  while j > 1 do begin
  max := arr[1];
  id_max := 1;
  for i := 2 to j do
  if arr[i] > max then begin
  max := arr[i];
  id_max := i
  end;
  arr[id_max] := arr[j];
  arr[j] := max;
  j := j - 1
  end;
  
  for i := 1 to n do
  write(arr[i]:4);
  
  readln
  end.
  

• 17 слайд

  Переходим к набору программ сортировки
  Обе сортировки должны быть реализованы обучающимися!!!
  
  Поняты и приняты на вооружение алгоритмы сортировки для решения задач программирования!
  

Краткое описание документа:

Данную презентацию использую при объяснении темы массивы. На предыдущем уроке дети знакомятся с массивами, правилами их описания и вызова в программе. Как правило, количество уроков на изучения программирования в школьном курсе мало, а качество усвоенного материала за эти уроки должно быть нереально высоко. Естественно, алгоритмы сортировки и сам материал, имеют других авторов. Мною они отобраны так, как удобно мне рассказывать и показывать. Возможно, кому-то будет удобно это также как и мне. Учебник тоже может быть любой, так как на материал учебника в данной презентации нет ни ссылок, ни рекомендаций.