Классификация алгоритмов сортировки

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

o Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

o Использование операции сравнения. Алгоритмы, использующие для сортировки сравнения элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет классификация алгоритмов сортировки - student2.ru , но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

§ В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

o Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

§ Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.

§ Объём данных не позволяет им разместиться в ОЗУ.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Сортировка вставками (англ. insertion sort) — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

o прост в реализации;

o эффективен на небольших наборах данных;

o эффективен на наборах данных, которые уже частично отсортированы;

o это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

o может сортировать список по мере его получения.

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

Пример реализации:

const N=255; type array_type=array [1..N] of integer; procedure InsertSort(var x:array_type); var i, j, buf:integer; begin for i:=1 to N do begin buf:=x[i]; j:=i-1; while (j>=0) and (x[j]>buf) do begin x[j+1]:=x[j]; j:=j-1; end; x[j+1]:=buf; end; end;

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Алгоритм имеет преимущества, если нужно отсортировать много чисел из небольшого диапазона, например, миллион натуральных чисел меньших 1000.

Предположим, что входной массив состоит из n целых чисел в диапазоне от 0 до k − 1. Далее алгоритм будет обобщён для произвольного целочисленного диапазона.

Простой алгоритм

Это простейший вариант алгоритма. Создать вспомогательный массив C[0..k], состоящий из нулей, затем последовательно прочитать элементы входного массива A, для каждого A[i] увеличить C[A[i]] на единицу. Теперь достаточно пройти по массиву C, для каждого в массив A последовательно записать число j C[j] раз.

Пример реализации 1:

{На примере массива из 10 эл-тов. Для модифицированного алгоритма}for i := 1 to 10 do beginc := 0; {кол-во одинаковых эл-тов}p := 0; {позиция эл-та}for j := 1 to 10 do beginif a[i] > a[j] then begininc(p);end; {элемент всегда равен сам себе. Этот вариант исключаем}if (a[i] = a[j]) and (i <> j) then begininc(c);end; end; {для цикла по j}{Записываем кол-во одинаковых эл-тов}if c > 0 then beginfor p + 1 to (p + 1) + c dob[p] := a[i];end; b[p + 1] := a[i];end; {для i}

Пример реализации 2:

for i := 1 to n do begin c[a[i]] := c[a[i]] + 1;end;{Сортировка}p := 1;for i := 1 to n do begin for j := 1 to c[i] do begin a[p] := i; inc(p); end;end;

СОДЕРЖАНИЕ РАБОТЫ: Используя записи, написать программу:

Вариант	Задание
№1, 11	Используя записи, написать программу, которая заполняет анкеты студентов. Анкета включает в себя ФИО, возраст, пол, номер группы и оценки по четырем предметам. Программа выводит ФИО студента, который имеет максимальный балл по четырем предметам.
№2, 12	Используя записи, написать программу, которая заполняет анкеты студентов. Анкета включает в себя ФИО, возраст, пол, номер группы и оценки по четырем предметам. Программа выводит ФИО студентов женского пола.
№3, 13	Используя записи, написать программу, которая заполняет анкеты студентов. Анкета включает в себя ФИО, возраст, пол, номер группы и оценки по четырем предметам. Программа выводит ФИО студентов мужского пола.
№4, 14	Используя записи, написать программу, которая заполняет анкеты студентов. Анкета включает в себя ФИО, возраст, пол, номер группы и оценки по четырем предметам. Программа выводит средний балл студентов женского пола.
№5, 15	Используя записи, написать программу, которая заполняет анкеты студентов. Анкета включает в себя ФИО, возраст, пол, номер группы и оценки по четырем предметам. Программа выводит средний балл студентов мужского пола.
№6, 16	Используя записи, написать программу, которая заполняет анкеты студентов. Анкета включает в себя ФИО, возраст, пол, номер группы и оценки по четырем предметам. Программа выводит средний возраст студентов женского пола.
№7, 17	Используя записи, написать программу, которая заполняет анкеты студентов. Анкета включает в себя ФИО, возраст, пол, номер группы и оценки по четырем предметам. Программа выводит ФИО самого молодого студента.
№8, 18	Используя записи, написать программу, которая заполняет анкеты студентов. Анкета включает в себя ФИО, возраст, пол, номер группы и оценки по четырем предметам. Программа выводит средний возраст студентов мужского пола.
№9, 19	Формирует расписание полетов самолетов. Расписание включает в себя номер поезда, пункт назначения, время вылета, тип самолета. Программа выводит пункт назначения, время вылета, тип самолета на вводимый с клавиатуры номер рейса.
№10, 20	Формирует расписание полетов самолетов. Расписание включает в себя номер самолета, пункт назначения, время вылета, тип самолета. Программа выводит номера рейсов, время вылета, типы самолетов всех рейсов на вводимый с клавиатуры пункт назначения.