Алгоритмы сортировки массивов.
Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений. Например, массив X из n элементов будет отсортирован в порядке возрастания значений его элементов, если X1 ≤ X2 ≤...≤ Xn, и в порядке убывания, если X1 ≥ X2 ≥ ... ≥ Xn.
Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:
сортировка обменом;
сортировка выбором;
сортировка вставкой.
Представим, что нам необходимо разложить по порядку карты в колоде. Для сортировки карт обменом можно разложить карты на столе лицевой стороной вверх и менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.
Для сортировки выбором из разложенных на столе карт выбирают самую младшую (старшую) карту и держат ее в руках. Затем из оставшихся карт вновь выбрать наименьшую (наибольшую) по значению карту и помещают ее позади той карты, которая была выбрана первой. Этот процесс повторяется до тех пор, пока вся колода не окажется в руках. Поскольку каждый раз выбирается наименьшая (наибольшая) по значению карта из оставшихся на столе карт, по завершению такого процесса карты будут отсортированы по возрастанию (убыванию).
Для сортировки вставкой из колоды берут две карты и располагают их в необходимом порядке по отношению друг к другу. Каждая следующая карта, взятая из колоды, должна быть установлена на соответствующее место по отношению к уже упорядоченным картам.
http://teacher.dn-ua.com/old_version/algoritm/Third/part3.htm
Атд очередь. Операторы очереди.
Абстрактный тип данных (АТД) - это математическая модель плюс различные операторы, определенные в рамках этой модели.
Другой специальный тип списка - очередь (queue), где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют «списками типа FIFO» (аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел - первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Кроме того, различна устоявшаяся терминология для стеков и очередей.
1. NULLQUEUE(Q) очищает очередь Q, делая ее пустой. При реализации очереди на списке Q оператор NULLQUEUE(Q) эквивалентен NULLIST(Q).
2. FRONT(Q) - функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q),Q).
3. ENQUEUE(x,Q) вставляет элемент x в конец очереди Q. С помощью операторов списка этот оператор можно выполнить следующим образом: INSERT(x, NEXT(LAST(Q),Q), Q).
4. DEQUEUE(Q) удаляет первый элемент очереди Q. C помощью операторов списка данный оператор записывается как DELETE(FIRST(Q),Q).
5. EMPTYQUEUE(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью. При реализации очереди на списке Q оператор EMPTYQUEUE(Q) эквивалентен EMPTYLIST(Q).
АТД список. Операторы списка.
Список представляет собой последовательность элементов определенного типа. Список представляется в виде последовательности элементов, разделенных запятыми: a1,a2,...,an, где n0, и все ai имеют некоторый тип elementtype. Количество элементов n называют длиной списка. Если n1, то a1 называется первым элементом, а an - последним элементом списка. В случае n=0 имеем пустой список, который не содержит элементов.
Важное свойство списка заключается в том, что его элементы можно линейно упорядочить в соответствии с их позицией в списке. Говорят, что элемент ai предшествует ai+1 для i=1,2,...,n-1 и ai следует за ai-1 для i = 2,3,...,n. Также говорят, что элемент ai имеет позицию i.
Определим множества операторов списка. При этом будем использовать следующие обозначения: L - список объектов типа elementtype, x - объект типа elementtype, р - позиция элемента в списке. Обычно позиции - это целые положительные числа, но на практике могут встретиться другие представления.
1. INSERT(x,p,L). Этот оператор вставляет объект x в позицию p в списке L, перемещая элементы от позиции p и далее в следующую, более высокую позицию. Таким образом, если список L состоит из элементов a1,a2,...,an, то после выполнения этого оператора он будет иметь вид a1,a2,..., ap-1,x,ap,...,an. Если p принимает значение ENDLIST, равное n+1, то будем иметь a1,a2,...,an,x. Если в списке L нет позиции p, и p не равно ENDLIST, то результат выполнения этого оператора не определен.
2. LOCATE(x,L). Эта функция возвращает позицию объекта x в списке L. Если в списке объект x встречается несколько раз, то возвращается позиция первого от начала списка объекта x. Если объекта x нет в списке L, то возвращается ENDLIST.
3. RETRIEVE(p,L). Эта функция возвращает элемент, который стоит в позиции p в списке L. Результат не определен, если в списке L нет позиции p. Отметим, что элементы должны быть того типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.
4. DELETE(p,L). Этот оператор удаляет элемент в позиции p списка L. Так, если список L состоит из элементов a1,a2,...,an, то после выполнения этого оператора он будет иметь вид a1,a2,...,ap-1,ap+1,...,an. Результат не определен, если в списке L нет позиции p или p=ENDLIST.
5. NEXT(p,L) и PREVIOUS(p,L). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции p в списке L. Если p - последняя позиция в списке L, то NEXT(p,L)= ENDLIST. Функция NEXT не определена, когда p=ENDLIST, или в списке L нет позиции p. Функция PREVIOUS не определена, если р=1, или в списке L нет позиции p.
6. NULLIST(L). Эта функция делает список L пустым и возвращает позицию ENDLIST.
7. FIRST(L), LAST(L). Эти функции возвращают соответственно первую и последнюю позиции в списке L.
8. PRINTLIST(L). Печатает элементы списка L в порядке их расположения.
9. EMPTYLIST(L). Эта функция возвращает значение true (истина), если список L пустой и значение false (ложь) в противном случае.
АТД стек. Операторы стека.
Стек - это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Стеки иногда называют «магазинами», также для обозначения стеков используется аббревиатура LIFO (last-in-first-out - последний вошел - первый вышел). Интуитивными моделями стека могут служить патроны в магазине автоматического стрелкового оружия, книги, сложенные в стопку, или стопка тарелок; во всех этих моделях взять можно только верхний предмет, а добавить новый предмет можно, только положив его на верхний.
Абстрактные типы данных семейства STACK (cтек) обычно используют следующие пять операторов.
1. NULLSTACK(S). Делает стек S пустым. При реализации стека на списке S оператор NULLSTACK(S) эквивалентен NULLIST(S).
2. TOP(S). Возвращает элемент из вершины стека S. Если вершина стека соответствует первой позиции списка S, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIVE(FIRST(S),S). Если вершина стека соответствует последней позиции списка S, тогда TOP(S) можно записать как RETRIVE(LAST(S),S).
3. POP(S). Удаляет элемент из вершины стека (выталкивает из стека). Если вершина стека соответствует первой позиции списка S, тогда этот оператор можно записать как DELETE(FIRST(S),S). Если вершина стека соответствует последней позиции списка S, тогда POP(S) записывается как DELETE(LAST(S),S). Иногда оператор POP(S) реализуется в виде функции, возвращающей удаляемый элемент.
4. PUSH(x,S). Вставляет элемент x в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т.д. Если вершина стека соответствует первой позиции списка S, то данный оператор можно записать как INSERT(x,FIRST(S),S). Если вершина стека соответствует последней позиции списка S, то PUSH(x,S) записывается как INSERT(x, NEXT(LAST(S),S), S).
5. EMPTYSTACK(S). Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае. При реализации стека на списке S оператор EMPTYSTACK(S) эквивалентен EMPTYLIST(S).
Внешняя сортировка. Алгоритм сортировки слиянием.
Внешняя сортировка — сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память, то есть когда применить одну из внутренних сортировок невозможно. Стоит отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к магнитным дискам, лентам и т. п.
Алгоритм прямого слияния – простейший алгоритм внешней сортировки, основанный на процедуре слияния последовательностей, называемых серией и представляющих собой упорядоченные подпоследовательности из записей файлов.
Серия – несколько последовательно расположенных записей файла, упорядоченных по ключам.
Количество записей в серии называется ее длиной.
Последняя серия может иметь длину меньшую, чем остальные серии файлов.
Пример работы алгоритма на массиве 3 7 8 2 4 6 1 5.
