Использование алгоритмов сортировки

Цель работы: ознакомится с различными методами сортировки данных, освоить способы программирования алгоритмов сортировки.

 

Краткие теоретические сведения

Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве. В этом смысле сортировка присутствует почти во всех задачах обработки информации. С сортировкой связаны многие фундаментальные приемы построения алгоритмов, которые и будут нас интересовать в первую очередь. В частности, сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу, многие из которых в некотором смысле оптимальные, а большинство имеет какие-либо преимущества по сравнению с остальными. Поэтому на примере сортировки мы убеждаемся в необходимости сравнительного анализа алгоритмов. Зависимость выбора алгоритмов от структуры данных - явление довольно частое, а в случае сортировки она настолько сильна, что методы сортировки обычно разделяются на две категории:

· сортировка массивов (внутренняя сортировка)

·  сортировка файлов (внешняя сортировка).

 

ПОСТАНОВКА ЗАДАЧИ

ДАНО           

ТРЕБУЕТСЯ

СВЯЗЬ         

и последовательность является перестановкой исходной последовательности.

Основное требование к методам внутренней сортировки - экономное использование   памяти. Это означает, что переупорядочивание элементов надо выполнять на том же месте.

Методы внутренней сортировки можно разбить на четыре основных класса в зависимости от лежащего в их основе приема:

· сортировка включением(вставкой),

· сортировка выбором,

· сортировка обменом,

· разделением.

 

СОРТИРОВКА ВКЛЮЧЕНИЕМ. Этот метод состоит в том, что на каждом шаге берут i-ый элемент последовательности и передают его в готовую отсортированную часть последовательность, вставляя его на свое место. Алгоритм сортировки включениями выглядит следующим образом:

 

FOR I:= 2 TO N DO

BEGIN X:= a[I];

  < вставить X на подходящее место в a[1], a[2],...,a[I] >

END

СОРТИРОВКА ВЫБОРОМ. Этот метод основан на следующем правиле. Выбирается минимальный (максимальный) элемент последовательности и обменивается с первым элементом (элементом) последовательности. Очевидно, один элемент при этом встанет на свое место в отсортированной части последовательности. Далее все выше изложенное надо повторить в не отсортированной части последовательности и т.д.

 

FOR I = 1 TO N-1 DO

 BEGIN

 < присвоить K индекс наименьшего элемента из a[I]...a[N] >

 < поменять местами a[I] и a[K] >

 END

СОРТИРОВКА ОБМЕНОМ. Алгоритм обмена основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы. В качестве примера рассмотрим сортировку методом пузырька.

 

FOR I:= 2 TO N DO

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

 

СОРТИРОВКА РАЗДЕЛЕНИЕМ.  Алгоритм разделением основан на разбиении последовательности на две подпоследовательности по некоторому правилу. При этом каждая из них может не являться упорядоченной, но последовательное применение указанного правила приводит к упорядоченности последовательности. Примером этого класса алгоритмов является алгоритм быстрой сортировки.

Procedure quicksort (S);

begin

if < S содержит один элемент> then <возвратить S >

else begin <выбрать произвольный элемент a из S >;

<пусть S _1, S ₂ и S ₃ - последовательности элементов из S, соответственно меньших, равных и больших a >;

< возвратить quicksort(S₁), затем S_2,, затем quicksort(S₃) >

end

end

 

Внешняя сортировка, т.е. сортировка данных, находящихся на внешних запоминающих устройствах, имеет свои особенности.

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

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

 Рассмотрим один из алгоритмов внешней сортировки.

 

СОРТИРОВКА СЛИЯНИЕМ. Главная идея, которая лежит в основе этой сортировки это представлении файла в виде постепенно увеличивающихся серий, т.е. упорядоченных подпоследовательностей. Если есть, по крайней мере, два файла и число серий в них равно или отличается на единицу, то последовательным слиянием отсортированных серий в новый файл можно уменьшить количество серий, по крайней мере, в два раза.

Отчет о выполнении

 

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

Текст задачи

Листинг алгоритма исполняемого файла

Скриншот интерфейса запускного файла программы

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

1. Что такое одномерный массив?

2. Что такое двухмерный массив?

3. Что такое сортировка массива?

4. Какие методы сортировки вы знаете?

Варианты индивидуальных заданий

Вариант 1 Задать два массива по 6 целых чисел. Отсортировать оба массива: первый – по возрастанию методом пузырька, второй – по убыванию методом выбора. Выводить на экран каждый шаг сортировки.	Вариант 2 Задать два массива по 8 вещественных чисел. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.	Вариант 3 Задать два массива по 7 символов. Отсортировать оба массива: первый – по возрастанию методом выбора, второй – по убыванию методом пузырька. Выводить на экран каждый шаг сортировки.
Вариант 4 Задать два массива по 5 целых чисел. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – методом выбора на возрастание. Выводить на экран каждый шаг сортировки.	Вариант 5 Задать два массива по 9 вещественных чисел. Отсортировать оба массива: первый – по возрастанию методом выбора, второй – по убыванию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 6 Задать два массива по 4 символа. Отсортировать оба массива: первый – по убыванию методом выбора, второй – по возрастанию методом пузырька. Выводить на экран каждый шаг сортировки.
Вариант 7 Задать два массива по 9 целых чисел. Отсортировать оба массива: первый – по возрастанию методом выбора, второй – по убыванию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 8 Задать два массива по 6 вещественных чисел. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.	Вариант 9 Задать два массива по 5 символов. Отсортировать оба массива: первый – по возрастанию методом выбора, второй – по убыванию методом пузырька. Выводить на экран каждый шаг сортировки.
Вариант 10 Задать два массива по 7 целых чисел. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.	Вариант 11 Задать два массива по 10 вещественных чисел. Отсортировать оба массива: первый – по возрастанию методом выбора, второй – по убыванию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 12 Задать два массива по 8 символов. Отсортировать оба массива: первый – по возрастанию методом пузырька, второй – по убыванию методом выбора. Выводить на экран каждый шаг сортировки.
Вариант 13 Задать два массива по 5 целых чисел. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.	Вариант 14 Задать два массива по 9 вещественных чисел. Отсортировать оба массива: первый – по убыванию методом выбора, второй – по возрастанию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 15 Задать два массива по 4 символа. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.

Вариант 16 Задать два массива по 10 целых чисел. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.	Вариант 17 Задать два массива по 7 вещественных чисел. Отсортировать оба массива: первый – по возрастанию методом выбора, второй – по убыванию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 18 Задать два массива по 6 символов. Отсортировать оба массива: первый – по возрастанию методом пузырька, второй – по убыванию методом выбора. Выводить на экран каждый шаг сортировки.
Вариант 19 Задать два массива по 4 целых числа. Отсортировать оба массива: первый – по убыванию методом выбора, второй – по возрастанию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 20 Задать два массива по 9 вещественных чисел. Отсортировать оба массива: первый – по возрастанию методом пузырька, второй – по убыванию методом выбора. Выводить на экран каждый шаг сортировки.	Вариант 21 Задать два массива по 5 символов. Отсортировать оба массива: первый – по возрастанию методом пузырька, второй – по убыванию методом выбора. Выводить на экран каждый шаг сортировки.
Вариант 22 Задать два массива по 9 целых чисел. Отсортировать оба массива: первый – по возрастанию методом выбора, второй – по убыванию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 23 Задать два массива по 11 вещественных чисел. Отсортировать оба массива: первый – по возрастанию методом выбора второй – по убыванию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 24 Задать два массива по 8 символов. Отсортировать оба массива: первый – по убыванию методом выбора, второй – по возрастанию методом пузырька. Выводить на экран каждый шаг сортировки.
Вариант 25 Задать два массива по 7 целых чисел. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.	Вариант 26 Задать два массива по 9 вещественных чисел. Отсортировать оба массива: первый – по убыванию методом выбора, второй – по возрастанию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 27 Задать два массива по 5 символов. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.
Вариант 28 Задать два массива по 11 целых чисел. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.	Вариант 29 Задать два массива по 10 вещественных чисел. Отсортировать оба массива: первый – по убыванию методом выбора, второй – по возрастанию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 30 Задать два массива по 6 символов. Отсортировать оба массива: первый – по убыванию методом пузырька, второй – по возрастанию методом выбора. Выводить на экран каждый шаг сортировки.
Вариант 31 Задать два массива по 8 целых чисел. Отсортировать оба массива: первый – по убыванию методом выбора, второй – по возрастанию методом пузырька. Выводить на экран каждый шаг сортировки.	Вариант 32 Задать два массива по 7 вещественных чисел. Отсортировать оба массива: первый – по возрастанию методом пузырька, второй – по убыванию методом выбора. Выводить на экран каждый шаг сортировки	Вариант 33 Задать два массива по 9 символов. Отсортировать оба массива: первый – по возрастанию методом пузырька, второй – по убыванию методом выбора. Выводить на экран каждый шаг сортировки.