Вопрос 26.doc
Оценка 4.9

Вопрос 26.doc

Оценка 4.9
doc
13.05.2020
Вопрос 26.doc
Вопрос 26.doc

Вопрос 26.

8.  Сортировка.

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

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

Задача сортировки состоит в перестановке членов последовательности таким образом, чтобы выполнялось условие для всех i от 0 до n.

K

X

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

 

Если значение функции сравнения зависит от поля K, то такое поле называется ключом, по которому производится сортировка. На практике в качестве ключевого поля  К  выступает число, а поле в котором хранится значение не влияет на работу алгоритма.

Дадим общую формулу сортировки:

Необходимо упорядочить n элементов R1, R2, R3, … , Rn. Назовем их записями, а всю совокупность этих элементов файлом. Каждая запись  Rj имеет свой ключ kj , который управляет процессом сортировки. Отношение порядка “<” на множестве ключей вводятся таким образом, что для любых трёх значений  a, b, c  выполняются следующие условия:

1)    Справедливо одно и только одно из соотношений   ,    или 

2)    Если     и      ,   то 

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

Сортировка называется устойчивой, если она удовлетворяет дополнительному условию: записи с одинаковыми ключами должны находиться в прежнем порядке.

Параметры, по которым будет производиться оценка алгоритма.

1)    Время сортировки.

2)    Память. Ряд алгоритмов требует выделение памяти под временное хранение данных. При оценке используемой памяти не учитывается место, которое занимает исходный массив.

3)    Устойчивость. Устойчивая сортировка не изменяет взаимного расположения равных элементов.

4)    Естественность поведения. Эффективность метода при обработке отсортированных или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности.

5)    Оценка времени исполнения O( ).

Для оценки производительности алгоритмов можно использовать простой способ. Запустить каждый алгоритм на нескольких задачах и сравнить время исполнения.

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

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

9. Характеристики внутренних методов сортировки:

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

 

1.Линейные и нелинейные. Сложность метода определяющего последовательность сравнений зависит от того, как много информации о структуре используется в организации записи. Линейный алгоритм предполагает отсутствие структуры в списке. Список рассматривается, как линейная последовательность элементов. Сравниваемые элементы выбираются последовательно сверху или снизу списка один за другим. Нелинейные методы наоборот предполагают наличие структуры у списков, которые они сортируют. Они наиболее эффективны. Когда списки рассматриваются как двоичные деревья или строятся иным способом и выбирает последовательность более сложным способом. Все «эффективные» сортировки, т. е. сортировки, в ко­торых достигается теоретически минимальное число сравнений, являются нелинейными. 

2.Простые или комбинированные сортировки.

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

3.Сравнительные или распределительные.

В сравнительном методе данные упорядочиваются по относительной величине  в списке. Большинство методов сортировки являются сравнительными.

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

4.Минимальный или не минимальный по памяти.

В минимальном по памяти методе память требуется только для программы и упорядоченного списка. Не минимальный по памяти метод, помимо этого требует память для  копии исходного списка.

В соответствие с приведенными выше характеристиками приводится классификация методов сортировки на основе её временной характеристики О( ).

Все методы разделяются на простые  и усовершенствованные.

Простые О(n2) :Сортировка подсчетом, Сортировка выбора, Обменная сортировка, Сортировка вставками

Усовершенствованные сортировки, где О() : Сортировка Шелла, Сортировка Хоара, Квадратичная сортировка, Сортировка слиянием, Сортировка древесная (турнирная), Сортировка   Флойда

 

13. Сортировка вставками.

Сортировка вставками есть общее название группы методов сортировки, основанных на последовательной вставке «новых» элементов в увеличиваю­щийся упорядочиваемый список. Среди них есть три существенно разных ме­тода: линейная вставка, центрированная вставка и двоичная вставка. Эти методы сортировки различаются методами поиска подходящего места для вставки элемента. Простейшим методом является линейная вставка. Как сле­дует из названия, в этом методе уже существующий список рассматривается как простой линейный список, просматриваемый поэлементно сверху вниз, пока не будет найдена соответствующая позиция для нового элемента.

Сортировка выполняется каждый раз при получении нового элемен­та, размещая этот элемент в нужную позицию списка.

Линейная вставка не минимальная по объему памяти.

Под сортировку выделяется количество памяти, равное предполагаемой длине окончательного списка из всех элемен­тов. Счетчик длины списка в самом начале устанавливается равным нулю. При помощи этого счетчика контролируется длина области поиска нужной позиции для элемента, вставляемого в список. Сортировка привлекается для каждого элемента. Один «вызов» сортирующей подпрограммы размещает один элемент в списке и увеличивает счетчик списка на единицу.

 

Первый элемент помещается в верхнюю позицию области вывода. Сле­дующий элемент, присоединяемый к списку, сравнивается с первым. Если ключ нового элемента больше, он помещается в позицию, следующую за по­зицией первого элемента. Если ключ нового элемента меньше, то первый эле­мент перемещается в позицию 2, а новый элемент помешается в позицию 1.

В дальнейшем все новые элементы последовательно сравниваются с каж­дым элементом списка, начиная с первого, до тех пор, пока не встретится больший.   Этот   больший   элемент   и   все   последующие   элементы   списка передвигаются на одну позицию вниз. Таким образом освобождается место, на которое вставляется новый элемент.

Исх.

1-й

2-й

3-й

4-й

10-й

11-й

3

В:3ß

B: 3

B: 3

B: 3

 

B :2ß

B:1ß

11

0

11 ß

6 ß

4 ß

 

3 *

2 *

6

0

0

11 *

6 *

 

4 *

3 *

4

0

0

0

11*

 

5*

4*

9

0

0

0

0

 

6*

5*

5

0

0

0

0

 

7*

6*

7

0

0

0

0

 

8*

7*

8

0

0

0

0

 

9*

8*

10

0

0

0

0

 

10*

9*

2

0

0

0

0

 

11*

10*

1

0

0

0

0

 

0

11*

 

Dl=0

New=3

Dl=1

New=11

Dl=2

New=6

Dl=3

New=4

 

Dl=9

New=2

Dl=10

New=1

 Число сравнений для данной сортировки примерно равно . Если все элементы поступают в обратном порядке, то потребуется n-1 сравнений. Среднее число сравнений равно .

Число перемещений минимальное, когда список упорядочен. Максимальное число перемещений, когда список имеет обратный порядок ,  если список упорядочен ,то .

dl=длина, new=новый, ß- вставка, *- сдвиг.

 

Алгоритм сортировки вставками Теория метода:

Массив разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются вставляются в отсортированную часть так, чтобы не нарушить в ней упоря­доченность элементов. В начале работы алгоритма в качестве отсортирован­ной части массива принимают только один первый элемент, а в качестве не­отсортированной части — все остальные элементы.

Таким образом, алгоритм будет состоять из п-1 -го прохода ( п — раз­мерность массива), каждый из которых будет включать следующие действия:

·         взятие очередного неотсортированного элемента и сохранение его в дополнительной переменной;

·        поиск позиции в отсортированной части массива, в которой присутст­вие взятого элемента не нарушит упорядоченности элементов;

·        вставка взятого элемента в найденную позицию.

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

На первом этапе выбирается второй элемент и сравнивается с первым. Поскольку первый элемент больше рассматриваемого, то на его место ставится второй (рассматриваемый) элемент, а сам первый элемент перемеща­ется на одну позицию вправо (т. е. на место второго). Остальная часть по­следовательности остается без изменения. На втором этапе выбирается тре­тий элемент (80) и сравнивается с двумя упорядоченными ранее. Так как он больше этих элементов, то остается на месте. Затем из неупорядоченной по­следовательности выбирается четвертый элемент (15). Так как он меньше второго элемента упорядоченной последовательности (38), то перемещается на второе место, при этом второй и третий элементы смещаются на одну позицию вправо. Подобным образом последовательность меняется до тех пор, пока не станет упорядоченной (в нашем случае это достигается на седьмом этапе).

Размещение элемента массива на соответствующем ему месте в пред­шествующей, уже упорядоченной последовательности может быть проведено двумя способами:

·       последовательно сравнивать рассматриваемый элемент с элемен­том, расположенным слева от него, и обменивать их местами до тех пор, пока слева от перемещаемого элемента не окажется эле­мент, меньший его (m[j]<b) и пока не достигнут левый конец упорядоченной части массива. Такой способ называют «сравне­ние и обмен».

·       сначала определить место, соответствующее рассматриваемому элементу в упорядоченной последовательности, затем сдвинуть элементы массива вправо, чтобы освободить найденную позицию вставки и далее вставить рассматриваемый элемент. Эту разно­видность размещения называют «поиск места и вставка»


Вопрос 26. 8. Сортировка

Вопрос 26. 8. Сортировка

Естественность поведения. Эффективность метода при обработке отсортированных или частично отсортированных данных

Естественность поведения. Эффективность метода при обработке отсортированных или частично отсортированных данных

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

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

Если ключ нового элемента меньше, то первый эле­мент перемещается в позицию 2, а новый элемент помешается в позицию 1

Если ключ нового элемента меньше, то первый эле­мент перемещается в позицию 2, а новый элемент помешается в позицию 1

Методику сортировки иллюстрирует схема, где (для каждого этапа) жирным выделена отсортированная часть массива, подчеркива­нием анализируемый элемент, стрелкой снизу отмечено место, на ко­торое перемещается (при необходимости)…

Методику сортировки иллюстрирует схема, где (для каждого этапа) жирным выделена отсортированная часть массива, подчеркива­нием анализируемый элемент, стрелкой снизу отмечено место, на ко­торое перемещается (при необходимости)…
Скачать файл