Презентация по теме ««Алгоритмы сортировки»» для дисциплины ОП.08 Теория алгоритмов

• 1 слайд

  
  
  
  Тема урока: «Алгоритмы сортировки»
  Дисциплина ОП.08 Теория алгоритмов
  Преподаватель Скряго О.С.
  Смоленск 2014
  

• 2 слайд

  В чем состоит задача сортировки?
  Зачем нужно изучать сортировку?
  Сортировка пузырьком
  Сортировка выбором
  Сортировка вставками
  Сортировка слиянием
  

• 3 слайд

  1. В чем состоит задача сортировки?
  Сортировка – упорядочЕние заданного списка элементов.
  Вход: последовательность, состоящая из n чисел (a1, a2, …, an).
  Выход: перестановка (изменение порядка) (a1’, a2’,…, an’) входной последовательности таким образом, что a1’ ≤ a2’ ≤ … ≤ an’.
  Входная последовательность представляется в виде n-элементного массива.
  

• 4 слайд

  1. В чем состоит задача сортировки?
  Устойчивый алгоритм – не меняет относительное расположение одинаковых элементов в массиве.
  Если номера двух одинаковых элементов i < j, то в отсортированном списке i’ < j’
  
  Обменный (in-place) алгоритм – для его работы не требуется дополнительная память, которая зависит от размера массива.
  
  

• 5 слайд

  1. В чем состоит задача сортировки?
  Как правило, сортируются только ключи, которые существуют в записях (строчка в таблице, список, объект)
  
  Базовая операция – сравнение двух элементов: ai ≤ aj (кроме некоторых специальных алгоритмов)
  Время работы: Ω(n log n)
  
  Рассматривается сортировка по возрастанию
  

• 6 слайд

  2. Зачем нужно изучать сортировку?
  Во многих приложениях нужно сортировать данные
  Выдача информации (отчеты, списки)
  Сортировка для бинарного поиска
  Геометрические алгоритмы (вывод графики, поиск выпуклой оболочки)
  Многие алгоритмы требуют предварительную сортировку данных
  
  Алгоритмы сортировки – прекрасный способ изучения алгоритмов (большое количество алгоритмов, много техник).
  

• 7 слайд

  СОРТИРОВКА ПУЗЫРЬКОМ
  (BUBBLE SORT)
  

• 8 слайд

  3. Сортировка пузырьком
  Суть алгоритма: многократный проход по списку и сравнение двух соседних элементов. Если ai > ai+1, то элементы меняются местами.
  
  На первом проходе в конец списка перемещается («всплывает») самый большой элемент, на втором проходе – всплывает второй по величине элемент и т.д.
  

• 9 слайд

  3. Сортировка пузырьком
  Алгоритм Bubble sort (A[0…n-1])
  for i=0 to n-2 do
  for j=0 to n-2-i do
  if A[j+1] < A[j]
  обмен A[j] и A[j+1]
  
  Время работы: O(n2)
  Разные случаи: нет
  Модификация: если при проходе нет обмена – список отсортирован
  
  

• 10 слайд

  СОРТИРОВКА ВЫБОРОМ
  (SELECTION SORT)
  

• 11 слайд

  4. Сортировка выбором
  Суть алгоритма: проходим по списку, ищем наименьший элемент и меняем местами с первым элементом. Далее находим второй наименьший элемент и меняем его местами со вторым элементом и т.д.
  
  Есть другой вариант: ищем наибольший элемент и меняем местами с последним элементом.
  
  

• 12 слайд

  4. Сортировка выбором
  Алгоритм Selection sort (A[0…n-1])
  for i=0 to n-2 do
  min=i
  for j=i+1 to n-1 do
  if A[j] < A[min]
  min=j
  обмен A[j] и A[min]
  
  Время работы: O(n2)
  Разные случаи: нет
  

• 13 слайд

  СОРТИРОВКА ВСТАВКАМИ (INSERTION SORT)
  

• 14 слайд

  5. Сортировка вставками
  Суть алгоритма: делим список на отсортированную часть и неотсортированную.
  Изначально в отсортированную часть попадает первое значение списка.
  Далее сравниваем следующее значение со значениями в отсортированном списке и ставим его в нужном порядке, после чего отсортированная часть увеличивается на 1.
  Потом берем следующее значение и т.д.
  
  

• 15 слайд

  5. Сортировка вставками
  Алгоритм Insertion sort (A[0…n-1])
  for i=1 to n-1 do
  v=A[i]
  j=i-1
  while j≥0 AND A[j]>v do
  A[j+1]=A[j]
  j=j-1
  A[j+1]=v
  

• 16 слайд

  5. Сортировка вставками
  Время работы: O(n2) в худшем случае, O(n) в лучшем случае.
  
  Разные случаи: да, зависит от характера входных данных. Чем ближе входные данные к отсортированным – тем меньше сравнений.
  
  

• 17 слайд

  СОРТИРОВКА СЛИЯНИЕМ
  (MERGE SORT)
  

• 18 слайд

  6. Сортировка слиянием
  Суть алгоритма: список рекурсивно делится пополам, после чего каждая половина рекурсивно сортируется, после чего две половины сливаются в один отсортированный массив.
  
  Список рекурсивно делится пополам, пока все подмассивы не будут содержать 1 или 0 элементов.
  Если сортируемый список нечетный – один из подмассивов будет пустым.
  
  

• 19 слайд

  6. Сортировка слиянием
  Алгоритм Mergesort (A[0…n-1])
  if n>1
  Копировать A[0…n/2-1] в B[0…n/2-1]
  Копировать A[n/2…n-1] в С[0…n/2-1]
  Mergesort (B[0…n/2-1])
  Mergesort (С[0…n/2-1])
  Merge (B,C,A)
  

• 20 слайд

  6. Сортировка слиянием
  Алгоритм Merge (B[0…p-1], C[0…q-1], A[0…p+q-1)
  i=0; j=0; k=0
  While i<p AND j<q do
  if B[i]≤C[j]
  A[k]=B[i]; i=i+1
  else
  A[k]=C[j]; j=j+1
  k=k+1
  if i=p
  Копировать C[j…q-1] в A[k…p+q-1]
  Else
  Копировать B[i…p-1] в A[k…p+q-1]
  
  

• 21 слайд

  6. Сортировка слиянием
  

• 22 слайд

  6. Сортировка слиянием
  Время работы: O(n log n) в худшем случае, O(n log n) в лучшем случае.
  
  Разные случаи: да, зависит от характера входных данных, но не значительно
  
  Требует n дополнительной памяти для подмассивов
  
  

• 23 слайд

  Сравнительная таблица сортировок