78211

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

Лекция

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

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

Русский

2015-02-07

77 KB

18 чел.

екция: Сортировка и поиск информации. Методы внутренней сортировки   Страница  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.  Назовите принципы действия обменной сортировки. Приведите примеры.


 

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

10684. Кавказ - Шевченко Тарас - КАВКАЗ (Поема) 15.16 KB
  Кавказ Шевченко Тарас КАВКАЗ Поема Кавказькі гори засіяні горем кровію политі тривалий час там іде війна. Споконвіку там орел символ російського самодержавства карає Прометея символ нескореного народу та не в змозі остаточно здолати непокірного титана: Не в
10685. Іван Підкова - Шевченко Тарас - ІВАН ПІДКОВА (Поема) 13.53 KB
  Іван Підкова Шевченко Тарас ІВАН ПІДКОВА Поема 1 Поет оспівує козацькі часи в Україні. Запорожці вміли воювати добувати славу і волю. Від тієї слави лишилися тільки високі могили що про волю нишком в полі з вітрами говорять. Та згадка про ті славні часи може заспо
10686. Наталка Полтавка - Котляревський Іван 15.15 KB
  Наталка Полтавка Котляревський Іван Українська опера на дві дії Дійові особи: Наталка українська дівчина. Горпина Терпилиха її мати. Петро коханий Наталки. Микола далекий родич Терпилихи. Тетерваковський возний жених Наталчин. Макогоненко сільський вибо
10687. Маруся - Квітка-Основяненко 16.75 KB
  Маруся Квітка-Основяненко Наум Дрот та його дружина були людьми богобоязними та праведними. В усьому вони дотримуються Божого і морального людського закону. За це Бог допомагає їм. За молитви й невпинну працю дає їм Бог донечку. Дитина теж росте слухняна покірна на ву
10688. Чорна рада - Пантелеймон Куліш - Хроніка 1663 року 20.2 KB
  Чорна рада Пантелеймон Куліш Хроніка 1663 року І Навесні двоє верхових наближалися до Києва Білгородським шляхом. Де їхали полковник Шрам із сином. Полковник був сином поволоцького попа вивчився на попа але потім пішов до козаків. Після поразки повстання полковник дес...
10689. Вовчок Марко - Максим Гримач 14.49 KB
  Вовчок Марко Максим Гримач Давно це було коли панували в Україні Польща і Московщина. Застави між державами хоч і стояли та не густо спритні люди часто перевозили Дніпром усякий крам не сплачуючи мита. Навпроти Черкас над Дніпром стояв хутір Максима Гримача. Чолові
10690. Кайдашева сімя - Нечуй-Левицький Іван 17.95 KB
  Кайдашева сімя НечуйЛевицький Іван І Село Семигори знаходиться недалеко коло Росі ховається воно в зелених садах навколо розстилаються левади. Хата Омелька Кайдаша притулилася біля однієї гори в старому садку. Старий Кайдаш сидить коло повітки та майструє одягнен...
10691. Хіба ревуть воли, як ясла повні? - Мирний Панас - Роман з народного життя 25.69 KB
  Хіба ревуть воли як ясла повні Мирний Панас Роман з народного життя ЧАСТИНА ПЕРША І Польова царівна Надворі вповні розвинулася весна вся природа буяє. В такий прекрасний весняний день дорогою від села Пісок до Ромодана йшов молодий чоловік. Він із задоволенням розг
10692. Мартин Боруля - Карпенко-Карий Іван 17.35 KB
  Мартин Боруля КарпенкоКарий Іван Мартин Боруля багатий шляхтич чиншовик той хто платить за оренду землі якомусь іншому власникові просить повіреного Трандалєва прочитати документ де вказано що Дворянскоє депутатскоє собраніє зачисляє його Борулю до дворянс