Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Сортировка. Алгоритмы сортировки

Задача сортировки (sorting problem)
Сортировка. Алгоритмы сортировки.http://www.sorting-algorithms.com Задача сортировки (sorting problem) Сортировка выбором. Selection Sort. На каждой итерации i, найти индекс (min ) Сортировка выбором. Реализация.(см. Example5, Project SelectionSort)1. перемещаемся по массиву вправоi++;2. находим индекс Сортировка выбором. Анализ. Сравнений: (N-1)+(N-2)+…1+0 ~ N2/2Перестановок: NСложность алгоритма: O(N2)Время работы алгоритма: Сортировка вставками. Insertion Sort. двигаемся по массиву элементов слева на право на Сортировка вставками. Demo.ijijijijijijijij Сортировка вставками. Реализация.1. перемещаемся по массиву слева направоi++;2. двигаемся справа-налево от i-го Сортировка вставками. Анализ. Сравнений: ~1/4 N2 в среднемПерестановок: ~1/4 N2 в среднемСложность Сортировка простыми обменами. Bubble Sort. Алгоритм состоит из повторяющихся проходов по массиву Bubble sort. Demo.Swap (6,9)Don’t swapSwap (2,4)Swap (2,8)Конец 1-го проходаКонец 2-го прохода Bubble Sort. Реализация.1. Выполняем i-ый проход, перестановок не былоint i=0; bool swapped=false;2. Bubble sort. Анализ. Сравнений: (N-1)*N Перестановок: (N-1)*N/2Сложность алгоритма: O(N2)Наилучший случай: если массив
Слайды презентации

Слайд 2 Задача сортировки (sorting problem)

Задача сортировки (sorting problem)

Слайд 3 Сортировка выбором. Selection Sort.
На каждой итерации

Сортировка выбором. Selection Sort. На каждой итерации i, найти индекс (min

i, найти индекс (min ) минимального значения
поменять местами

элементы a[i] и a[min] - swap (a[i], a[min])

Идея алгоритма

(см. Example5, Project SelectionSort)

i

min

i

min

i

min

i

min

i

min


Слайд 4 Сортировка выбором. Реализация.
(см. Example5, Project SelectionSort)
1. перемещаемся по

Сортировка выбором. Реализация.(см. Example5, Project SelectionSort)1. перемещаемся по массиву вправоi++;2. находим

массиву вправо
i++;
2. находим индекс минимального в правой части массива
int

min=i;
for (int j=i+1; j if ( less(a[j], a[min]) )
min=j;

3. меняем местами элементы i-ый и min
swap(a, i, min);


Слайд 5 Сортировка выбором. Анализ.
Сравнений: (N-1)+(N-2)+…1+0 ~ N2/2
Перестановок: N
Сложность

Сортировка выбором. Анализ. Сравнений: (N-1)+(N-2)+…1+0 ~ N2/2Перестановок: NСложность алгоритма: O(N2)Время работы

алгоритма: O(N2)
Время работы алгоритма: не зависит от порядка расположения

исходных данных. Квадратичное, даже если исходный массив отсортирован.

Плюсы: Количество перестановок минимально

Минусы: Очень высокая вычислительная сложность O(N2)


Слайд 6 Сортировка вставками. Insertion Sort.
двигаемся по массиву

Сортировка вставками. Insertion Sort. двигаемся по массиву элементов слева на право

элементов слева на право
на каждой итерации i меняем

местами a[i] с каждым элементом слева от a[i] и большим его

Идея алгоритма

(см. Example5, Project InsertionSort)


Слайд 7 Сортировка вставками. Demo.
i
j
i
j
i
j
i
j
i
j
i
j
i
j
i
j

Сортировка вставками. Demo.ijijijijijijijij

Слайд 8 Сортировка вставками. Реализация.
1. перемещаемся по массиву слева направо
i++;
2.

Сортировка вставками. Реализация.1. перемещаемся по массиву слева направоi++;2. двигаемся справа-налево от

двигаемся справа-налево от i-го элемента и меняем местами с

каждым, большим a[i]
for (int j=i; j>0; j--)
if ( less(a[j], a[j-1]) )
swap(a, j, j-1);
else break;

Слайд 9 Сортировка вставками. Анализ.
Сравнений: ~1/4 N2 в среднем
Перестановок:

Сортировка вставками. Анализ. Сравнений: ~1/4 N2 в среднемПерестановок: ~1/4 N2 в

~1/4 N2 в среднем
Сложность алгоритма: O(N2)
Наилучший случай: если массив

отсортирован, то алгоритм выполняет N-1 сравнение и 0 перестановок.
Наихудший случай: если массив отсортирован в обратном порядке, то алгоритм выполняет ~1/2 N2 сравнений и ~1/2 N2 перестановок

Плюсы:
эффективен на небольших наборах данных (до десятков элементов)
эффективен на частично-отсортированных наборах данных

Минусы: Очень высокая вычислительная сложность O(N2)


Слайд 10 Сортировка простыми обменами. Bubble Sort.
Алгоритм состоит

Сортировка простыми обменами. Bubble Sort. Алгоритм состоит из повторяющихся проходов по

из повторяющихся проходов по массиву
За каждый проход элементы

сравниваются попарно.
Если порядок в паре неверный, то выполняется обмен элементов.
Проходы выполняются n-1 раз или до тех пор, пока на очередном шаге окажется, что обмены больше не нужны, т.е массив отсортирован.

Идея алгоритма

(см. Example5, Project BubbleSort)


Слайд 11 Bubble sort. Demo.
Swap (6,9)
Don’t swap
Swap (2,4)
Swap (2,8)
Конец 1-го

Bubble sort. Demo.Swap (6,9)Don’t swapSwap (2,4)Swap (2,8)Конец 1-го проходаКонец 2-го прохода

прохода
Конец 2-го прохода


Слайд 12 Bubble Sort. Реализация.
1. Выполняем i-ый проход, перестановок не

Bubble Sort. Реализация.1. Выполняем i-ый проход, перестановок не былоint i=0; bool

было
int i=0; bool swapped=false;
2. Сравниваем все пары соседних элементов

a[j], a[j-1]. Если порядок нарушен, выполняем перестановку

for (int j=n-1; j>i; j--)
if ( less(a[j], a[j-1]) )
{
swap(a, j, j-1);
swapped=true;
}

2. Сравниваем все пары соседних элементов a[j], a[j-1]. Если порядок нарушен, выполняем перестановку

for (int j=n-1; j>i; j--)
if ( less(a[j], a[j-1]) )
{
swap(a, j, j-1);
swapped=true;
}

3. Если перестановок не было, то завершаем проходы, иначе следующий проход (i++)
if (!swapped) break;


  • Имя файла: sortirovka-algoritmy-sortirovki.pptx
  • Количество просмотров: 105
  • Количество скачиваний: 0