Схема и алгоритм сортировки методом выбора

Шаги алгоритма:

1. находим минимальное значение в текущем списке

производим обмен этого значения со значением на первой неотсортированной позиции

теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

2. Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.

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

Пример

void selection(Item a[],int l,int r){

 for(int i=l;i<r;i++){

int min=i;

for(int j=i+1;j<=r;j++){

if(a[j]< a[min])

min=j;

}

if(min!=i)

exch(a[i],a[min]);

}

15. Пузырёк

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

// проход сверху вниз

for (j=1; j<=ub; j++) {

if (a[j-1] > a[j]) {

   x=a[j-1]; a[j-1]=a[j]; a[j]=x;

   k=j;

16. Алгоритм вставок

1. В качестве отсортированной части массива принимается первый элемент.

2. Берется очередной элемент из несортированной части. Его значение сохраняется в дополнительной переменной.

3. Осуществляется поиск позиции в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов

4. Для освобождения найденной позиции элементы сдвигаются вправо, после чего на это место вставляется сохраненное ранее значение.

Пункты 2–4 выполняются до полной упорядоченности массива.

17.*Улучшенные алгоритмы сортировки: Шелла, быстрая сортировка

Сначала в исходной последовательности сортируются между собой элементы, отстоящие друг от друга на расстоянии n/2 элементов, затем на расстоянии n/4 и т.д. до тех пор пока не получим 2 последовательности, элементы которых отстоят друг от друга на расстоянии 1-го элемента. После этого делаем сортировку этой полученной последовательсти выбранным методом и на выходе имеем уже полностью отсортированную последовательность.

Быстрая - выбрать элемент, называемый опорным.

сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие. повторить рекурсивно для «меньших» и «больших».

18. *Модели динамических структур данных: стек, очередь

На базе линейных списков могут строится стеки, очереди и деки. Стек представляется как линейный список, в котором включение элементов всегда производятся в начала списка, а исключение - также из начала. Для представления его нам достаточно иметь один указатель - top, который всегда указывает на последний записанный в стек элемент. В исходном состоянии (при пустом стеке) указатель top - пустой. Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой.

Выделим типовые операции над очередями:

добавление элемента в очередь (помещение в хвост);

удаление элемента из очереди (удаление из головы);

проверка, пуста ли очередь;

очистка очереди.