Сортировка выбором. Государственное образовательное учреждение среднего профессионального образования

Государственное образовательное учреждение среднего профессионального образования

ВОРКУТИНСКИЙ ГОРНО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ

РАССМОТРЕНО УТВЕРЖДАЮ:

На заседании цикловой комиссии Зам. директора по УВР

«___»_____________2008 г. ______________З.Г. Штокалюк

Председатель цикловой комиссии «___»___________2008 г.

____________ О.В. Гармаш

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

к лабораторной работе № 14

Тема:

«Методы сортировки данных»

Дисциплина: «Программирование на языке высокого уровня»

для студентов специальности 230101

Разработал преподаватель Баев А.В.

2008 г.

Лабораторная работа №14

Методы сортировки данных

Цель работы:

1. Изучить методы сортировки данных.

2. Получить навыки разработки программ сортировки данных.

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

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

Наиболее простыми алгоритмами сортировки считаются алгоритмы, известные в литературе под названиями - обменная (или пузырьковая) сортировка и сортировка выбором. Эти алгоритмы, в худшем случае, решают задачу сортировки за время пропорциональное N², где N - число сортируемых элементов. Такие алгоритмы называют алгоритмами с квадратичной сложностью. Эти алгоритмы используют, когда число сортируемых элементов относительно не велико (до 1000). Для сортировки данных больших объемов используют более сложные, с точки зрения реализации, алгоритмы. Сложность этих алгоритмов определяется по формулам: N*ln N или N*log₂N. Такие алгоритмы называют алгоритмами с логарифмической сложностью или быстрой сортировки. Эти алгоритмы используют чаще всего при сортировке данных в оперативной памяти, например в массивах или в динамических списках. Для сортировки данных во внешней памяти можно использовать алгоритм сортировки слиянием.

Сортировка выбором

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

Пусть дан одномерный неупорядоченный массив, содержащий целые числа М={m_i}, i=1,n; n - число элементов. Необходимо упорядочить элементы этого массива по возрастанию их значений.

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

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

Схема алгоритма сортировки выбором

Min - минимальный элемент

i_min - адрес минимального элемента