Учеба и Обучение | ИнфоСайт

АЛГОРИТМЫ СОРТИРОВКИ ВЫБОРОМ

Простой линейный выбор

АЛГОРИТМЫ СОРТИРОВКИ ВЫБОРОМ

Простой линейный выбор

Метод предполагает использование рабочего (дополнительного) массива, в который в конечном итоге помещается отсортированный массив. Количество просмотров определяется количеством элементов массива. Сортировка посредством простого линейного выбора сводится к следующему:

1. Найти наименьший (наибольший) элемент, переслать его в рабочий массив и заменить его в исходном массиве величиной, которая больше (меньше) любого реального элемента.

2. Повторить шаг 1. На этот раз будет выбран наименьший (наибольший) из оставшихся элементов.

3. Повторять шаг 1 до тех пор, пока не будут выбраны все N элементов.

Линейный выбор с обменом (сортировка выбором).

Рабочий массив здесь не используется.

Этот метод сортировки основан на следующих принципах:

Например, нужно отсортировать массив по убыванию

Выбирается максимальный элемент.

Он меняется местами с первым элементом a[1]. На первом месте оказывается  максимальный элемент.

Дальше рассматривается только не отсортированная часть массива, и этот процесс повторяется с оставшимися N-1, N-2 элементами и т. д. до тех пор, пока не останется один, наименьший элемент.

Алгоритм метода будет следующим:

Начало цикла (выполнять  для i от 0 до N-1)

               k=i;

max=a[i];

       Начало цикла (выполнять  для j от i+1 до N-1)

если a[j] >max

тогда

       max=a[j];

k=j;

               все

конец цикла

a[k]=a[i];

a[i]=max;

конец цикла

СОРТИРОВКА ОБМЕНОМ

Стандартный обмен (сортировка обменом, метод "пузырька")

Рассмотрим еще один метод сортировки, который основан на следующих принципах.

Пусть необходимо отсортировать массив по убыванию.

Сравниваем первые два элемента. Если первый меньше второго, то меняем их местами.

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

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

Массив будет отсортирован после просмотра, в котором приняли участие только первый и второй элементы.

Начало цикла (выполнять  для i от 0 до N-1)

       Начало цикла (выполнять  для j от 0 до N-1)

если a[j] > a[j+1]

тогда

                               x= a[j];

                               a[j]= a[j+1];

                               a[j+1]=x;

                       все

конец цикла

конец цикла

Оптимизируем алгоритм - можем запомнить, были или не были перестановки в процессе некоторого прохода, и если  перестановок не было, то работу можно заканчивать. Ля этого воспользуемся «булевским принципом»: веем логическую переменную flag. для контроля: был обмен или нет и переменную i1 для запоминания индекса последнего обмена.

Еще нужна одна переменная R – это будет граница, на которой заканчиваем просмотр:

flag = «истина»;

i1=N-1;

Начало цикла: выполнять пока flag = =«истина»;

               flag = «ложь»;

               R=i1;

Начало цикла (выполнять  для j от 1 до R)

если a[j] > a[j+1]

тогда

x= a[j];

a[j]= a[j+1];

a[j+1]=x;

flag = «истина»;

                                               i1=j;

                               все

конец цикла

конец цикла

БЫСТРАЯ СОРТИРОВКА

Метод Хоара

Метод Хоара (Charles Antony Richard Hoare, разраотал агоритм в 1962 г.), называемый также методом быстрой сортировки (Quicksort) основывается на следующем: находится такой элемент, который разбивает множество на два подмножества так, что в одном все элементы больше, а в другом - меньше делящего. Каждое из подмножеств также разделяется на два, по такому же признаку. Конечным итогом такого разделения станет рассортированное множество.

Рассмотрим один из вариантов реализации сортировки Хоора.

Сначала выберем средний элемент. Потом, используя переменные i (цикл:  i=0, i++) и j (цикл:  j=n-1, j--), пройдем по массиву, отыскивая в левой части элементы больше среднего, а в правой - меньше среднего. Два найденных элемента переставим местами. Будем действовать так, пока i не станет больше (или равным) j. Тогда мы получим два подмножества, ограниченные с краев индексами l и r, а в середине - j и i. Если эти подмножества существуют (т.е. i<r и j>l), то теперь выполняем их сортировку по такому же алгоритму

Метод Шелла

Сортировка Шелла (Donald Lewis Shell разработал алгоритм в 1959г.), называемая также «слиянием с обменом» является расширением челночной сортировки.

Алгоритм  челночной  сортировки действует точно также как стандартный обмен до тех пор, пока не возникает необходимость перестановки элементов исходного массива. Сравниваемый меньший элемент поднимается, насколько это возможно, вверх. Этот элемент сравнивается в обратном порядке со своими предшественниками, по направлению к первой позиции. Если он меньше предшественника, то выполняется обмен и начинается очередное сравнение. Когда элемент, передвигаемый вверх, встречает меньший элемент, этот процесс прекращается и нисходящее сравнение возобновляется с той позиции, в которой выполнялся первый обмен.

Сортировка заканчивается, когда нисходящее сравнение выходит на границу массива.

Основная идея алгоритма Шелла состоит в том, что на начальном этапе реализуется сравнивание и перемещение далеко отстоящих друг от друга элементов. Интервал между сравниваемыми элементами (h) постепенно уменьшается до единицы, что приводит к перестановке соседних элементов на последних стадиях сортировки (если это необходимо).

Реализовать метод Шелла можно следующим образом. Начальный шаг сортировки примем равным h=n/2, т.е. 0,5 от общей длины массива, и после каждого прохода будем уменьшать его в два раза. Каждый этап сортировки включает в себя проход всего массива и сравнение отстоящих на h элементов (i=0; j=n/2; i++; j++; до тех пор, пока j<n). Проход с тем же шагом повторяется, если элементы переставлялись. Заметим, что после каждого этапа отстоящие на h элементы отсортированы.

Таким образом, вначале сравниваются (и, если нужно, переставляются) далеко стоящие элементы, а на последнем проходе - соседние элементы.

Выигрыш получается за счет того, что на каждом этапе сортировки либо участвует сравнительно мало элементов, либо эти элементы уже довольно хорошо упорядочены, и требуется небольшое количество перестановок. Последний просмотр сортировки Шелла выполняется по тому же алгоритму, что и в челночной сортировке. Предыдущие просмотры подобны просмотрам челночной обработки, но в них сравниваются не соседние элементы, а элементы, отстоящие на заданное расстояние h. Большой шаг на начальных этапах сортировки позволяет уменьшить число вторичных сравнений на более поздних этапах.

ДВОИЧНЫЙ  ПОИСК

Двоичный поиск применяют для нахождения элемента X в отсортированном массиве a[1..N].

Основная идея заключается в следующем.

Пусть массив отсортирован в порядке убывания:

       1) определяем средний элемент массива a[m], где m = (n+1)/2 ;

       2) сравниваем его с Х, и если Х=a[m], то поиск на этом заканчивается;

       3) если  a[m] < Х, то все элементы от m до n отбрасывают;

       4) если  a[m] > Х, то отбрасывают элементы от 1 до m;

       5) таким образом, каждый раз необходимо пересчитывать левую (L)  или правую (R) границы, т.е. изначально L=1, R=n (первый шаг); на втором шаге или L=m или R=m т.е. на втором шаге либо левая, либо правая граница поменяет свое значение и т.д.;

       6) поиск продолжается до тех пор, пока элемент не будет найден: a[m]=X,  либо пока  левая и права границы поиска не совпадут: (L=R), т.е. объект Х в массиве отсутствует.

количество операций сравнения, которые необходимы для нахождения элемента в упорядоченном массиве при помощи алгоритма бинарного поиска K=[log2 N]+1, где квадратные скобки обозначают целую часть числа находящегося в скобках. Алгоритм имеет следующий вид:

flag = «ложь»;

L=1;

R=N

Начало цикла: выполнять пока (L ≤ R)  и (flag = =«ложь»);

m=(R+L)/2;

если a[m] = = X]

тогда

flag = «истина»;

       иначе                если a[m]> X

                                       тогда

                                               L=m+1;

                                       иначе

                                               R=m+1;

                       все

       все

конец цикла

Если  (flag= = true)  то

                       печать сообщения: «Элемент Х найден, его номер -  m»,

       иначе        печать: «Элемента Х нет!»,

Варианты заданий

1. Программа должна сформировать случайным образом одномерный целочисленный массив из N чисел  в диапазоне от 0 о 99 (значение N – с клавиатуры).

Для этого:

в начале функции main() нужно вызвать стандартную функцию srand(time(NULL));  которая при каждом обращении к ней задает новое стартовое значение для генератора случайных чисел rand() использую для этого текущее системное время компьютера ;

далее в цикле  заполнить массив N – случайными значениями: m[i]=rand()%100;

(rand() возвращает очередное псевдослучайное число в диапазоне от 0 до RAND_MAX, обе функции декларированы в заголовочном файле stdlib.h, а  time() – в time.h).

Теперь программа должна обратиться к функции сортировки sort() передав ей сформированный массив и его размер (предусмотреть подсчет числа перестановок).

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

И в заключение вызывается функция бинарного поиска значения Х, вводимого с клавиатуры. 

№варианта	Алгоритмы сортировки
1.	а). Простой линейный выбор б) Метод Хоара
2.	а). Простой линейный выбор б) Метод Шелла
3.	а) Линейный выбор с обменом (сортировка выбором). б) Метод Хоара
4.	а) Линейный выбор с обменом (сортировка выбором). б) Метод Шелла
5.	а) Стандартный обмен (сортировка обменом, метод "пузырька") б) Метод Хоара
6.	а) Стандартный обмен (сортировка обменом, метод "пузырька") б) Метод Шелла
7.	а) Стандартный обмен с контролем б) Метод Хоара
8.	а) Стандартный обмен с контролем б) Метод Шелла
9.	а). Простой линейный выбор б) Метод Хоара
10.	а). Простой линейный выбор б) Метод Шелла
11.	а) Линейный выбор с обменом (сортировка выбором). б) Метод Хоара
12.	а) Линейный выбор с обменом (сортировка выбором). б) Метод Шелла
13.	а) Стандартный обмен (сортировка обменом, метод "пузырька") б) Метод Хоара
14.	а) Стандартный обмен (сортировка обменом, метод "пузырька") б) Метод Шелла
15	а) Стандартный обмен с контролем б) Метод Хоара

Контрольные вопросы

В чем суть метода сортировки обменом и почему его зовут метод «пузырька»?

Какие группы алгоритмов сортировки можно выделить?

Как работают методы быстрой сортировки?

Как оценить скорость алгоритмов сортировки?

Что представляет из себя двоичный поиск