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

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

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

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

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

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

Содержание

2. Задача сортировки (sorting problem)
3. Сортировка выбором. Selection Sort. На каждой итерации
4. Сортировка выбором. Реализация.(см. Example5, Project SelectionSort)1. перемещаемся
5. Сортировка выбором. Анализ. Сравнений: (N-1)+(N-2)+…1+0 ~ N2/2Перестановок:
6. Сортировка вставками. Insertion Sort. двигаемся по массиву
7. Сортировка вставками. Demo.ijijijijijijijij
8. Сортировка вставками. Реализация.1. перемещаемся по массиву слева
9. Сортировка вставками. Анализ. Сравнений: ~1/4 N2 в
10. Сортировка простыми обменами. Bubble Sort. Алгоритм состоит
11. Bubble sort. Demo.Swap (6,9)Don’t swapSwap (2,4)Swap (2,8)Конец 1-го проходаКонец 2-го прохода
12. Bubble Sort. Реализация.1. Выполняем i-ый проход, перестановок
13. Скачать презентацию
14. Похожие презентации

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

Главная
Информатика
Сортировка. Алгоритмы сортировки

Сортировка. Алгоритмы сортировки.http://www.sorting-algorithms.com

Сортировка выбором. 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)

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

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

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

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

(см. Example5, Project SelectionSort)

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

Слайд 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-го

прохода
Конец 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;