Элементарные методы сортировки. Методы внешней сортировки
8 Сортировка вставкой
9 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом вставки Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. f f=1 f – условие выхода из цикла (если f=1, то выход) Val Val – промежуточное значение, используемое для перемещения элементов массив Постановка задачи
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." class="link_thumb"> 10 10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма."> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма."> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма." title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма."> title="10 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма.">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" class="link_thumb"> 11 11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает данное условие? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает данное условие?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает" title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает"> title="11 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Что обозначает">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" class="link_thumb"> 12 12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение j =2 ? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение j =2 ?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов"> title="12 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" class="link_thumb"> 13 13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение i =2 ? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартовое значение i =2 ?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов" title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов"> title="13 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Почему стартов">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" class="link_thumb"> 14 14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли происходит обмен входного j элемента с отсортированным элементом? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли происходит обмен входного j элемента с отсортированным элементом?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои" title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои"> title="14 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Всегда ли прои">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" class="link_thumb"> 15 15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли заменить цикл ПОКА и ЕСЛИ одним циклом ПОКА с условием i>=2 и A>A[i] ? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли заменить цикл ПОКА и ЕСЛИ одним циклом ПОКА с условием i>=2 и A>A[i] ?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за" title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за"> title="15 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Возможно ли за">
A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" class="link_thumb"> 16 16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг Шаг Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг Шаг i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен этот оператор? A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен этот оператор?"> A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен" title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен"> title="16 Начало алгоритма. Шаг 1 Шаг 1 j:=2, Шаг 2 Шаг 2 Пока j=2 и f=0 выполнять: Шаг 2.2.1 Шаг 2.2.1 Если A>A[i] то Val:=A; A:=A[i]; A[i]:=Val, иначе f:=1, Шаг 2.2.2 Шаг 2.2.2 i:=i-1, Шаг 2.3 Шаг 2.3 j:=j+1. Конец алгоритма. Для чего нужен">
18 Суть сортировки: Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.
Сортировка выбором Отсортиро- ванная часть Отсортированная часть Массив отсортирован по возрастанию
20 Постановка задачи А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом выбора. Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. min min – минимальное число в массиве. Imin Imin – номер минимального числа в массиве
25 Суть сортировки: Последовательно просматривается массив и сравнивается каждая пара элементов между собой. При этом "неправильное" расположение элементов устраняется путем их перестановки. Процесс просмотра и сравнения элементов повторяется до просмотра всего массива.
26 Сортировка обменом
27 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом обмена Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. Val Val – промежуточное значение, используемое для перемещения элементов массива Постановка задачи
2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" class="link_thumb"> 28 28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседних элементов Обмен соседних элементов местами, в случае если левый больше правого Формируется отсортированная часть =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседних элементов Обмен соседних элементов местами, в случае если левый больше правого Формируется отсортированная часть"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни" title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни"> title="28 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Сравнение соседни">
2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" class="link_thumb"> 29 29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие такое? =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие такое?"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та" title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та"> title="29 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему условие та">
2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" class="link_thumb"> 30 30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг Шаг i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j уменьшается? Можно ли увеличивать? Что нужно изменить? =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j уменьшается? Можно ли увеличивать? Что нужно изменить?"> =2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j" title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j"> title="30 Начало алгоритма. Шаг 1 Шаг 1 j:=N, Шаг 2 Шаг 2 Пока j>=2 выполнять: Шаг 2.1 Шаг 2.1 i:=1;, Шаг 2.2 Шаг 2.2 Пока iA то Val:=A[i]; A[i]:=A; A:=Val, Шаг 2.2.2 Шаг 2.2.2 i=i+1, Шаг 2.3 Шаг 2.3 j:=j-1. Конец алгоритма. Почему значение j">
35 12 Сортировка Шелла шаг. 4 группы из 2-х элементов шаг. 2 группы из 4-х элементов
36 Сортировка Шелла шаг. 1 группа из 8-ми элементов Массив отсортирован по возрастанию
37 А N Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом Шелла Вспомогательные переменные j j – номер первого элемента остатка. i i – номер перемещаемого элемента. M M- оптимальный шаг P P– промежуточное значение, используемое для перемещения элементов массива Постановка задачи
45 Суть сортировки: Выбирается некоторое значение (x)- барьерный элемент, который определяется округлением до целого деления количества сортируемых элементов на 2; Просматриваем массив, двигаясь слева направо, пока не найдется элемент, больший x Затем просматриваем его справа налево, пока не найдется элемент, меньший x
46 Суть сортировки: Меняем найденные элементы местами. В случае, если не найден наибольший или наименьший элементы, местами меняется средний элемент с найденным наибольшим или наименьшим элементом; Дойдя до середины имеем 2 части массива; Процесс продолжается для каждой части, пока массив не будет отсортирован
7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" class="link_thumb"> 47 47 Быстрая сортировка Барьерный элемент Барьерный элемент Барьерный элемент >7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэтому меняем местами 7 и 12 4>3 Отсортиро- ванная часть 12>11 переносим в правую часть, т. к >11 не переносим, 811 переносим в правую часть, т. к. 16>11, 12>11,не переносим, 11 11=11 поэтому меняем местами 11 и 19 Отсортированная часть 19>12 переносим в правую часть, т. к. 16>12,не переносим, 12 12=12 поэтому меняем местами 12 и 19 19>16 Массив отсортирован по возрастанию Меньше равно 7 Больше 7 7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт"> 7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэтому меняем местами 7 и 12 4>3 Отсортиро- ванная часть 12>11 переносим в правую часть, т. к. 8 12 16>11 не переносим, 811 переносим в правую часть, т. к. 16>11, 12>11,не переносим, 11 11=11 поэтому меняем местами 11 и 19 Отсортированная часть 19>12 переносим в правую часть, т. к. 16>12,не переносим, 12 12=12 поэтому меняем местами 12 и 19 19>16 Массив отсортирован по возрастанию Меньше равно 7 Больше 7"> 7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт" title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт"> title="47 Быстрая сортировка 812371911416 Барьерный элемент 4378123 4 Барьерный элемент 8121119 Барьерный элемент 1219 1619 8>7 переносим в правую часть, т. к. 16>7 не переносим, 47 переносим в правую часть, т. к. 16>7, 8>7,11>7, 19>7 не переносим, 7=7 поэт">
48 А n Пусть нужно отсортировать массив А по возрастанию, в котором n элементов быстрым методом Вспомогательные переменные: t – t –конечный элемент массива m - m - начальный элемент массива x – x – элемент относительно которого перемещаются все остальные элементы. w – w – промежуточное значение, используемое для перемещения элементов массива Постановка задачи
58 Устойчивость – отсортированный массив не меняет порядок элементов с одинаковыми значениями. Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" Параметры оценки алгоритмов
59 Естественность поведения - эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше Параметры оценки алгоритмов
60 Оценка алгоритма сортировки выбором Общее количество сравнений C =N-l + N = (N 2 -N)/2 Общее количество операций n + (n-1) + (n-2) + (n-3) = 1/2 * (n 2 +n) = Theta(n 2) Число обменов
63 Оценка алгоритма сортировки вставкой Для массива потребуется N-1 сравнение. Для массива потребуется (N 2 -N)/2 сравнение. Общее количество операций Theta(n 2)
66 Не эффективный метод, так как включение элемента связано со сдвигом всех предшествующих элементов на одну позицию, а эта операция неэкономна В совокупности устойчивость и естественность поведения алгоритма, делает метод хорошим выбором в соответствующих ситуациях
70 Сравнение методов простой сортировки N N – количество элементов, M M – кол-во пересылок, C – кол-во сравнений МинимумМаксимум Простые включения M=2(n-1) C = n-1 M=2(n-1) С=(n 2 -n)/2 М=(n+3n-4)/2 М=(n 2 +3n-4)/2 Простой обмен C=(n 2 -n)/2M=3(n-1) С=(n 2 -n)/2 М=n/4+3(n-1) М=n 2 /4+3(n-1) Простой выбор C=(n 2 -n)/2 M = 0 С=(n 2 -n)/2 М=(n-n)*1,5 М=(n 2 -n)*1,5 ? Чему будет равно количество пересылок
72 Оценка алгоритма Шелла n 1.2 Время выполнения пропорционально n 1.2, т. к. при каждом проходе используется небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных
73 Оценка алгоритма быстрой сортировки N=2g X N N/2N/2 Если размер массива равен числу, являющемуся степенью двойки (N=2g), и при каждом разделении элемент X находится точно в середине массива, тогда при первом просмотре выполняется N сравнений и массив разделится на две части размерами N/2. Для каждой из этих частей N/2 сравнений и т. д. Следовательно C=N+2*(N/2)+4*(N/4)+...+N*(N/N). N Если N не является степенью двойки, то оценка будет иметь тот же порядок
74 Theta(n). Общее количество операций Theta(n). log n O(n log n) Количество шагов деления (глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n) O(n 2) Если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности, тогда быстродействие O(n 2)
77 Контрольные вопросы? Что такое «сортировка»? ? В чем заключается метод сортировки отбором? ? В чем заключается метод сортировки вставками? ? В чем заключается метод пузырьковой сортировки? ? В чем заключается метод быстрой сортировки? ? В чем заключается метод сортировки Шелла?
78 Контрольные вопросы? Какой алгоритм сортировки считается самым простым? ? Какой алгоритм сортировки считается самым эффективным? ? Сколько существует групп алгоритмов сортировки? ? По каким признакам характеризуются алгоритмы сортировки? ? Что нужно учитывать при выборе алгоритма сортировки?
Введение .
Около трех с половиной десятилетий минуло с тех пор, как в педвузах введено в качестве учебной дисциплины программирование для ЭВМ. При колоссальной скорости изменений в самом предмете, всегда существенно превышавшей скорость центральных издательских механизмов, специально ориентированные на программы педвузов книги выходили не чаще, чем раз в десятилетие – едва ли не соразмерно скорости смены поколений ЭВМ. Сегодня полки книжных магазинов ломятся от изданий по информатике. Однако преподавателю (а более всего студенту) специальные учебные книги, содержание и направленность которых отвечают заданному учебному плану и программе все-таки очень нужны. Сейчас помимо программирования на некоторых специальностях в педвузах введены и другие более сложные спецкурсы, находящиеся на стыке прикладной (дискретной) математики и информатики.
В данной курсовой работе можно познакомится с массивами и узнать о простых и сложных методах их сортировки, а также о том, какие из них наиболее эффективны и в каких случаях.
1. Задачи сортировки.
1.1.Общие положения.
Основная задача – продемонстрировать различные методы сортировки и выделить наиболее эффективные из них. Сортировка – достаточно хороший пример задачи, которую можно решать с помощью многих различных алгоритмов. Каждый из них имеет и свои достоинства, и свои недостатки, и выбирать алгоритм нужно, исходя из конкретной постановки задачи.
В общем сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты.
Таким образом, разговор о сортировке вполне уместен и важен, если речь идет об обработке данных. Первоначальный интерес к сортировке основывается на том, что при построении алгоритмов мы сталкиваемся со многими весьма фундаментальными приемами. Почти не существует методов, с которыми не приходится встречаться при обсуждении этой задачи. В частности, сортировка – это идеальный объект для демонстрации огромного разнообразия алгоритмов, все они изобретены для одной и той же задачи, многие в некотором смысле оптимальны, большинство имеет свои достоинства. Поэтому это еще и идеальный объект, демонстрирующий необходимость анализа производительности алгоритмов. К тому же на примерах сортировок можно показать, как путем усложнения алгоритма, хотя под рукой и есть уже очевидные методы, можно добиться значительного выигрыша в эффективности.
Выбор алгоритма зависит от структуры обрабатываемых данных – это почти закон, но в случае сортировки такая зависимость столь глубока, что соответствующие методы разбили на два класса – сортировку массивов и сортировку файлов (последовательностей). Иногда их называют внутренней и внешней сортировкой, поскольку массивы хранятся в быстрой, оперативной, внутренней памяти машины со случайным доступом, а файлы обычно размещаются в более медленной, но и более емкой внешней памяти, на устройствах, основанных на механических перемещениях (дисках или лентах).
Прежде чем идти дальше, введем некоторые понятия и обозначения. Если у нас есть элементы а , a, …… , а то сортировка есть перестановка этих элементов в массив а k, ak, …… , ak где ak ak ak .
Считаем, что тип элемента определен как INTEGER .
Constn=???; //здесь указывается нужная длина массива
Var A: array of integer;
Выбор INTEGER до некоторой степени произволен. Можно было взять и
другой тип, на котором определяется общее отношение порядка.
Метод сортировки называют устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некотором вторичным ключам (т.е. свойствам), не влияющим на основной ключ.
1.2. Постановка задачи сортировки массивов.
Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте т. е. методы, в которых элементы из массива а передаются в результирующий массив b, представляют существенно меньший интерес. Мы будем сначала классифицировать методы по их экономичности, т. е. по времени их работы. Хорошей мерой эффективности может быть C – число необходимых сравнений ключей и M – число пересылок (перестановок) элементов. Эти числа суть функции от n – числа сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n* logn сравнений, мы сначала разберем несколько простых и очевидных методов, их называют прямыми, где требуется порядка n2 сравнений ключей. Начинать разбор с прямых методов, не трогая быстрых алгоритмов, нас заставляют такие причины:
Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.
Программы этих методов легко понимать, и они коротки.
Усложненные методы требуют большого числа операций, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.
Методы сортировки “ на том же месте “ можно разбить в соответствии с определяющими их принципами на три основные категории:
Сортировки с помощью включения (byinsertion).
Сортировки с помощью выделения (byselection).
Сортировка с помощью обменов (byexchange).
Теперь мы исследуем эти принципы и сравним их. Все программы оперируют массивом а.
Constn=
a: array ofinteger;
2. Методы сортировки массивов.
2.1. Простые методы сортировки массивов.
2.1.1. Сортировка с помощью прямого включения.
Такой метод широко используется при игре в карты. Элементы мысленно делятся на уже “готовую” последовательность а , … , а и исходную последовательность. При каждом шаге, начиная с I = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i- й элементы и перекладывается в готовую последовательность, при этом он вставляется на нужное место.
ПРОГРАММА 2.1. ССОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВКЛЮЧЕНИЯ.
I,J,N,X:INTEGER;
A:ARRAY OF INTEGER;
WRITELN(‘Введите длину массива’);
READ(N);
WRITELN(‘Введите массив ’);
FOR I:=1 TO N DO READ(A[I]);
FOR I:=2 TO N DO
WRITELN("Результат:");
END.
Такой типичный случай повторяющегося процесса с двумя условиями
окончания позволяет нам воспользоваться хорошо известным приемом
“барьера” (sentinel).
Анализ метода прямого включения. Число сравнений ключей (Ci) при i- м просеивании самое большее равно i-1, самое меньшее – 1; если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнений – I/2. Число же пересылок Mi равно Ci + 2 (включая барьер). Поэтому общее число сравнений и число пересылок таковы:
Cmin = n-1 (2.1.) Mmin = 3*(n-1) (2.4.)
Cave = (n2+n-2)/4 (2.2.) Mave = (n2+9*n-10)/4 (2.5.)
Cmax = (n2+n-4)/4 (2.3.) Mmax = (n2+3* n-4)/2 (2.6.)
Алгоритм с прямыми включениями можно легко улучшить, если обратить внимание на то, что готовая последовательность, в которую надо вставить новый элемент, сама уже упорядочена. Естественно остановиться на двоичном поиске, при котором делается попытка сравнения с серединой готовой последовательности, а затем процесс деления пополам идет до тех пор, пока не будет найдена точка включения. Такой модифицированный алгоритм сортировки называется методом с двоичным включением (binaryinsertion).
ПРОГРАММА 2.2. СОРТИРОВКА МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ.
I,J,M,L,R,X,N:INTEGER;
A:ARRAY OF INTEGER;
WRITELN("Введи массив");
FOR I:=1 TO N DO READ(A[I]);
FOR I:=2 TO N DO
X:=A[I];L:=1;R:=I;
FOR J:=I DOWNTO R+1 DO A[J]:=A;
WRITELN("Результат:");
FOR I:=1 TO N DO WRITE(A[I]," ")
END.
Анализ двоичного включения. Место включения обнаружено, если L= R. Таким образом, в конце поиска интервал должен быть единичной длины; значит, деление его пополам происходит I* logI раз. Таким образом:
C = Si: 1i n : [ logI ] (2.7.)
Аппроксимируем эту сумму интегралом
Integral (1:n) log x dx = n*(log n – C) + C (2.8.)
Где C = loge = 1/ ln 2 = 1.4426… . (2.9.)
2.1.2.Сортирвка с помощью прямого выбора.
Этот прием основан на следующих принципах:
Выбирается элемент с наименьшим ключом
Он меняется местами с первым элементом а1.
Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.
ПРОГРАММА 2.3. СОРТИРВКА С ПОМОЩЬЮ ПРЯМОГО ВЫБОРА.
I,J,R,X,N:INTEGER;
A:ARRAY OF INTEGER;
WRITELN("Введи длину массива");
WRITELN("Введи массив");
FOR I:=1 TO N DO READ(A[I]);
FOR I:=1 TO N-1 DO
FOR J:=I+1 TO N DO IF A[J]
WRITELN("Результат:");
FOR I:=1 TO N DO WRITE(A[I]," ")
END.
Анализ прямого выбора. Число сравнений ключей (С), очевидно не зависит от начального порядка ключей. Для С мы имеем C = (n2 – n)/2 (2.10.).
Число перестановок минимально: Mmin = 3*(n-1) (2.11.).
В случае изначально упорядоченных ключей и максимально Mmax = n2/4 + 3*(n-1) (2.12.)
Определим М avg . Для достаточно больших n мы можем игнорировать дробные составляющие и поэтому аппроксимировать среднее число присваиваний на i-м просмотре выражением Fi = lni + g + 1 (2.13.), где g = 0.577216… - константа Эйлера.
Среднее число пересылок Mavg в сортировке с выбором есть сумма Fi с i от 1 до n
Mavg = n*(g + 1) + (Si: 1
Вновь аппроксимируя эту сумму дискретных членов интегралом
Integral (1:n) ln x dx = x*(ln x – 1) = n*ln (n) – n + 1 (2.15.)
Получаем приблизительное значение
Mavg = n*(ln (n) + g) . (2.16.)
2.1.3. Сортировка с помощью прямого обмена .
Как и в методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу.
ПРОГРАММА 2.4. ПУЗЫРЬКОВАЯ СОРТИРОВКА.
PROGRAMBS;
I,J,X,N:INTEGER;
A:ARRAY OF INTEGER;
WRITELN("Введи длину массива");
WRITELN("Введи массив");
FOR I:=1 TO N DO READ(A[I]);
FOR I:=2 TO N DO
FOR J:=N DOWNTO I DO
IF A>A[J] THEN
WRITELN("Результат:");
FOR I:=1 TO N DO
END.
Улучшения этого алгоритма напрашиваются сами собой:
Запоминать, были или не были перестановки в процессе
некоторого прохода.
Запоминать не только сам факт, что обмен имел место, но и
положение (индекс) последнего обмена.
Чередовать направление последовательных просмотров.
Получающийся при этом алгоритм мы назовем “шейкерной” сортировкой (ShakerSoft).
Анализ пузырьковой и шейкерной сортировок. Число сравнений в строго обменном алгоритме C = (n2 – n)/2, (2.17.), а минимальное, среднее и максимальное число перемещений элементов (присваиваний) равно соответственно M = 0, Mavg = 3*(n2 – n)/2, Mmax = 3*(n2 – n)/4 (2.18.)
Анализ же улучшенных методов, особенно шейкерной сортировки довольно сложен. Минимальное число сравнений Cmin = n – 1. Кнут считает, что улучшенной пузырьковой сортировки среднее число проходов пропорционально n – k1 n1/2, а среднее число сравнений пропорционально ½(n2 – n(k2 + lnn)).
ПРОГРАММА 2.5. ШЕЙКЕРНАЯ СОРТИРОВКА.
PROGRAMSS;
J,L,K,R,X,N,I:INTEGER;
A:ARRAY OF INTEGER;
WRITELN("Введи длину массива’);
WRITELN("Введи массив");
FOR I:=1 TO N DO
FOR J:=R DOWNTO L DO
IF A>A[J] THEN
FOR J:=L TO R DO
IF A>A[J] THEN
WRITELN("Результат:");
FOR I:=1 TO N DO
END.
Фактически в пузырьковой сортировке нет ничего ценного, кроме ее привлекательного названия. Шейкерная же сортировка широко используется в тех случаях, когда известно, что элементы почти упорядочены – на практике это бывает весьма редко.
2.2. Улучшенные методы сортировки массивов.
2.2.1.Метод Шелла.
В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сначала отдельно сортируются и группируются элементы, отстоящие друг от друга на расстояние 4. Такой процесс называется четверной сортировкой. В нашем примере восемь элементов и каждая группа состоит из двух элементов. После первого прохода элементы перегруппировываются – теперь каждый элемент группы отстоит от другого на две позиции – и вновь сортируются. Это называется двойной сортировкой. На третьем подходе идет обычная или одинарная сортировка. На каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок.
ПРОГРАММА 2.6. СОРТИРОВКА ШЕЛЛА..
PROGRAMSHELLS;
H: ARRAY OF INTEGER = (15,7,3,1);
I,J,K,S,X,N,M:INTEGER;
A:ARRAY[-16..50] OF INTEGER;
WRITELN("Введи длину массива");
WRITELN("Введи массив");
FOR I:=1 TO N DO
FOR M:=1 TO T DO
FOR I:=K+1 TO N DO
IF S=0 THEN S:=-K;
WRITELN("Результат:");
FOR I:=1 TO N DO
Анализ сортировки Шелла. Нам не известно, какие расстояния дают наилучший результат. Но они не должны быть множителями один другого. Справедлива такая теорема: если k-отсортированную последовательность i-отсортировать, то она остается k-отсортированной. Кнут показывает, что имеет смысл использовать такую последовательность, в которой hk-1 = 3 hk + 1, ht = 1 и t = [ log2 n] – 1. (2.19.)
2.2.2.Сортировка с помощью дерева .
Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди n-1 оставшихся элементов и т. д. Как же усовершенствовать упомянутый метод сортировки? Этого можно добиться, действуя согласно следующим этапам сортировки:
1. Оставлять после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Проделав n-1 сравнений, мы можем построить дерево выбора вроде представленного на рисунке 2.1.
44 12 18 06
44 55 12 42 94 18 06 67
РИСУНОК 2.1. ПОВТОРЯЮЩИЙСЯ ВЫБОР СРЕДИ ДВУХ КЛЮЧЕЙ.
2. Спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путем замены либо на пустой элемент в самом низу, либо на элемент из соседний ветви в промежуточных вершинах (см. рисунки 2.2 и 2.3.).
Д. Уилльямсом был изобретен метод Heapsort, в котором было получено существенное улучшение традиционных сортировок с помощью деревьев. Пирамида определяется как последовательность ключей a[ L], a[ L+1], … , a[ R], такая, что a[ i] a и a[ i] a для i= L… R/2.
Р. Флойдом был предложен некий “лаконичный” способ построения пирамиды на ”том же месте”. Здесь a … a[ n] – некий массив, причем a[ m]… a[ n] (m = [ nDIV 2] + 1) уже образуют пирамиду, поскольку индексов i и j, удовлетворяющих соотношению j = 2 i (или j = 2 i + 1), просто не существует.
44 12 18
44 55 12 42 94 18 67
РИСУНОК 2.2.ВЫБОР НАИМЕНЬШЕГО КЛЮЧА.
12 18
44 12 18 67
44 55 12 42 94 18 67
РИСУНОК 2.3. ЗАПОЛНЕНИЕ ДЫРОК.
Эти элементы образуют как бы нижний слой соответствующего двоичного дерева (см. рисунок 2.4.), для них никакой упорядоченности не требуется. Теперь пирамида расширяется влево; каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент. Получающаяся пирамида показана на рисунке 2.4.
РИСУНОК 2.4.МАССИВ , ПРЕДСТАВЛЕННЫЙ В ВИДЕ ДВОИЧНОГО ДЕРЕВА .
ПРОГРАММА 2.7. HEARSORT.
I,X,L,N,R:INTEGER;
A:ARRAY OF INTEGER;
PROCEDURE SIFT(L,R: INTEGER);
WRITELN("Введи длину массива");
WRITELN("Введи массив");
FOR I:=1 TO N DO
WRITELN(‘Результат:");
FOR I:=1 TO N DO
END.
Анализ Heapsort. Heapsort очень эффективна для большого числа элементов n; чем больше n, тем лучше она работает.
В худшем случае нужно n/2 сдвигающих шагов, они сдвигают элементы на log(n/2), log(n/2 – 1), … , log(n – 1) позиций (логарифм по [основанию 2] «обрубается» до следующего меньшего целого). Следовательно фаза сортировки будет n – 1 сдвигов с самое большое log(n-1), log(n-2), … , 1 перемещениями. Можно сделать вывод, что даже в самом плохом из возможных случаев Heapsort потребуется n* logn шагов. Великолепная производительность в таких случаях – одно из привлекательных свойств Heapsort.
2.2.3. Сортировка с помощью разделения .
Этот улучшенный метод сортировки основан на обмене. Это самый лучший из всех известных на данный момент методов сортировки массивов. Его производительность столь впечатляюща, что изобретатель Ч. Хоар назвал этот метод быстрой сортировкой (Quicksort) . В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, что у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно сдвигаться с двух сторон. Это возможно в том случае, когда мы знаем, что порядок действительно обратный. Однако полученный при этом алгоритм может оказаться и не удачным, что, например, происходит в случае n идентичных ключей: для разделения нужно n/2 обменов. Этих необязательных обменов можно избежать, если операторы просмотра заменить на такие:
В этом случае x не работает как барьер для двух просмотров. В результате просмотры массива со всеми идентичными ключами приведут к переходу через границы массива.
Наша цель – не только провести разделение на части исходного массива элементов, но и отсортировать его. Будем применять процесс разделения к получившимся двум частям, до тех пор, пока каждая из частей не будет состоять из одного-единственного элемента. Эти действия описываются в программе 2.8.
ПРОГРАММА 2.8. QUICKSORT.
A:ARRAY OF INTEGER;
PROCEDURE SORT(L,R: INTEGER);
I,J,X,W: INTEGER;
X:=A[(L+R) DIV 2];
WRITELN("Введи длину массива");
WRITELN("Введи массив");
FOR I:=1 TO N DO READ(A[I]);
WRITELN("Результат:");
FOR I:=1 TO N DO
END.
Анализ Quicksort. Процесс разделения идет следующим образом: выбрав некоторое граничное значение x, мы затем проходим целиком по всему массиву. При этом выполняется точно n сравнений. Ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x.
N*(n-1)/2n-(2n2-3n+1)/6n = (n-1/n)/6 (2.20.)
В том случае, если бы нам всегда удавалось выбирать в качестве границы медиану, то каждый процесс разделения расщеплял бы массив на две половинки, и для сортировки требовалось бы всего n* logn подходов. В результате общее число сравнений было бы равно n* logn, а общее число обменов – n* log(n) /6. Но вероятность этого составляет только 1/ n.
Главный из недостатков Quicksort – недостаточно высокая производительность при небольших n, впрочем этим грешат все усовершенствованные методы, одним из достоинств является то, что для обработки небольших частей в него можно легко включить какой-либо из прямых методов сортировки.
Тесты .
в сортируемой последовательности masi длиной n (i = 0..n - 1) последовательно выбираются элементы начиная со второго (i
в сортируемой последовательности masi длиной n (i=0..n-1) последовательно выбираются элементы начиная со первого (i
в сортируемой последовательности masi длиной n (i=0..n-1) последовательно выбираются элементы начиная со второго (i
в сортируемой последовательности masi длиной n-1 (i=0..n-1) последовательно выбираются элементы начиная со второго (i
найден элемент последовательности mas, для которого masi>x; достигнут левый конец отсортированной слева последовательности.
найден элемент последовательности mas, для которого masi
найден элемент последовательности mas, для которого masi
к исходной последовательности справа добавляется фиктивный элемент X. В начале каждого шага просмотра влево отсортированной части массива элемент X устанавливается в значение того элемента, для которого будет осуществляться поиск места вставки.
к исходной последовательности слева добавляется фиктивный элемент X. В конце каждого шага просмотра влево отсортированной части массива элемент X устанавливается в значение того элемента, для которого будет осуществляться поиск места вставки.
к исходной последовательности слева добавляется фиктивный элемент X. В начале каждого шага просмотра влево отсортированной части массива элемент X устанавливается в значение того элемента, для которого не будет осуществляться поиск места вставки.
к исходной последовательности слева добавляется фиктивный элемент X. В начале каждого шага просмотра влево отсортированной части массива элемент X устанавливается в значение того элемента, для которого будет осуществляться поиск места вставки.
N^2/2 перемещений.
N^2/4 перемещений.
N^2 перемещений.
N/4 перемещений.
Идея сортировки массива прямым включением заключается в том, что
При сортировке массива прямым включением поиск места включения очередного элемента х в левой части последовательности mas может закончиться двумя ситуациями:
При сортировке массива прямым включением для отслеживания условия окончания просмотра влево отсортированной последовательности используется прием «барьера». Суть его в том, что
Сортировка массива прямым включением требует в среднем
Выберите правильный вариант для вставки вместо знака «вопрос» во фрагмент кода сортировки массива прямым включением:
For i:=2 to С ount do
Begin
Tmp:=Arr [i];
j:=i -1;
Begin
Arr :=Arr[j];
j:=j -1;
End ;
Arr :=Tmp;
End ;
вставляет i - й элемент в готовую последовательность, которая пока не отсортирована, для нахождения места для i - го
вставляет i - й i - го элемента используется метод бинарного поиска элемента.
вставляет i - й элемент в готовую последовательность, которая уже отсортирована, для нахождения места для i - го
вставляет i - й элемент в пока готовую последовательность, которая пока не отсортирована, для нахождения места для i - го элемента используется метод Шелла поиска элемента.
N log 2 N сравнений.
log 2 N сравнений.
log 2 (N/ 2 ) сравнений.
N /2*log 2 N сравнений.
станет больше
станет меньше
не изменится.
бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся левее этой позиции, сдвигаются вправо.
бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся правее этой позиции, сдвигаются влево.
бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся правее этой позиции, сдвигаются вправо.
бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся левее этой позиции, сдвигаются влево.
сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии большем h.
сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии меньшем h.
сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии h.
сортировке подвергаются не все подряд элементы последовательности, а только h элементов.
Если h=1, то алгоритм сортировки массива методом Шелла вырождается в
пирамидальную сортировку.
сортировку прямыми включениями.
сортировку слиянием.
сортировку бинарного включения.
последний шаг должен равняться единице.
последний шаг должен равняться нулю.
первый элемент равен последнему элементу.
первый элемент равен предпоследнему элементу.
при каждом проходе используется очень большое число элементов, упорядоченность увеличивается при каждом новом просмотре данных.
при каждом проходе элементы массива не упорядочены, а упорядоченность увеличивается при каждом новом просмотре данных.
при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.
на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной максимальный элемент. Если он найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он не найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он найден, то производится его перемещение на место крайнего правого элемента несортированной левой части массива.
на каждом шаге просмотру подвергается несортированная правая часть массива. В ней ищется очередной минимальный элемент. Если он найден, то производится его перемещение на место крайнего левого элемента несортированной правой части массива.
первый проход: c d b a; второй проход: a b b c; третий проход: a b c d.
d c; третий проход: a b c d.
первый проход: a d b c; второй проход: a cdb; третий проход: a b c d.
первый проход: a d b c; второй проход: a b d c; третий проход: d b c a.
выполняется n раз, а внутренний цикл выполняется n/2 раз.
выполняется n-1 раз, а внутренний цикл выполняется n раз.
выполняется n-1 раз, а внутренний цикл выполняется n/2 раз.
выполняется n раз, а внутренний цикл выполняется n раз.
While (j0) and (Arr[j] ) do
While (j>0) and (Arr[j]>Tmp) do
While (j> 0 ) and (Arr [ j ] ) do
While (j=0) and (Arr[j]=Tmp) do
Алгоритм сортировки массива бинарными включениями
При сортировке массива бинарными включениями всего будет произведено
Изменится ли количество пересылок в сортировке массива бинарными включениями по отношению к количеству сравнений
При сортировке массива методом бинарного включения внутренний цикл поиска с одновременным сдвигом следует разделить:
В чем состоит идея сортировки массива методом Шелла?
При сортировке массива методом Шелла на каждом шаге значение h изменяется, пока не станет (обязательно) равно
При сортировке массива методом Шелла расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что
Эффективность сортировки массива методом Шелла объясняется тем, что
Идея алгоритма сортировки массива прямым выбором заключается в том, что
Если сортировку выбором применить для массива "bdac", то будут получены следующие проходы
Как и в сортировке массива пузырьковым методом в сортировке массива прямым выбором внешний цикл
Вставить во фрагмент кода сортировки массива прямым выбором, вместо знака «вопроса», верное неравенство:
for i:= 1 to n - 1 do
begin
min:= i;
for j:= i + 1 to n do
if ? then
min:= j;
t:= a[i];
a[i] := a;
a := t
end;
a[ min] a[ j].
a > a[j].
При сортировке массива методом прямого выбора в лучшем случае (когда исходный массив уже упорядочен) потребуется поменять местами только?, а каждая операция обмена требует три операции пересылки.
Вставьте вместо знака «вопрос» верный вариант.
являются отображением в памяти дерева специальной структуры - пирамиды.
являются отображением в памяти дерева специальной структуры - дерева.
являются отображением в памяти пирамиды специальной структуры - пирамиды.
являются отображением в памяти куста специальной структуры - дерева.
n-элементов.
(n-1)-элементов.
n/2-элементов.
2*n-элементов.
Алгоритм сортировки массива методом пирамидального выбора предназначен для сортировки последовательности чисел, которые
На рисунке изображено несколько деревьев, из которых лишь одно является пирамидой.
Т4.
Пирамида, показанная на рисунке (одна из четырех), в памяти будет представлена следующим массивом:
n*log n (двоичных) сравнений.
(log n )/2 (двоичных) сравнений.
log n (двоичных) сравнений.
2 * log n (двоичных) сравнений.
если номер позиции большего из элементов больше номера позиции меньшего элемента, то меняем их местами.
если номер позиции меньшего из элементов больше номера позиции большего элемента, то не меняем их местами.
если номер позиции меньшего из элементов больше номера позиции большего элемента, то оставляем их на месте.
если номер позиции меньшего из элементов больше номера позиции большего элемента, то меняем их местами.
n проходов.
(n-1) проходов.
n /2 проходов.
2*n проходов.
таблица не отсортирована и требует дальнейших проходов.
таблица уже отсортирована и требует дальнейших проходов.
таблица уже отсортирована и дальнейших проходов не требуется.
таблица не отсортирована и дальнейших проходов не требуется.
достигает своего места за один проход.
достигает своего места за два прохода.
достигает своего места за три прохода.
достигает своего места за N проходов.
очень быстро достигает своего места.
очень медленно достигает своего места.
не достигает своего места.
достигает середины массива.
двух упорядоченных таблиц.
одной упорядоченной таблицы.
трех упорядоченных таблиц.
двух неупорядоченных таблиц.
попарно сливаются, образуя три новые группы, содержащие втрое больше элементов.
попарно сливаются, образуя две новые группы, содержащие вдвое больше элементов.
попарно сливаются, образуя новые группы, содержащие втрое больше элементов.
попарно сливаются, образуя новые группы, содержащие вдвое больше элементов.
3, 2, 7, 11, 5, 8, 14, 9, 27.
2, 3, 5, 7, 8, 9, 11, 14, 27.
27, 14, 11, 9, 8, 7, 5, 3, 2.
27, 9, 14, 8, 5, 11, 7, 2, 3.
На каждом из n шагов, требуемых для сортировки массива методом пирамидального выбора, нужно
Идея алгоритма сортировки массива прямым обменом заключается в том, что
При использовании метода пузырьковой сортировки массива требуется самое большее
При сортировке массива методом прямого обмена или методом пузырьковой сортировки после каждого прохода через таблицу может быть сделана проверка, были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что
Сортировка массива пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент
Сортировка массива пузырьковым методом обладает одной особенностью: элемент, расположенный в начале массива
В основе метода внутренней сортировки массива лежит процедура слияния
Сущность сортировки массива слиянием состоит в том, что упорядочиваемая таблица разделяется на равные группы элементов. Группы упорядочиваются, а затем
В предложенных тестах правильные ответы выделены курсивом.
Заключение .
В данной курсовой работе рассматриваются задачи сортировки, постановка задачи сортировки массивов. А также основная часть отведена рассмотрению методов: а именно, простые методы сортировки (сортировка с помощью прямого включения, сортировка с помощью прямого выбора, сортировка с помощью прямого обмена) и улученные методы сортировки массивов (метод Шелла, сортировка с помощью дерева, сортировка с помощью разделения). Предложен анализ к каждому из методов сортировки массивов. Разработаны тестовые задания по сортировкам массивов (30 заданий). http://ru.wikipedia.org
МОУ СОШ С. КАМЫШКИ
ТВОРЧЕСКАЯ РАБОТА
Методы сортировки данных
в курсе ОИВТ
Выполнила:
учитель информатики
На I квалификационную категорию
с. Ал-Гай, 2006
Введение. 3
1. Необходимость изучения темы "Методы сортировки данных". 4
2. Подготовительная работа к теме "Методы сортировки данных". 4
3.Методы сортировок. 7
4. Более сложные и более эффективные методы сортировки. 10
5. Сравнительная характеристика методов сортировки. 11
Заключение. 12
ЛИТЕРАТУРА.. 13
Приложение. 14
Приложение. 15
Приложение. 16
Приложение. 20
Приложение. 21
Приложение. 24
Приложение. 26
Приложение. 28
Приложение. 29
Приложение. 34
Приложение. 37
Приложение. 42
Введение
В этой работе рассматривается большая тема "методы сортировки данных", которая является обязательной в курсе ОИВТ
Изучение табличных величин и методов сортировки - неотъемлемая часть любого курса информатики. Это видно хотя бы по тому факту, что эта тема рассматривается во всех распространенных сегодня учебниках, несмотря на различия в идейных и методических установках их авторов.
Процессом сортировки называют действия по упорядочению некоторых данных (таблицу) по ключу. Ключи могут быть разными. Например, преобразовать
1) таблицу чисел по возрастанию,
2) таблицу фамилий - по алфавиту , причем только по первой букве,
3) элементы, стоящие только на четных местах таблицы в убывающем порядке.
Очевидно, что с "отсортированными" данными работать легче и быстрее, чем с произвольно расположенными. Когда элементы "отсортированы", проще найти, например, телефон товарища в телефонной книге на 500 страниц, быстрее найти слово в словаре на 700 страниц.
Важность темы "сортировки" определяется и особой ролью таблиц. Все применения ЭВМ основаны на их способности к быстрой и точной обработке больших объемов информации, а это возможно только когда информация однородна и отсортирована. Таким образом, таблицы как основное средство представления однородной информации неизбежно используются во всех реальных компьютерных программах.
На табличном принципе основана и архитектура современных ЭВМ: память машины можно рассматривать как большой массив байтов, адреса которых располагаются по возрастанию. Следовательно, без понимания информационной сущности таблиц и основных алгоритмов их обработки невозможно формирование полноценных представлений о возможностях ЭВМ и принципах их работы. Отсюда вытекает необходимость темы "Сортировки " в общеобразовательном курсе информатики. Абсолютно необходима эта тема и в углубленном курсе информатики. Для построения сколько-нибудь сложных и содержательных программ необходимо уверенное владение общими принципами применения таблиц и базовыми приемами их обработки.
Элементы сортировки данных излагаются во многих работах различных авторов (см.). Это указывает на актуальность темы "сортировка", изучение их методов, разработки методики преподавания тем из курса ОИВТ, связанных с сортировкой данных.
В МОУ СОШ с. Камышки информатика преподается на протяжении многих лет. За эти годы нам не раз приходилось изменять программу. Иногда приходилось изменять методику изложения и содержание материала, что частично связано с развитием вычислительной техники и появляющимися в связи с этим новыми возможностями и новыми технологиями .
Тема "сортировки" является неотъемлемой частью программы. У учителя имеется большое количество заготовленных алгоритмов решения тех или иных задач. В процессе изучения темы оказывается эффективным: выполнение учеником готовых алгоритмов и программ самому, "вместо компьютера", выполнение "трассировки" алгоритма для тех или иных исходных данных, подбор таких данных, для которых алгоритм будет выполнять наибольшее или наименьшее возможное количество действий. Для каждой темы такая работа не только с компьютером, но и с тетрадью дает, по мнению автора, положительный результат.
Целью данной работы является изложение методики преподавания в 10-11 классах темы "Сортировки элементов", а также тем, связанных с сортировкой данных.
Кроме того, на примере этой темы хотелось бы продемонстрировать ту методику преподавания, которая используется и при преподавании многих других тем.
Методы "быстрой" сортировки, которые являются более сложными для понимания, изучаются на факультативных занятиях.
1. Необходимость изучения темы "Методы сортировки данных"
Изучение любой темы следует начинать с того, чтобы подвести ученика к необходимости этого, показать потребность в решении соответствующего круга проблем, привести доступные для понимания учеников примеры, продемонстрировать использование элементов сортировки в прикладных задачах (на практике, в окружающем нас мире).
Как только мы дали еще интуитивное понятие смысла "сортировки" данных, мы говорим на уроках ОИВТ о ее необходимости, например, сортировки данных по какому-либо признаку. Мы приводим примеры организации личных записных книжек, словарей, телефонных справочников , математических таблиц, энциклопедий. Трудно себе представить, как пользоваться перечисленными объектами, если информация в них не была бы отсортирована.
В словарях слово "сортировка" определяется как распределение, отбор по сортам, качеству, размерам, по сходным признакам, в программировании это слово традиционно используется в более узком смысле.
Под сортировкой в курсе ОИВТ обычно понимают процесс размещения элементов заданного множества объектов в некотором определенном порядке, как правило, в порядке возрастания или убывания (когда сортируемыми элементами являются числа) или в алфавитном порядке (при сортировке текстовой информации).
Очевидно, что отсортированными данными легче пользоваться, чем произвольно расположенными данными. Когда элементы отсортированы, их проще отыскать, проще производить с ними различные операции. В отсортированных данных легче определить, имеются ли пропущенные элементы. Для двух отсортированных таблиц легче найти общие элементы.
Сортировка также является мощным средством ускорения работы практически любого алгоритма, в котором возникает необходимость частого обращения к определенным элементам. Как пишет один из классиков теории программирования Д. Кнут в [ 4 ] "Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования". Анализ этих методов очень полезен и с точки зрения обучения, так как с их помощью можно наглядно проиллюстрировать самые разные ситуации. По словам создателя языка Паскаль, Н. Вирта, "создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки" [ 5 ].
Интересен этот класс алгоритмов еще и тем, что на нем наглядно демонстрируются богатейшие возможности программирования: насколько разными путями можно прийти к одной цели - получение упорядоченного массива! На множестве алгоритмов сортировки становится понятной необходимость сравнительного анализа алгоритмов и оценки их качества, критериями которого являются увеличение быстродействия и экономии памяти. Недаром вопросы, связанные с сортировкой, занимают важное место в школьном курсе информатики
2. Подготовительная работа к теме "Методы сортировки данных".
Поиск и сортировка относятся к табличным и другим сложным структурам данных, поэтому возникает необходимость, прежде всего, в изучении этих сложных структур данных, например, линейных и прямоугольных массивов (таблиц).
Структуру для представления однородной информации в программировании принято называть массивом. (Фактически термины таблица и массив в данном контексте - полные синонимы).
В 10 классе вводится понятие таблицы как новый способ хранения информации. Новые понятия лучше всего воспринимаются учениками в тех случаях, когда они возникают не случайно, а как необходимость при решении каких-либо новых задач. Новое понятие возникает в результате решения специально-подобранной вводной задачи. Фактически ученики сами изобретают недостающие средства, а учитель должен направить формирование этих средств в нужное русло.
Возможная вводная задача для темы "Таблицы" - нахождение периметра многоугольника с известными длинами сторон изложена в приложение 1. Эта задача подводит учеников к основным свойствам табличных величин: таблица состоит из множества простых переменных, к которым можно обращаться не по уникальным именам, а по общему имени таблицы с указанием номера элемента.
После такого введения ученики понимают, зачем нужны таблицы, они готовы разбираться в таких понятиях, как элемент, индекс, обращение к элементу и т. д.
Важный вопрос, на который надо отвечать при решении реальных задач, - когда следует и когда не следует объединять простые переменные в таблицы. Ключ к ответу - понимание таблицы как составной величины, хранящей однородную информацию.
Однородность означает, что все элементы таблицы равноправны: имеют одинаковый, содержательный смысл, при обработке над ними совершаются одинаковые операции.
Чтобы научить школьника решать задачи, необходимо, не только познакомить его с типовыми приемами, но и показать те ситуации, в которых срабатывает тот или иной прием.
Хорошая классификация должна помогать этому, ее применение должно сокращать путь от условия до решения. Для этого необходимо объединить в группы задачи, обладающие одновременно схожими условиями и принципами решения.(см. приложение №2)
Общность условий обеспечивает распознавание задачи учеником, отнесение ее к конкретному типу, то есть создает возможность реального применения классификации.
Общность решений помогает ученику сделать следующий шаг - подобрать метод решения, то есть обеспечивает результативность классификации.
Таким образом, в основу классификации должен лечь некий признак, явно видимый из условия задачи и существенно влияющий на ее решение. В качестве такого признака предлагается рассматривать информационную роль таблицы в алгоритме, то есть вид табличной величины.
Очевидно, что таблица может быть результатом алгоритма(заполнение), аргументом (обработка) и аргументом-результатом (модификация). При более внимательном рассмотрении становится ясно, что обработка (таблица - аргумент) включает слишком большой класс задач, решаемых разными методами. Среди них можно выделить две большие группы: задачи анализа и задачи поиска. В задачах анализа требуется просмотреть всю таблицу и определить какие-то ее характеристики (сумма, произведение, количество элементов с заданным свойством и т. д.) В задачах поиска требуется найти в таблице элемент, обладающий нужным свойством, причем просматривать всю таблицу для этого необязательно.
С другой стороны, многие задачи модификации не требуют освоения специальных приемов и сводятся к комбинации анализа и заполнения. Это, например, известная задача о корректировке отчета (элементы, меньшие100, заменить на 100) и ей подобные. Поэтому выделять модификацию как отдельный класс задач не стоит.
Реальный интерес представляют задачи перестановки, в которых необходимо переставить элементы заданной таблицы в соответствии с какими-то требованиями. Эти задачи не сводятся к другим и могут рассматриваться как самостоятельная группа. Главная задача перестановки - это сортировка элементов массива, то есть элементы массива необходимо переставить так, чтобы они располагались, например, по возрастанию. Задача сортировки массивов не падает с неба, а относится к одной из групп задач на табличные величины. Окончательно получаем такие группы задач:
1. Заполнение
2. Анализ
3. Поиск
4. Перестановка.
Серия задач для каждой группы приведена в приложении 3.
Фактически все основные приемы построения алгоритмов формируются на линейных таблицах. Обработка прямоугольных таблиц приводит к количественному, но не качественному усложнению. Линейная таблица - это основное, первичное понятие, а прямоугольная таблица может быть построена как линейная таблица, состоящая из линейных таблиц. Поэтому в общеобразовательном курсе достаточно рассмотреть только линейные таблицы, быть может, упоминая, но не разбирая подробно, прямоугольные. При реализации углубленного курса изучение прямоугольных таблиц необходимо, но и в этом случае сначала нужно твердо усвоить основные принципы обработки линейных таблиц.
По нашему школьному предмету ОИВТ, фактически, нет сборников задач и опубликованного дидактического материала. Учителю информатики приходится постоянно заниматься подбором и систематизацией условий задач.
Опыт работы за многие годы показал, что кроме составления алгоритмов и программ учителем и учениками желательно уделять большое внимание выполнению готовых алгоритмов.
Учащиеся при этом "обязаны":
1) выполнить алгоритм,
2) определить, что получается при его выполнении на конкретных данных,
3) восстановить условие задачи по готовому алгоритму,
4) проанализировать количество "элементарных" действий при выполнении алгоритма, что отражает скорость работы алгоритма или время его выполнения,
5) подобрать такие данные, для которых количество "элементарных" действий будет минимальным и такие данные, для которых он будет максимальным.
С готовыми алгоритмами можно работать в различных формах, например:
1. при объяснении всем учащимся одного и того же алгоритма;
2. при работе с учеником индивидуально;
3. при объяснении отдельной темы, ученикам, которые пропустили тему, например, по причине болезни;
4. при уяснении темы с теми учащимися, которые не всегда с первого раза усваивают материал.
Работа в различных формах с готовыми алгоритмами позволяет:
1. учитывать индивидуальные особенности учеников;
2. учитывать психологию, их различную по времени реакцию;
3. развивать их логические, алгоритмические способности;
4. углубить знания по соответствующей теме, так как для получения результата он обязан сам, как исполнитель выполнить алгоритм, а значит закрепить все конструкции, глубже понять, как они выполняются, какие особенности имеют.
Еще одним элементом подготовительной работы к теме "сортировка" является исследование массивов переменной размерности в языках программирования. В приложении 4 приведены задания, предлагаемые учащимся для решения.
Подготовительная работа, проведенная с учащимися в 10-х классах, позволяет далее перейти непосредственно к изучению методов сортировки.
Итак в первый год обучения (в 10 классе) заложен фундамент изучения таблиц, проработкой серии задач и алгоритмов на выбор максимальных и минимальных элементов, перестановку элементов и т. д.
В 11-ом классе - мы вплотную подходим к методам сортировки, опираясь на изученные алгоритмы обработки таблиц.
Рассматриваются задачи поиска нужного элемента, составление словарей, справочников, составление лотерейных таблиц, списка учеников в журнале.
Для решения многих задач удобно сначала упорядочить данные по определенному признаку.
Данные, например, элементы массива, можно отсортировать:
по возрастанию - каждый следующий элемент больше предыдущего:
а[ 1 ] < a < a[n];
по неубыванию - каждый следующий элемент не меньше предыдущего:
а <= а <=. . .<= а[n];
по убыванию - каждый следующий элемент меньше предыдущего:
а [ 1 ]> а> ... >а[n],
по невозрастанию - каждый следующий элемент не больше предыдущего:
а [ 1 ] >= а >= ... >=a[n].
3.Методы сортировки
Существует довольно много различных методов сортировки, отличающихся друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки, время выполнения и объем занимаемой ОП. Рассмотрим подробно некоторые из указанных методов. Сначала приведены четыре простых метода. Каждый учитель может выбирать любой порядок изучения указанных методов, если предложенный порядок не устраивает.
Однако, перед тем как рассматривается любой из метод сортировки необходимо повторить отдельных уже изученных алгоритмов, на которые этот метод опирается.
Сначала рассмотрим два метода сортировки:
сортировку выбором (или линейную) и сортировку обменом (или пузырьковую).
Оба метода не очень эффективны и на практике используются крайне редко. Но тогда почему ими нужно вообще заниматься? Во-первых, во многих простых случаях (например, когда требуется отсортировать всего 20-25 чисел) они вполне удовлетворительны. Во-вторых, эти методы интересны для нас тем, что в них моделируется естественное поведение человека, осуществляющего сортировку в ручную. Именно эти два метода легче всего описываются в форме четких алгоритмов и приводят к простой программной реализации.
Рассмотрим сортировку выбором.
Сортировка выбором состоит в том, что сначала в неупорядоченной последовательности выбирается минимальный элемент. Этот элемент исключается из дальнейшей обработки, а оставшаяся последовательность элементов принимается за исходную, и процесс повторяется до тех пор, пока все элементы не будут выбраны. Очевидно, что выбранные элементы образуют упорядоченную последовательность. Выбранный в исходной последовательности минимальный элемент размещается на предназначенном ему месте упорядоченной последовательности несколькими способами:
1. Минимальный элемент после i-го просмотра перемещается на i-е место (i=1, 2 , 3, другого массива, а в старом, исходном, на месте выбранного размещается какое-то очень большое число, превосходящее по величине любой элемент сортируемого массива. Измененный таким образом массив принимается за исходный, и осуществляется следующий просмотр. Очевидно, что при этом размер обрабатываемого массива на 1 меньше размера предыдущего.
2. Минимальный элемент после i-го просмотра перемещается на i-ое место (i=1, 2, 3, заданного массива, а элемент с i-го места - на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т. е. размер каждого последующего обрабатываемого массива на 1 меньше размера предыдущего.
Этот метод сортировки обычно применяется для массивов, не содержащих повторяющихся элементов. Для достижения поставленной цели можно действовать следующим образом:
1) выбрать максимальный элемент массива;
2) поменять его местами с последним элементом (после этого наибольший элемент будет стоять на своем месте);
3) повторить пункты. 1-2 с оставшимися п-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в ней максимальный элемент и поменять его местами с предпоследним; (п-1)-м элементом массива и так далее, пока не останется один элемент, уже стоящий на своем месте.
Всего потребуется п-1 раз выполнить эту последовательность действий. В процессе сортировки будет увеличиваться отсортированная часть массива, а не отсортированная, соответственно, уменьшаться.
Итак, этот метод основывается на нахождении максимального (минимального) значения и перестановках. Причем эти алгоритмы уже отработаны и мы просто на них опираемся. Поэтому перед тем, как рассматривать данный метод сортировки необходимо вспомнить решение этих задач. Единственная трудность, возникающая при составлении алгоритма, это то, что мы работаем с частью табличной величины. На примере данного алгоритма можно продемонстрировать использование вспомогательных алгоритмов или процедур, так как поиск максимального значения можно выделить как самостоятельную программу, то есть как процедуру.
Алгоритмы, реализующие этот метод, рассмотрены в приложении 5.
Можно предложить ученикам:
1. Подсчитать количество произведенных сравнений типа А[I] < AF.
2. Подсчитать количество произведенных перестановок типа Swap (A, B).
Проанализировав первый и второй способы с точки зрения эффективности алгоритма, который выражается в наименьшем количестве выполняемых пересылок и сравнений, вместе с учениками следует записать ещё один, третий способ сортировки выбором (см. приложение 5).
Ход сортировки третьим способом для сортировки массива 30, 17, 73, 47, 22, 11, 65, 54 отразим в таблице
На последующих уроках информатики следует закрепить изученный метод сортировки выбором.
Возвращаясь ещё раз к вопросу об эффективности алгоритмов сортировки выбором, установим, что наименьшее количество действий будет выполняться для исходного массива, уже отсортированного уже в нужном порядке. Наибольшее количество действий будет выполняться для исходного массива, отсортированного в "противоположном смысле".
Рассмотрим сортировку обменом (метод "Пузырька").
Сортировка обменом - метод, при котором все соседние элементы массива попарно сравниваются друг с другом и меняются местами в том случае, если предшествующий элемент больше последующего. В результате этого максимальный элемент постепенно смещается вправо и, в конце концов, занимает свое крайне правое место в массиве, после чего он исключается из дальнейшей обработки. Затем процесс повторяется, и свое место занимает второй по величине элемент, который также исключается из дальнейшего рассмотрения. Так продолжается до тех пор, пока вся последовательность не будет упорядочена.
Если последовательность сортируемых чисел расположить вертикально (первый элемент - внизу) и проследить за перемещениями элементов (рис. 2 в приложении 6), то можно увидеть, что большие элементы, подобно пузырькам воздуха в воде, "всплывают" на соответствующую позицию. Поэтому "сортировку", таким образом, называют еще сортировкой методом "пузырька", или "пузырьковой" сортировкой.
Сортировка методом простого обмена может быть применена для любого массива.
Итак, в сортировке "обменом" все соседние элементы попарно сравниваются друг с другом и меняются местами, если предшествующий элемент больше последующего. То есть мы опять основываемся на уже отработанных алгоритмах перестановки элементов.
Описание этого метода подробнее в приложении 6.
"Шейкер" - сортировка.
Несмотря на все сделанные выше усовершенствования, "пузырьковая" сортировка следующего (почти упорядоченного!) массива 5, 7, 12, 28, 36, 85, 2 будет проведена за семь проходов. Это связано с тем, что при сортировке, рассматриваемым методом, за один проход элемент не может переместиться влево больше чем на одну позицию. Так что если минимальный элемент массива находится в его правом конце (как в рассматриваемом примере), то придется выполнить максимальное число проходов. Поэтому естественно напрашивается еще одно улучшение метода "пузырьковой" сортировки - попеременные проходы массива в обоих направлениях, а не только от его начала к концу. В этом случае время сортировки может несколько сократиться. Такой метод сортировки называется "шейкер"-сортировкой (от английского слова shake - трясти, встряхивать). Его работа показана на примере сортировки массива из 8 элементов (на рис. 3 в приложении 7). Алгоритмы этого метода подробно изложены в приложении 7.
Сортировка подсчетом
Этот простой и легкий для понимания метод заключается в том, что каждый элемент массива сравнивается со всеми остальными. Место каждого элемента в отсортированном массиве зависит от числа элементов, меньших его. Иными словами, если некоторый элемент превышает 13 других, то его место в упорядоченной последовательности - 14. Следовательно, для сортировки необходимо сравнить попарно все элементы и подсчитать, сколько из них меньше каждого отдельного элемента. После этого все элементы исходного массива можно разместить на соответствующих им местах в новом, специально созданном массиве. Алгоритм сортировки подсчетом подробно изложен в приложении 8.
Сортировка вставками (методом прямого включения).
Сортировка вставками, так же как и сортировка методов простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов. Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На k-м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть a < a< . . . < a. Далее необходимо взять k-й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое j (1<=j<=k-1), что a<=a[k]
Более подробно этот метод рассмотрен в приложении 9
4. Более сложные и более эффективные методы сортировки.
При решении более сложных задач, в том числе олимпиадных, приходится обрабатывать большие наборы данных. Применение простых для понимания, но медленно работающих методов сортировки, изложенных в предыдущем разделе, становится нецелесообразно. Ученики начинают искать другие методы сортировки. Именно, когда ученикам недостает более эффективных методов сортировки и рассматриваются эти более сложные методы.
Преследуемая цель: знакомство с эффективными алгоритмами сортировки и поиска; реализация рекурсивных процедур и функций. Изучение быстрых методов сортировки проводится на кружках и факультативных занятиях.
Обменная сортировка с разделением (сортировка Хоара)
Сортировка методом простого обмена (методом "пузырька") является в среднем самой неэффективной. Это обусловлено самой идеей метода, который требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы. Можно существенно улучшить метод сортировки, основанный на обмене. Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением. Он основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. Предложил этот метод Ч. в 1962 году. Поскольку производительность этого метода впечатляюща, автор назвал его "быстрой сортировкой".
Более подробно этот метод рассмотрен в приложении 10.
Сортировка методом слияний
Существует еще один метод сортировки элементов массива, эффективность которого сравнительно велика, - метод слияний.
Перед тем как давать этот метод сортировки, ученикам модно предложить следующую задачу, которая когда-то была олимпиадной, а теперь решается на обычных уроках.:
Причем с минимальным количеством сравнений. На алгоритме этой задачи, которую могут решить сами ученики без подсказки учителя, и построен метод слияния.
Конечно, можно решить задачу, используя метод вставок - каждый элемент массива А разместить на соответствующем ему месте в массиве В. Однако, при этом количество сравнений превысит n+m.
Способ решения задачи изложен в приложении11.
Метод сортировки "слиянием" состоит в разбиении данного массива на несколько частей, которые сортируются по отдельности и впоследствии "сливаются" в одну.
Пусть массив а разбивается на части длиной k, тогда первая часть - a[I], a , . . ., a [k], вто-рая - a, a,..., a и так далее. Если n не делится на k, то в последней части будет менее k элементов.
После того как массивы-части упорядочены, можно объединить их в упорядоченные массивы-части, состоящие не более чем из 2k элементов, которые далее объе-динить в упорядоченные массивы длиной не более 4k, и так далее, пока не получится один упорядоченный массив. Таким образом, чтобы получить отсортированный массив этим методом, нужно многократно " сливать" два упорядоченных отрезка массива в один упорядоченный отрезок. При этом другие части массива не затрагиваются. Более подробно этот метод как факультативный материал рассмотрен в приложении 12.
5. Сравнительная характеристика методов сортировки.
Вспомним один из простых методов - метод подсчета. Поскольку этот метод, несмотря на усовершенствование, требует сравнения всех пар элементов, то продолжительность сортировки массива из n элементов будет пропорциональна n2. Несколько лучшие показатели имеют методы сортировки вставками, обменом и выбором, однако и в них продолжительность работы процедур также пропорциональна n2. Вместе с тем можно показать, что время, затрачиваемое на упорядочивание массива такими методами, как, например, быстрая сортировка или пирамидальная сортировка, пропорционально n log2n, т. е. значительно меньше. Поэтому все рассмотренные методы сортировки подразделяют на простые (n2) и усовершенствованные, или "логарифмические" (n log2n) .
Подробный анализ основных методов сортировки проведен в работах . В качестве показателей для оценки того или иного метода в них используются количество сравнений и количество перемещений элементов в ходе сортировки. Однако эти характеристики не учитывают затрат времени на другие операции, такие, как управление циклами, и др. Очевидно, что критерием для сравнения различных методов является время, затрачиваемое на сортировку. Данные о времени выполнения процедур сортировки получены Н. Виртом .
Конечно, современные компьютеры работают значительно быстрее, чем тогда, когда были проведены расчеты, т. е. данные, приведенные в , устарели. В то же время относительные показатели различных методов в целом не изменились. В приложении 12 представлены относительные характеристики девяти вариантов методов сортировки, полученные на основе результатов, приведенных Н. Виртом.
Приведенные данные демонстрируют явное различие методов: n2 и n log2n. Из таблицы 1 видно, что наилучшим среди простых методов является сортировка вставками, среди усовершенствованных - быстрая сортировка.
Н. Вирт отмечает также следующее:
- "пузырьковая" сортировка является наихудшей среди всех сравниваемых методов. Ее улучшенный вариант - "шейкер" - сортировка - все-таки хуже, чем сортировка простыми вставками и сортировка выбором;
- особенностью быстрой сортировки является то, что она сортирует массив с элементами, расположенными в обратном порядке практически так же, как и отсортированный в прямом порядке.
Следует добавить, что приведенные результаты были получены при сортировке числовых массивов. Если же значением элементов массива являются данные типа "запись", в которых сопутствующие поля (компоненты) занимают в 7 раз больше памяти, чем числовое поле, по которому проводится сортировка, то картина изменится.
В таблице 2 даны сравнительные характеристики методов сортировки массивов данных типа "запись".
Видно, что
1) сортировка выбором дает существенный выигрыш и оказывается лучшим из простых методов;
2) "пузырьковая" сортировка по-прежнему является наихудшим методом;
3) быстрая сортировка даже укрепила свою позицию в качестве самого быстрого метода и оказалась действительно лучшим алгоритмом сортировки.
Оценка алгоритма сортировки
Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:
Классификация алгоритмов сортировки
- Устойчивость (stability) - устойчивая сортировка не меняет взаимного расположения равных элементов.
- Естественность поведения - эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:
- Внутренняя сортировка
оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
- В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
- Внешняя сортировка
оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы "видим" только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
- Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
- Объём данных не позволяет им разместиться в ОЗУ.
Также алгоритмы классифицируются по:
- потребности в дополнительной памяти или её отсутствии
- потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой
Список алгоритмов сортировки
В этой таблице n - это количество записей, которые необходимо упорядочить, а k - это количество уникальных ключей.
Алгоритмы устойчивой сортировки
- Сортировка пузырьком (англ. Bubble sort ) - сложность алгоритма: O(n 2) ; для каждой пары индексов производится обмен, если элементы расположены не по порядку.
- Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) - Сложность алгоритма: O(n 2)
- Сортировка вставками (Insertion sort) - Сложность алгоритма: O(n 2); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда
- Блочная сортировка (Корзинная сортировка, Bucket sort) - Сложность алгоритма: O(n ); требуется O(k ) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций "переставить" и "сравнить".
- Сортировка подсчётом (Counting sort) - Сложность алгоритма: O(n +k ); требуется O(n +k ) дополнительной памяти (рассмотрено 3 варианта)
- Сортировка слиянием (Merge sort) - Сложность алгоритма: O(n log n ); требуется O(n ) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем - сливаем упорядоченные списки
- In-place merge sort - Сложность алгоритма: O(n 2), O(n log 2 n ) или O(n log n ) в зависимости от применяемого алгоритма слияния.
- Двоичное дерево сортировки (Binary tree sort) - Сложность алгоритма: O(n log n ); требуется O(n ) дополнительной памяти
- Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) - Сложность алгоритма: O(n +k ); требуется O(k ) дополнительной памяти
- Гномья сортировка (Gnome sort) - Сложность алгоритма: O(n 2)
Алгоритмы неустойчивой сортировки
- Сортировка выбором (Selection sort) - Сложность алгоритма: O(n 2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка
- Сортировка Шелла (Shell sort) - Сложность алгоритма: O(n log 2 n ); попытка улучшить сортировку вставками
- Сортировка расчёской (Comb sort) - Сложность алгоритма: O(n log n )
- Пирамидальная сортировка (Сортировка кучи, Heapsort) - Сложность алгоритма: O(n log n ); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
- Плавная сортировка (Smoothsort) - Сложность алгоритма: O(n log n )
- Быстрая сортировка (Quicksort) - Сложность алгоритма: O(n log n ) - среднее время, O(n 2) - худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
- Introsort - Сложность алгоритма: O(n log n ), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
- Patience sorting - Сложность алгоритма: O(n log n + k ) - наихудший случай, требует дополнительно O(n + k ) памяти, также находит самую длинную увеличивающуюся подпоследовательность
- Обменная поразрядная сортировка - Сложность алгоритма: O(n ·k ); требуется O(k ) дополнительной памяти
Непрактичные алгоритмы сортировки
- Bogosort - O(n ·n !) в среднем. Произвольно перемешать массив, проверить порядок.
- Сортировка перестановкой - O(n ·n !) - худшее время. Генерируются всевозможные перестановки исходного массива и для каждой осуществляется проверка верного порядка.
- Глупая сортировка (Stupid sort) - O(n 3); рекурсивная версия требует дополнительно O(n 2) памяти
- Bead Sort - O(n ) or O(√n
- Блинная сортировка (Pancake sorting) - O(n ), требуется специализированное аппаратное обеспечение
Алгоритмы, не основанные на сравнениях
- Блочная сортировка (Корзинная сортировка, Bucket sort)
- Лексикографическая или поразрядная сортировка (Radix sort)
- Сортировка подсчётом (Counting sort)
Остальные алгоритмы сортировки
См. также
- Ёмкостная сложность алгоритма
- Сортирующие сети (сравнение)
- Сравнивание
- Трансформация Шварца
- Параллельная сортировка
Литература
- Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. - 2-е изд. - М.: «Вильямс» , 2007. - С. 824. - ISBN 0-201-89685-0
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс» , 2006. - С. 1296. - ISBN 0-07-013151-1
- Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. - СПб.: ДиаСофтЮП, 2003. - С. 672. - ISBN 5-93772-081-4
Ссылки
- Анимированное сравнение алгоритмов сортировки (англ.)
Wikimedia Foundation . 2010 .
Смотреть что такое "Методы сортировки" в других словарях:
класс сортировки - Классификация контролируемого изделия в одном диапазоне или в нескольких диапазонах требуемых характеристик, например твердости, состава материала или размеров. [Система неразрушающего контроля. Виды (методы) и технология неразрушающего контроля … Справочник технического переводчика
ГОСТ Р ИСО 14644-3-2007: Чистые помещения и связанные с ними контролируемые среды. Часть 3. Методы испытаний - Терминология ГОСТ Р ИСО 14644 3 2007: Чистые помещения и связанные с ними контролируемые среды. Часть 3. Методы испытаний оригинал документа: 3.2.11 U дескриптор (U descriptor): Полученное или заданное количество частиц, включая ультрамелкие… …
ГОСТ Р ИСО 2859-5-2009: Статистические методы. Процедуры выборочного контроля по альтернативному признаку. Часть 5. Система последовательных планов на основе AQL для контроля последовательных партий - Терминология ГОСТ Р ИСО 2859 5 2009: Статистические методы. Процедуры выборочного контроля по альтернативному признаку. Часть 5. Система последовательных планов на основе AQL для контроля последовательных партий оригинал документа: 3.36… … Словарь-справочник терминов нормативно-технической документации
У этого термина существуют и другие значения, см. Триаж (значения). Триаж во Франции, Первая мировая война. Медицинская сортир … Википедия
- (Selection sort) алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное… … Википедия
Алгоритмом сортировки называется алгоритм для упорядочения некоторого множества элементов. Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания множества элементов по возрастанию или убыванию.
В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они располагаются рядом друг за другом в любом порядке. Однако иногда бывает полезно сохранять первоначальный порядок элементов с одинаковыми значениями.
В алгоритмах сортировки лишь часть данных используется в качестве ключа сортировки . Ключом сортировки называется атрибут (или несколько атрибутов), по значению которого определяется порядок элементов. Таким образом, при написании алгоритмов сортировок массивов следует учесть, что ключ полностью или частично совпадает с данными.
Алгоритм преобразования массива в пирамиду (построение пирамиды) . Пусть дан массив x,x,...,x[n] .
Шаг 1. Устанавливаем k=n/2 .
Шаг 2. Перебираем элементы массива в цикле справа налево для i=k,k-1,...,1 . Если неравенства x i > x 2i , x i > x 2i+1 не выполняются, то повторяем перестановки x i с наибольшим из потомков. Перестановки завершаются при выполнении неравенств x i > x 2i , x i > x 2i+1 .
Алгоритм сортировки пирамиды .
Рассмотрим массив размерности n , который представляет пирамиду x,x,...,x[n] .
Шаг 1. Переставляем элементы x и x[n] .
Шаг 2. Определяем n=n-1 . Это эквивалентно тому, что в массиве из дальнейшего рассмотрения исключается элемент x[n] .
Шаг 3. Рассматриваем массив x,x,...,x , который получается из исходного за счет исключения последнего элемента. Данный массив из-за перестановки элементов уже не является пирамидой. Но такой массив легко преобразовать в пирамиду . Это достигается повторением перестановки значения элемента из x с наибольшим из потомков. Такая перестановка продолжается до тех пор, пока элемент из x не окажется на месте элемента x[i] и при этом будут выполняться неравенства x[i] > x, x[i] > x . Тем самым определяется новое