78211

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

Лекция

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

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

Русский

2015-02-07

77 KB

16 чел.

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


 

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

23207. Діалектика та метафізика як філософські методи 38.5 KB
  Діалектика метод філософського дослідження при якому речі явища розглядаються гнучко критично послідовно з врахуванням їх внутрішніх протиріч змін розвитку причин і наслідків єдності і боротьби протилежностей. Метафізика метод протилежний діалекціку при якому об'єкти розглядаються: відособлено як самі по собі а не з точки зору їх взаємозв'язаної ; статично ігнорується факт постійних змінсамору хурозвитку; однозначно ведеться пошук абсолютної істини не приділяється уваги протиріччямне усвідомлюється їх єдність....
23208. Основні функції філософії 37.5 KB
  Основні функції філософії: У межах цілісної структури філософії основні функції філософії взаємопов'язані і взаємно детермінують одна одну. Розглянемо спочатку взаємний зв 'язок світоглядної і онтологічної функцій філософії. Але ще в античній філософії були розроблені різні варіанти онтології. Суттєвою функцією філософії є пізнавальна.
23209. Основні рівні буття 38.5 KB
  Основні рівні буття. Буття належить до числа тих системотворчих понять які покладені в основи філософії багатьма мислителями як минулого так і сучасного. Перший аспект проблеми буття: а Що існує Світ. Суть проблеми полягає в існуванні суперечливої єдності неминучого вічного і минулого змінного буття окремих речей ста нів людських та інших істот.
23210. Особливості розвитку та функціонування системи філософських категорії 47.5 KB
  Філософські категорії це найзагальнішігранично широкі поняття що виражають універсальні характеристики та відношення матеріального й духовного світу в які і через які здійснюється філософське мислення і які служать вихідними принципами пізнання і духовнопрактичного перетворення світу. У процесі пізнання категорії виконують вимоги логіки. Категорії матерія форма причина і ціль які ним були теж сформульовані чомусь не увійшли до цієї системи.
23213. Специфіка філософської думки в період Середньовіччя 48.5 KB
  До них належать: Афанасій Олександрійський Василь Великий Григорій Нісський Григорій Назіанзін Амвросій Медіоланський Августин Блаженний Іоанн Дамаскін та ін.Одним із найбільш яскравих представників патрістики був єпископ із ГіппонаПівнічна Африка Августин якого католицькі богослови нарекли ще й ім'ям Блаженний. Августин вважав що філософія поза богослов'ям ніщо. Воюючи з язичеством як він називав античну філософію Августин намагався розгорнути християнську теологічну систему на основі неоплатонізму.
23214. Особливості філософії епохи Відродження 33 KB
  Особливості філософії епохи Відродження Філософія Відродження охоплює період відXIV до початкуXVII ст. Відродженняперехідна епоха і цим значною мірою пояснюється чимало її специфічних рис і насамперед та завдяки якій майже синонімічною назвою для епохи стає словогуманізм. Для епохи Відродження характерним було швидке зростання кількості людей розумової праці. Звичайно мислителі Відродження були далекі від думки ігнорувати Святе письмо віру в Бога але якщо у схоластів центром уваги був Бог то у гуманістів епохи Відродження Бог і...