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

слиянием

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

расположение одинаковых элементов в массиве.
Если номера двух одинаковых элементов i < j, то в отсортированном списке i’ < j’

Обменный (in-place) алгоритм – для его работы не требуется дополнительная память, которая зависит от размера массива.

существуют в записях (строчка в таблице, список, объект)

Базовая операция – сравнение двух элементов: ai ≤ aj (кроме некоторых специальных алгоритмов)
Время работы: Ω(n log n)

Рассматривается сортировка по возрастанию

(отчеты, списки)
Сортировка для бинарного поиска
Геометрические алгоритмы (вывод графики, поиск выпуклой оболочки)
Многие алгоритмы требуют предварительную сортировку данных

Алгоритмы сортировки – прекрасный способ изучения алгоритмов (большое количество алгоритмов, много техник).

соседних элементов. Если ai > ai+1, то элементы меняются местами.

На первом проходе в конец списка перемещается («всплывает») самый большой элемент, на втором проходе – всплывает второй по величине элемент и т.д.

for j=0 to n-2-i do
if A[j+1] < A[j]
обмен A[j] и A[j+1]

Время работы: O(n2)
Разные случаи: нет
Модификация: если при проходе нет обмена – список отсортирован

меняем местами с первым элементом. Далее находим второй наименьший элемент и меняем его местами со вторым элементом и т.д.

Есть другой вариант: ищем наибольший элемент и меняем местами с последним элементом.

min=i
for j=i+1 to n-1 do
if A[j] < A[min]
min=j
обмен A[j] и A[min]

Время работы: O(n2)
Разные случаи: нет

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

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

случае.

Разные случаи: да, зависит от характера входных данных. Чем ближе входные данные к отсортированным – тем меньше сравнений.

половина рекурсивно сортируется, после чего две половины сливаются в один отсортированный массив.

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

Копировать A[n/2…n-1] в С[0…n/2-1]
Mergesort (B[0…n/2-1])
Mergesort (С[0…n/2-1])
Merge (B,C,A)

j 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]

log n) в лучшем случае.

Разные случаи: да, зависит от характера входных данных, но не значительно

Требует n дополнительной памяти для подмассивов