78211

Сортировка и поиск информации. Методы внутренней сортировки

Лекция

Информатика, кибернетика и программирование

Почему так устроена человеческая натура? Оказывается потому, что поиск в упорядоченном массиве значительно эффективнее! Ведь в природе зачастую успешность деятельности зависит от быстроты выбора правильного решения. Поэтому, если у вас в голове все знания упорядочены, вы достигаете больших успехов.

Русский

2015-02-07

77 KB

7 чел.

екция: Сортировка и поиск информации. Методы внутренней сортировки   Страница  5 из 5

Оглавление

[1] Оглавление

[2] Сортировка и поиск информации

[2.1] Методы внутренней сортировки

[2.1.0.1] Сортировки включением

[2.1.0.2] Сортировка прямым включением.

[2.1.0.3] Сортировка бинарными включениями.

[2.1.0.4] Сортировка выбором

[2.1.0.5] Прямой выбор.

[2.1.0.6] Обменные сортировки

[2.1.0.7] Сортировка прямого обмена (пузырьковая).

[2.1.0.8] Шейкерная сортировка.

[2.1.0.9] Пирамидальная сортировка.

[2.1.0.10] Обменная сортировка разделением (быстрая сортировка).

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

Комбинированный урок №13

Тема: Сортировка и поиск информации. Методы внутренней сортировки

Цель: изучить методы внутренней сортировки такие как.

Сортировка и поиск информации

Вся человеческая деятельность связана с поиском и упорядочиванием.

Почему так устроена человеческая натура? Оказывается потому, что поиск в упорядоченном массиве значительно эффективнее! Ведь в природе зачастую успешность деятельности зависит от быстроты выбора правильного решения. Поэтому, если у вас в голове все знания упорядочены, вы достигаете больших успехов.

Используя структурированный тип Record, создаются массивы записей всевозможных баз данных (информация о студентах Вуза, информация о товарах в магазине, информация о машинном парке и др.).

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

Обычно запись содержит некое ключевое слово (ключ), по которому ее находят среди множества других аналогичных записей. В зависимости от решаемой задачи ключом может, например, служить фамилия или учетный номер, или адрес. Основное требование к ключу в задачах поиска и сортировки состоит в том, чтобы операция проверки на равенство была корректной. Поэтому, например, в качестве ключа не следует выбирать действительное число, т.к. из-за всегда возможной ошибки округления, поиск нужного ключа может оказаться безрезультатным, хотя этот ключ в массиве имеется. Для применения более эффективных методов поиска значения ключей должны допускать упорядоченность (т.е. проверку на > или <). Желательно, чтобы в массиве записей не было повторяющихся ключей.

Под сортировкой понимают процесс переупорядочивания некоторого множества объектов с целью их размещения в заданном порядке. Это универсальный вид деятельности с точки зрения обработки данных, которые представляют собой последовательность ключей. С помощью сортировки добиваются такого их размещения, чтобы было выполнено условие: f(a[1])  f(a[2])f(a[3])f(a[N]), где символ означает знак предшествования, а f-некоторая функция упорядочивания. При упорядочивании по возрастанию, после сортировки будет выполнено условие: a[1]a[2]  a[3]  . . . a[N]

В ходе сортировки элементы последовательности меняются местами. Сортировка называется устойчивой, если на этапе замены два одинаковых ключа не меняются местами. Сортировка называется внутренней, если все сортируемые ключи размещаются в оперативной памяти. Если некоторая часть ключей размещается на внешнем носителе, то сортировка называется внешней. Сортировку массивов принято называть внутренней в отличие от сортировки файлов (списков), которую называют внешней. Основное условие при внутренней сортировке массивов – это не вводить дополнительных массивов, т.е. все перестановки элементов должны выполняться «на том же месте» в исходном массиве.

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

Если в таблице имеется запись с ключом, равным х, то поиск называется удачным или результативным. В противном случае поиск называется неудачным (безрезультатным). 

Методы внутренней сортировки

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

Сортировки включением

Сортировка прямым включением. 

Допустим, что массив a[1..n] разбит на две части a1..i-1, ai..n – в первой части элементы упорядочены, во второй – нет. При i=2 такое разбиение получается автоматически, т.к. массив из одного элемента тривиально упорядочен. На каждом шаге i=2..n выполняем элементарный алгоритм: берем очередной элемент r из неупорядоченной части и включаем его в «нужное» место упорядоченной части. Для поиска нужного места в нижеприведенном алгоритме используется барьер a[0]:=x. Элементы, начиная от  i-1 до нужного j сдвигаются на одну позицию: a[j]:=a[j-1]. На каждом проходе происходит перемещение i-того элемента в готовую последовательность, а некоторое число элементов сдвигается вправо. Данный процесс перемещения называется просачиванием элемента.

Во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур - количество элементов массива (n), на выходе - упорядоченный массив элементов (а).

Procedure Straight_Insertion(n:integer; Var a:array[1..100] of integer);

Var i,j:word;

X,r:integer;

Begin

For i:=2 To n Do

begin

x:=a[i];r:=a[i]; a[0]:=x; j:=i;

While x<a[j-1] Do

Begin a[j]:=a[j-1]; j:=j-1; end;

a[j]:=r

end;

End;{Straight_Insertion}{сортировка прямым включением}

Сортировка бинарными включениями. 

Алгоритм сортировки прямыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1],...,a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

Procedure Binary_Insertion(n:word;Var a: array[1..100] of integer);

Var i,j,l,r,m:word;

x:integer;

Begin

For i:=2 To n Do

begin

x:=a[i]; l:=1; r:=i-1;

While l<=r Do

begin

m:=(l+r) div 2;

If x < a[m] Then r:=m-1

Else l:=m+1

end;

For j:=i-1 DownTo l Do a[j+1]:=a[j];

a[l]:=x

end;

End;{Binary_Insertion}{сортировка бинарным вкючением}

Сортировка выбором

Прямой выбор. 

Для i=1..n-1 выполняется следующий элементарный алгоритм: среди элементов ai..n выбираем минимальный am и переставляем местами элементы i-й и m-й. В результате на первое место станет самый минимальный, на второе – следующий минимальный и т.д.

Procedure Straight_Selection(n:word;Var a array[1..100] of integer);

Var i,j,k:word;

x:integer;

Begin

For i:=1 To n-1 Do

begin

m:=i;

For j:=i+1 To n Do

If a[m] > a[j] Then m:=j;

x:=a[i]; a[i]:=a[m]; a[m]:=x

end

End;{Straight_Selection} {сортировка простым выбором}

Обменные сортировки

Сортировка прямого обмена (пузырьковая).

Это метод, в котором обмен двух элементов является основной характеристикой процесса. Алгоритм сортировки простым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы. Для i=1..n-1 выполняется следующий элементарный алгоритм: начиная от n до i последовательно проверяем упорядоченность двух соседних элементов a[j] и a[j-1], и если они не упорядочены, то меняем их местами. В результате такого обмена минимальный элемент перемещается на место i.

Критерием окончания является отсутствие обменов при очередном проходе.

Во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур - количество элементов массива (n), на выходе - упорядоченный массив элементов (а).

Procedure Bubble_Sort(n:word;Var a: array[1..100] of integer);

Var i,j:word;

x:integer;

Begin

For i:=1 To n-1 Do

begin

For j:=n DownTo i Do

If a[j-1]>a[j] Then

begin

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

end

end

End;{Bubble_Sort}

Шейкерная сортировка. 

Улучшение алгоритма - это запоминать, производится ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм может закончить работу. Этот процесс улучшения можно продолжить, если запомнить не только сам факт обмена, но и место (индекс) последнего обмена.

Однако внимательный программист заметит здесь странную асимметрию: один неправильно расположенный "пузырек"  в "тяжелом" конце рассортированного массива всплывет на место за один проход, а неправильно расположенный элемент в "легком" конце будет опускаться на правильное место только на один шаг на каждом проходе. Изменение направления сортировки в каждом из проходов алгоритма поиска называют шейкерной сортировкой.

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

Procedure Shaker_Sort(n:word;Var a:array [1..100] of integer);

Var j,k,l,r:word;

x:integer;

Begin

l:=2; r:=n; k:=n;

Repeat

For j:=r DownTo l Do   {проход снизу-вверх}

If a[j-1]>a[j] Then

begin

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

end;

l:=k+1;

For j:=l To r Do  {проход cверху-вниз}

If a[j-1]>a[j] Then

begin

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

end;

r:=k-1;

Until l>r

End;{Shaker_Sort}

Пирамидальная сортировка.

Предположим, что дана пирамида с элементами hl+1, ..., hr для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду hl, ..., hr. Новый элемент x сначала помещается в вершину дерева, а затем “просеивается” по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом, формируется новая пирамида.

В процедуре Heap_Sort вызывается процедура Sift, которая реализует алгоритм формирования пирамиды.

Procedure Heap_Sort(n:word;Var a: array [1..100] of integer);

Var l,r:word;x:integer;

Procedure Sift;

Label 13;

Var i,j:word;

Begin

i:=l; j:=2*i; x:=a[i];

While j<=r Do

begin

If j<r Then

If a[j]<a[j+1] Then j:=j+1;

If x>=a[j] Then Goto 13;

a[i]:=a[j]; i:=j; j:=2*i;

end;

13: a[i]:=x

End;{Sift}

BEGIN

l:=(n div 2)+1; r:=n;

While l>1 Do

begin

l:=l-1; Sift

end;

While r>1 Do

begin

x:=a[1]; a[1]:=a[r]; a[r]:=x;

r:=r-1; Sift

end

END;{Heap_Sort}

Обменная сортировка разделением (быстрая сортировка). 

Выбирается любой произвольный элемент массива, далее массив просматривается слева направо до тех пор пока не будет найден элемент больший выбранного; а затем просмотрим его справа налево, пока не найдем элемент меньший выбранного. Найденные элементы поменяем местами. Затем продолжим процесс “просмотра с обменом”, пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими выбранного элемента; и правую - с большими ключами. Описанный алгоритм применяется к обоим этим частям, в результате чего последовательность разбивается на 4 части. Алгоритм применяется к каждой четвертинке и т.д. Разделение заканчивается, когда в каждой части остается 1 элемент.

В процедуре Quick_Sort  вызывается процедура Sort, которая реализует алгоритм разделения и обмена для одной части массива.

Procedure Quick_Sort(n:word;Var a:massiv);

Procedure Sort(l,r:word);

Var w,x:integer;

i,j:word;

Begin

i:=l; j:=r;

x:=a[(l+r) div 2];

Repeat

While a[i]<x Do i:=i+1;

While a[j]>x Do j:=j-1;

If i<=j Then

begin

w:=a[i]; a[i]:=a[j]; a[j]:=w;

i:=i+1; j:=j-1

end

Until i>j;

If l<j Then Sort(l,j);

If i<r Then Sort(i,r);

End;{Sort}

BEGIN

Sort(1,n);

END;{Quick_Sort}

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

  1.  Дайте определение понятиям «поиск» и «сортировка».
  2.  Что такое ключ и основные требования к нему?
  3.  Назовите принципы действия сортировки включением. Приведите примеры.
  4.  Назовите принципы действия сортировки выбором.
  5.  Назовите принципы действия обменной сортировки. Приведите примеры.


 

А также другие работы, которые могут Вас заинтересовать

78298. Бронхо-легенева система в умовах спокою, тренувальних впливів, екстремальних, граничних та патологічних станів: бронхо-легенева система в умовах спокою 157.42 KB
  Кількісні показники зовнішнього дихання. Для цього треба застосовувати комплекси фізичних вправ які розвивають дихання. Дихання людини Дихання людини складається з таких процесів: Зовнішнє дихання вентиляція легень надходження повітря в повітроносні шляхи і газообмінміж альвеолами та зовнішнім середовищем. Значення дихання для людини Газообмін між організмом і зовнішнім середовищем надходження О2 до клітин організму а також виведення СО2 з організму.
78300. НОРМИРОВАНИЕ ТОЧНОСТИ УГЛОВЫХ РАЗМЕРОВ 187 KB
  Система единиц на угловые размеры Углом в плоскости называется геометрическая фигура образованная двумя лучами сторонами угла выходящими из одной точки вершины. Полуплоскости называются гранями двугранного угла а их общая прямая ребром. В промышленности чаще всего приходится иметь дело с двугранными углами однако для удобства измерений требования к точности относятся к углу в плоскости т. углу получаемому пересечением двугранного угла плоскостью перпендикулярной ребру.
78301. НОРМИРОВАНИЕ ТОЧНОСТИ МЕТРИЧЕСКОЙ РЕЗЬБЫ 606 KB
  Резьбовые соединения используемые в машиностроении Резьбовым соединением называется соединение двух деталей с помощью резьбы т. элементов деталей имеющих один или несколько равномерно расположенных винтовых выступов резьбы постоянного сечения образованных на боковой поверхности цилиндра или конуса. Контур сечения канавок и выступов в плоскости проходящей через ось резьбы общий для наружной и внутренней резьбы называется профилем резьбы.
78302. НОРМИРОВАНИЕ ТОЧНОСТИ ПРЯМОБОЧНЫХ ШЛИЦЕВЫХ СОЕДИНЕНИЙ 398.5 KB
  Шлицевым соединением или зубчатым соединением называется разъемное соединение вала с отверстием когда на валу имеются зубья выступы а в отверстии соответствующие впадины шлицы. Шлицевое соединение можно представить как многошпоночное соединение с равномерно расположенными шпонками. В зависимости от формы профиля выступов у вала и впадин у втулки имеются прямобочные шлицевые и эвольвентные соединения. Значительно реже применяются шлицевые соединения с треугольным профилем.
78303. НОРМИРОВАНИЕ ТОЧНОСТИ ШПОНОЧНЫХ СОЕДИНЕНИЙ 101 KB
  В шпоночных соединениях имеются вал и отверстие как в гладких соединениях. На валу и во втулке этого соединения имеются пазы расположенные вдоль оси. В машиностроении в основном используют шпоночные соединения с призматическими сегментными и клиновыми шпонками. Помимо перечисленных шпоночных соединений в машиностроении используются и нормируются точности других шпоночных соединений представляющих в определенном роде разновидность перечисленных: соединения с призматическими направляющими шпонками с призматическими высокими...
78304. НОРМИРОВАНИЕ ТОЧНОСТИ ЦИЛИНДРИЧЕСКИХ ЗУБЧАТЫХ КОЛЕС И ПЕРЕДАЧ 811 KB
  Зубчатое колесо представляет собой деталь сложной геометрической формы в виде диска с зубьями на внутренней или наружной цилиндрической или конической поверхности входящими в зацепление с зубьями другого зубчатого колеса. Принцип нормирования точности зубчатых колес и передач Трудность в отношении нормирования точностных требований к зубчатым передачам заключается в том что эти детали сложны по своей геометрической форме а кроме того они являются элементами кинематической...
78305. Сертификация, ее сущность и характеристики 967 KB
  Сущность сертификации Общие положения. Сертификация базируется на стандартах и в ее основе лежат испытания по нормам сертификации. Самосертификация выполняет все необходимые действия и заявляет об этом специальным документом или простановкой знака сертификации на продукции или сопроводительным документом. Любая система сертификации базируется на стандартах государственных предприятий технических условиях.
78306. ОСНОВЫ МЕТРОЛОГИИ И ТЕХНИЧЕСКИХ ИЗМЕРЕНИЙ 341 KB
  В настоящее время к техническим измерениям рассматриваемым во взаимной связи с точностью и взаимозаменяемостью в машиностроении относят измерения линейных угловых и радиусных величин. Основные задачи метрологии ГОСТ 16263 установление единиц физических величин государственных эталонов и образцовых средств измерений контроля и...