Презентация по информатике а тему "Методы сортировки"

Сортировка одномерного массива

Понятие «Сортировка»

Сортировка – один из наиболее распространенных процессов обработки данных.

Сортировкой числового массива называют расположение его элементов в возрастающем или убывающем по величине порядке.

Сортировка символьного массива заключается в расположении элементов, например, по алфавиту или по длине строк. Сортировка массивов включена в качестве стандартной операции во многие системы прикладного обеспечения (MS Word, MS Excel и др).

Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием.

Существует достаточно много методов (алгоритмов) сортировки массивов. Мы рассмотрим два из них: метод прямого выбора и метод обмена (метод “пузырька”)

Метод прямого выбора

Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:

• Просматривая массив с первого и до последнего элемента, найти минимальный и поменять его местами с первым элементом.
• Просматривая массив со второго и до последнего элемента, найти минимальный и поменять его местами со вторым элементом.
• И, так далее, до последнего элемента.

Пример работы алгоритма:

• Исходный массив: 8, 3, 6, 1, 4

( меняются местами 8 и 1)

• После первого шага: 1 , 3, 6, 8, 4

( меняются местами 3 и 3)

• После второго шага: 1 , 3 , 6, 8, 4

(меняются местами 6 и 4)

• После третьего шага: 1 , 3 , 4 , 8, 6

(меняются местами 8 и 6)

• После четвертого шага: 1 , 3 , 4 , 6 , 8

Алгоритм выбора использует вложенные циклы.

Внешний цикл (счетчик шагов) последовательно выбирает номер элемента массива, куда следует записывать найденный в неупорядоченной части массива минимальный элемент.

Внутренний цикл перебирает номера неупорядоченных элементов при поиске минимального элемента. Для внешнего цикла достаточно шагов на один меньше, чем элементов в массиве.

Метод простого обмена (пузырьковая сортировка)

В основе алгоритма лежит обмен соседних элементов массива.

Каждый элемент массива, начиная с первого, сравнивается со следующим и, если он больше следующего, то элементы меняются местами.

Таким образом, элементы с меньшим значением продвигаются к началу массива, а элементы с большим значением – к концу массива (всплывают), поэтому этот метод иногда называют методом “пузырька”.

Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.

Пример работы алгоритма простого обмена

• Исходный массив: 8, 3, 6, 4, 1 (последовательно меняются местами 8 и 3,8 и 6, 8 и 4, 8 и 1)
• После первого шага: 3, 6, 4, 1, 8

(далее последовательно меняются местами 6 и 4, 6 и 1)

• После второго шага: 3, 4, 1, 6, 8 (последовательно меняются местами 4 и 1)
• После третьего шага: 3, 1, 4, 6, 8 (последовательно меняются местами 3 и 1)
• После четвертого шага: 1, 3, 4, 6, 8