16.Сортировка методом выбора
При сортировке этим методом упорядоченная последовательность записей создается на том же участке памяти, что и исходная последовательность. В течение первого прохода осуществляется поиск наименьшего элемента. После того как этот элемент найден, его меняют местами с первым элементом исходной последовательности, в результате наименьший элемент занимает первую позицию в формируемой упорядоченной последовательности. Затем осуществляется поиск следующего наименьшего элемента среди оставшихся. Найденный элемент меняется местами со вторым элементом исходной последовательности. После второго прохода окажется сформированной последовательность из двух элементов, первый из которых меньше второго. Поиск элементов со следующим наименьшим значениями ключа и помещение их в соответствующие позиции исходной последовательности продолжится до тех пор, пока все элементы не будут отсортированы в восходящем порядке.
Для
сортировки последовательности из
элементов требуется
проходов, так как на каждом проходе в
соответствующую позицию упорядоченной
последовательности заносится только
один элемент. Для
i-ого
прохода требуется
сравнений.
Следовательно, общее число сравнений
Количество
перестановок элементов зависит от того,
как расположены элементы исходной
последовательности. Однако в любом
случае в течение одного прохода
потребуется не более одной перестановки;
следовательно, максимальное количество
перестановок равно
.
В лучшем случае, когда исходная
последовательность уже упорядочена,
не потребуется ни одной перестановки.
Следдовательно, среднее число перестановок
пропорционально
Пример
8 3 1 2 4
1 3 8 2 4
1 2 8 3 4
1 2 3 8 4
1 2 3 4 8
17.Сортировка методом обмена (метод пузырька)
При
сортировке этим методом упорядоченная
последовательность создается на том
же месте в памяти, где располагалась
исходная последовательность. В процессе
обработки производится попарное
сравнение элементов. Если порядок между
сравниваемыми элементами нарушен, они
меняются местами. Этот метод обмена
часто называют методом пузырька, так
как наименьшие элементы с каждым
проходом, подобно пузырькам, «всплывают»
по направлению к первой позиции
последовательности. После первого
прохода наибольший элемент займет
позицию, а минимальный – переместится
на одну позицию верх(«всплывет»).
На
каждом следующем проходе очередные
наибольшие элементы занимают,
соответственно, позиции
и т.д., в результате чего будет сформирован
упорядоченный массив.
После каждого прохода может быть сделана проверка, были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что последовательность упорядочена и дальнейших проходов не требуется. В течение прохода фиксируется последний элемент, участвующий в обмене. В очередном проходе этот элемент и все последующие в сравнении не участвуют, так как с этой позиции последовательность уже упорядочена.
Число совпадений для этого метода зависит от числа проходов, необходимых для сортировки. В худшем случае, когда последовательность имеет обратную упорядоченность, в течение каждого i-ого прохода выполняются перестановки, а число проходов равно . При этом для сортировки потребуется максимальное число сравнений Cmax, равное сумме членов арифметической прогрессии
В
лучшем случае, когда исходная
последовательность уже упорядочена,
потребуется всего один проход и
сранение. Минимальное число сравнений
.
Среднее число сравнений пропорционально
Число
обменов при сортировке методом пузырька
зависит от степени упорядоченности
исходной последовательности. Если
исходная последовательность полностью
упорядочена, то обменов нет. Максимальное
число обменов в последовательности,
имеющей исходный обратный порядок, т.е.
в том случае, когда надо отсортировать
по возрастанию записи ключа, расположенные
по убыванию ключа. В этом случае обмен
происходит при каждом сравнении и общее
число обменов равно
.
Среднее число обменов пропорционально
Пример
8 3 1 2 4
3 8
1 8
2 8
4 8
3 1 2 4 8
1 2 3 4 8
1 2 3 4 8
1 2 3 4 8