Сортировки методами прямого включения и выбора
7.1. Цель работы:
- исследовать и изучить методы сортировки включением и выбором;
- овладеть умениями и навыками написания на языке программирования С++ программ с использованием сортировки включением и выбором.
Порядок выполнения работы
- ознакомиться с краткой теорией и примерами решения задач, относящихся к сортировке структур данных включением и выбором;
- ответить на контрольные вопросы и получить оценку по знанию теории;
- получить задание на выполнение конкретного варианта лабораторной работы и выполнить его;
- написать и отладить программу решения задачи на языке С++;
- составить отчет по лабораторной работе и защитить его у преподавателя.
Содержание отчета по ЛР
- наименование ЛР и ее цель;
- задание на ЛР согласно варианту;
- листинг приложения, обеспечивающей успешное решение студентом полученного варианта задачи;
- результаты работы программы.
Краткая теория
При обработке данных в ЭВМ важно знать и информационное поле элемента, и его размещение в памяти машины. Для этих целей используется сортировка. Итак, сортировка- -это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание значения ключа от начала к концу в массиве.
Различают следующие типы сортировок:
· · внутренняя сортировка - это сортировка, происходящая в оперативной памяти машины
· · внешняя сортировка - сортировка во внешней памяти.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей, делают перестановку указателей, т.е. сам массив не перемещается. Это метод сортировки таблицы адресов.
При сортировке могут встретиться одинаковые ключи. В этом случае при сортировке желательно расположить после сортировки одинаковые ключи в том же расположении, что и в исходном файле. Это устойчивая сортировка.
Эффективность сортировки можно рассмотреть с нескольких критериев:
· · время, затрачиваемое на сортировку
· · объем оперативной памяти, требуемой для сортировки
· · время, затраченное программистом на написание программы
Выделяем первый критерий, поскольку будем рассматривать только методы сортировки «на том же месте », то есть не резервируя для процесса сортировки дополнительную память. Эквивалентом затраченного на сортировку времени можно считать количество сравнений при выполнении сортировки и количество перемещений.
Различают следующие методы сортировки:
· · строгие (прямые) методы
· · улучшенные методы
Рассмотрим преимущества прямых методов:
1. Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.
2. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.
3. Усложненные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых количествах элементов прямые методы оказываются быстрее, хотя при больших количествах элементов их использовать, конечно, не следует.
Методы сортировки "на том же месте" можно разбить в соответствии с определяющими их принципами на 3 категории:
1. Сортировки с помощью включения (by insertion)
2. Сортировки с помощью выбора (by selection)
3. Сортировки с помощью обменов (by exchange)
Сортировка методом прямого включения
Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже "готовую" последовательность a(1),...,a(i-1) и исходную последовательность. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i -й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.
Алгоритм сортировки прямым включением таков:
for x=2 to n do
x=a[i]
включение х на соответствующее место среди a[1]...a[i]
end
В реальном процессе поиска подходящего места удобно, чередуя сравнения сравнивать текущий элемент с очередным элементом a(j), а затем
- либо х вставляется на свободное место,
- либо a(j) сдвигается (передается) вправо и процесс "уходит" влево.
Обратите внимание, что процесс просеивания может закончиться при выполнении одного из двух следующих различных условий:
1. Найден элемент a(j) с ключом, меньшим, чем ключ у х.
2. Достигнут левый конец готовой последовательности.
Сортировка методом прямого выбора
В общем сортировка - это процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки облегчить последующий поиск элементов в таком отсортированном множестве. Это почти универсальная, фундаментальная деятельность. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах почти везде, где нужно искать хранимые объекты. Даже малышей учат держать свои вещи "в порядке", и они уже сталкиваются с некоторыми видами сортировок задолго до того, как познакомятся с азами арифметики.
Таким образом, разговор о сортировке вполне уместен и важен, если речь идет об обработке данных. Что может легче сортироваться, чем данные? Тем не менее наш первоначальный интерес к сортировке основывается на том, что при построении алгоритмов мы сталкиваемся со многими весьма фундаментальными приемами. Почти не существует методов, с которыми не приходится встречаться при обсуждении этой задачи. В частности, сортировка это идеальный объект для демонстрации огромного разнообразия алгоритмов, все они изобретены для одной и той же задачи, многие в некотором смысле оптимальны, большинство имеет свои достоинства. Поэтому это еще и идеальный объект, демонстрирующий необходимость анализа производительности алгоритмов. К тому же на примерах сортировок можно показать, как путем усложнения алгоритма, хотя под рукой и есть уже очевидные методы, можно добиться значительного выигрыша в эффективности.
Выбор алгоритма зависит от структуры обрабатываемых данных это почти закон, но в случае сортировки такая зависимость столь глубока, что соответствующие методы были даже разбиты на два класса сортировку массивов и сортировку файлов последовательностей. Иногда их называют внутренней и внешней сортировкой, поскольку массивы хранятся в быстрой оперативной, внутренней памяти машины со случайным доступом, а файлы обычно размещаются в более медленной, но и более емкой внешней памяти, на устройствах, основанных на механических перемещениях дисков или лент. На примере сортировки пронумерованных карточек становится очевидным существенное различие в этих подходах. Если карты "выстроены" в виде массива, то они как бы лежат перед сортирующим, он видит каждую из них и имеет к ней доступ. Если же карты образуют файл, то это предполагает, что видна только верхняя карта в каждой из стопок. Такое ограничение, конечно же, серьезно повлияет на метод сортировки, но ничего не поделаешь: ведь карточек может быть так много, что все они на столе не поместятся.
Прежде чем идти дальше, введем некоторые понятия и обозначения. Ими мы будем пользоваться далее. Если у нас есть элементы а1, а2,..., аn, то сортировка есть перестановка этих элементов массив аk1, аk2,..., аkn, где при некоторой упорядочивающей функции f выполняются отношения f аk1 <= f аk2 <=... <= f аkn.
Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явная компонента поля каждого элемента. Ее значение называется ключом key элемента. Поэтому для представления элементов хорошо подходят такие образования, как запись, а графически это представляется так:
a) 
Отсортированный массив:
b) 
Массив, отсортированный другим методом
c) 
Говоря об алгоритмах сортировки, мы будем обращать внимание лишь на компоненту - ключ, другие же компоненты можно даже и не определять (b). Чтобы уменьшить эти затраты, сортировку производят в таблице адресов ключей. После сортировки перестанавливают указатели. Это метод сортировки таблицы адресов (c). Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некоторым вторичным ключам (т.е. свойствам), не влияющим на основной ключ.
Основное условие: выбранный метод сортировки массивов должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте, т.е. методы, в которых элементы из массива А передаются в результирующий массив H, представляют существенно меньший интерес. Ограничив критерием экономии памяти наш выбор нужного метода среди многих возможных, мы будем сначала классифицировать методы по их экономичности, т.е. по времени их работы. Хорошей мерой эффективности может быть С - число необходимых сравнений ключей и М - число пересылок (перестановок) элементов.
Эти числа - функции от n - числа сортируемых элементов. Сортировка методом прямого выбора требует порядка n2сравнений ключей.
Рассматриваем весь ряд массива и выбираем элемент меньший или больший элемента а(i), определяем его место в массиве - k, и затем меняем местами элемент а(i) и элемент а(k).
Алгоритм сортировки методом прямого включения:
for i = 2 to n
x = a(i)
a (0) = x { a (0) - барьер}
j = i - 1
while x < a(j) do
a(j + 1 ) = a(j)
j = j - 1
endwhile
a(j + 1 ) = x
next i
return
Для внутреннего цикла, организованного как цикл while, необходима постановка «барьера», без которого при отрицательных значениях ключей происходит потеря значимости и «зависание» компьютера.
Эффективность алгоритма:
Наилучшие оценки числа сравнений Cmin и перемещений Mmin встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки Сmax и Mmax - когда они первоначально расположены в обратном порядке.
Количество сравнений в худшем случае, когда массив отсортированпротивоположным образом, Сmax = n(n -1)/2, то есть порядок О(n 2). Количество перестановок Mmax=Cmax +3(n -1), то есть порядок О (n 2).
Алгоритм сортировки прямым выбором:
for i = 1 to n - 1
x = a(i)
k = i
for j = i + 1 to n
if a(j)<x then
k = j
x = a(k)
endif
next j
a(k) = a(i)
a(i) = x
next i
return
Эффективность алгоритма:
· Количество сравнений в худшем случае, когда массив отсортирован противоположным образом
Сmax = n(n -1)/2,
· Количество перемещений когда массив обратно отсортирован
Mmax =Сmax +3(n-1),
· Количество перемещений, когда массив упорядочен
Mmin=3(n -1), C min=(n -1)
В худшем случае сортировка прямым выбором дает порядок n2, как и для числа сравнений, так и для числа перемещений.
Рассмотрим реализацию функций сортировки прямым включением и выбором на С++
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВКЛЮЧЕНИЕМ */
void Sis(int A[],int nn)
{ int i,j,k;
printf("\n Отладочная печать по шагам сортировки");
for (j=1; j<nn; j++)
{ k = A[j];
i = j -1;
while (k < A[i] && i >= 0)
{ A[i+1] = A[i];
i -= 1; }
A[i+1] = k;
/* Отладочная печать */
printf("\n j = %d",j);
for (i=0; i<nn; i++)
printf("\t%d",A[i]);
}
}
Алгоритм с прямыми включениями можно легко улучшить с учетом того, что готовая последовательность, куда надо вставить новый элемент, уже упорядочена. Тогда место включения ищется методом двоичного (бинарного) поиска. Такой улучшенный алгоритм сортировки называется методом с двоичным включением (методом прямого включения с делением пополам). Однако применение этого алгоритма оправдано только тогда, когда число сортируемых элементов достаточно велико.
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВЫБОРОМ С ДЕЛЕНИЕМ ПОПОЛАМ */
void BinIns(int A[],int nn)
{ int i,j,x,m,L,R;
printf("\n Отладочная печать по шагам сортировки ");
for (i=1; i<nn; i++)
{ x = A[i]; L = 0; R = i;
while (L < R)
{ m = (L+R)/2;
if (A[m] <= x)
L = m+1;
else
R = m;
}
for (j=i; j>=R; j--)
A[j] = A[j-1];
A[R] = x;
/* отладочная печать */
printf("\ni=%d",i);
for (j=0; j<nn;j++)
printf("\t %d",A[j]);
}
}
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВЫБОРОМ */
void StrSel(int A[],int nn)
{ int i,j,x,k;
printf("\n Отладочная печать по шагам сортировки");
for (i=0; i<nn-1; i++)
{ x = A[i]; k = i;
for (j=i+1; j<nn; j++)
if (A[j] < x)
{ k = j; x = A[k]; }
A[k] = A[i]; A[i] = x;
printf("\n i=%d",i);
for (j=0; j<nn;j++)
printf("\t %d",A[j]);
}
}
Задания
Сортировка методом включения
В ремонтной мастерской находятся несколько (N) машин. О них имеются следующие сведения:
- номер,
- марка,
- имя владельца,
- дата последнего ремонта (число, месяц, год),
- день, к которому машина должна быть отремонтирована (число, месяц, год).
Требуется (согласно варианту):
1. Расположить по алфавиту имена владельцев и, соответственно, вывести информацию об их машинах.
2. Исходя из того, что машина, дата окончания ремонта которой раньше, должна ремонтироваться в первую очередь, вывести порядок ремонта автомобилей.
3. Вывести по убыванию количество всех предыдущих ремонтов машин марки "Жигули".
4. Вывести по убыванию номера тех машин, количество предыдущих ремонтов которых равно 2.
5. Вывести по возрастанию даты конца ремонта всех машин, которые ранее не ремонтировались.
6. Вывести по алфавиту в обратном порядке владельцев автомобилей марки "Мерседес"
7. Вывести по алфавиту марки машин, которые должны быть отремонтированы раньше всех (дата конца ремонта меньше 01.08.96).
8. Вывести по возрастанию номера машин марки "Жигули".
9. Вывести по алфавиту имена владельцев, чьи машины не ремонтировались с прошлого года.
10. Вывести машины, которые надо отремонтировать к следующему месяцу по возрастанию даты их последнего ремонта.
11. Вывести по алфавиту в обратном порядке имена владельцев, количество предыдущих ремонтов машин которых больше трех.
12. Вывести по убыванию номера машин марки "Мерседес".