78211

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

Лекция

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

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

Русский

2015-02-07

77 KB

15 чел.

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


 

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

76432. Структурные схемы систем автоматического управления 160.04 KB
  Структурная схема Структурная схема САУ схема САУ это изображение системы регулирования в виде совокупности динамических звеньев с указанием связей между ними. Структурная схема САУ может быть составлена на основе известных уравнений системы и наоборот уравнения системы могут быть получены из структурной схемы. Наименование Обозначение на структурной схеме Звено с одним входом Звено с двумя входами Узел разветвление Наименование Обозначение на структурной схеме Cумматор Элемент сравненияаналог сумматора Простейшие сочетания...
76433. Статические и астатические системы управления 21.21 KB
  В зависимости от принципа и закона функционирования ЗУ задающего программу изменения выходной величины различают основные виды САУ: системы стабилизации программные следящие и самонастраивающиеся системы среди которых можно выделить экстремальные оптимальные и адаптивные системы. обеспечивается неизменное значение управляемой величины при всех видах возмущений...
76434. Критерий управляемости САУ 24.47 KB
  Очевидно что эта система является неуправляемой так как управляющее воздействие влияет не на все переменные состояния переменная состояния не поддается управлению. Пусть описание САУ представлено в терминах пространства состояния САУ будет управляемой тогда и только тогда если матрица управляемости имеет ранг . порядок вектора состояния .
76435. Ответственность за несвоевременную уплату алиментов. Индексация алиментов 14.47 KB
  Индексация алиментов Индексация алиментов предусмотрена с целью защиты алиментных платежей от инфляции и предотвращения необходимости многократного обращения с иском об изменении размера алиментов выплачиваемых в твердой денежной сумме. Индексация возможна только для алиментов взыскиваемых в твердой денежной сумме. Индексация алиментов взыскиваемых по решению суда в твердой денежной сумме производится администрацией организации по месту удержания алиментов пропорционально увеличению установленного законом минимального размера оплаты труда.
76436. Выявление и учет детей, оставшихся без попечения родителей. Банк детей, оставшихся без попечения родителей 16.73 KB
  Банк детей оставшихся без попечения родителей Существуют различные обстоятельства в результате которых дети остаются без родительского попечения. Сведения о детях оставшихся без попечения родителей учитываются в специальном государственном банке данных в соответствии с Федеральным законом...
76437. Органы, осуществляющие защиту прав и интересов детей и способы устройства детей, оставшихся без попечения родителей 14.2 KB
  Защиту прав и интересов таких детей осуществляют специально уполномоченные государством органы опеки и попечительства. Эти органы ведут учет детей оставшихся без попечения родителей; исходя из конкретных обстоятельств утраты попечения родителей избирают формы их устройства; осуществляют последующий контроль за условиями их содержания воспитания и образования ст. Для своевременного выявления таких детей закон возлагает на должностных лиц учреждений которые непосредственно соприкасаются с детьми детских садов школ детских поликлиник и т.
76438. Усыновление. Понятие, значение, порядок усыновления 16.4 KB
  Понятие значение порядок усыновления Усыновление представляет собой правовой институт призванный создать между усыновителем и усыновленным отношения наиболее близкие к тем которые возникают между родителями и родными детьми. Усыновление или удочерение далее усыновление является приоритетной формой устройства детей оставшихся без попечения родителей п. Усыновление допускается в отношении несовершеннолетних детей и только в их интересах с соблюдением требований абзаца третьего пункта 1 статьи 123 СК РФ а также с учетом возможностей...
76439. Дети, подлежащие усыновлению. Лица которые могут быть усыновителями 20.88 KB
  Поэтому при усыновлении ребенка должны учитываться его этническое происхождение; принадлежность к определенной религии и культуре родной язык возможность обеспечения преемственности в воспитании и образовании а также возможность обеспечить усыновляемым детям полноценное физическое психическое духовное и нравственное развитие п. 124 СК закреплено правило согласно которому усыновление братьев и сестер разными лицами не допускается так как при усыновлении прекращаются правоотношения ребенка не только с родителями но и с другими...
76440. Условия усыновления 18.15 KB
  129 СК специально оговорено что при усыновлении ребенка несовершеннолетних родителей которые не достигли возраста шестнадцати лет требуется также согласие их родителей или опекунов попечителей а при отсутствии родителей или опекунов попечителей согласие органа опеки и попечительства. Если законные представители несовершеннолетних родителей не выразили согласия на усыновление ребенка то усыновление не может состояться...