Список алгоритмов сортировки. Алгоритмы устойчивой сортировки

Индивидуальные задания для лабораторных работ

1 курс 1-ый семестр

Задание 6. КСР. Методы сортировки

Составить программу реализации указанного метода сортировки и иллюстрации его выполнения. В программе предусмотреть просмотр входных и выходных данных и пошаговое перемещение элементов в соответствии с алгоритмом.

Для получения входных данных иметь три варианта:

a) непосредственный ввод и запись в текстовый файл;

b) генерирование с помощью датчика случайных чисел и запись в текстовый файл;

c) ввод из текстового файла.

Алгоритм сортировки реализовать в виде процедуры с параметрами, которую поместить в отдельный файл.

Описание методов сортировки можно посмотреть в книгах:

Лэнггсам Й., ОгенстайнМ., Тененбаум А. Структуры данных для персональных ЭВМ, М., Мир, 1989г., 567 стр.
Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4
Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4

Список алгоритмов сортировки

В этой таблице n — это количество записей, которые необходимо упорядочить, а k — это количество уникальных ключей.

Алгоритмы устойчивой сортировки

· Сортировка вставками (метод простых ставок)(Insertion sort) — Сложность алгоритма: O(n²); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда Киселев В. С.

сортировка вставками(метод простых вставок)

сортировка вставками(метод двухпутевых вставок)