Текст программы сортировки выбором
Федеральное агентство по образованию
Государственное образовательное учреждение среднего профессионального образования
ВОРКУТИНСКИЙ ГОРНО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ
РАССМОТРЕНО УТВЕРЖДАЮ:
На заседании цикловой комиссии Зам. директора по УВР
«___»_____________2008 г. ______________З.Г. Штокалюк
Председатель цикловой комиссии «___»___________2008 г.
____________ О.В. Гармаш
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к лабораторной работе № 14
Тема:
«Методы сортировки данных»
Дисциплина: «Программирование на языке высокого уровня»
для студентов специальности 230101
Разработал преподаватель Баев А.В.
2008 г.
Лабораторная работа №14
Методы сортировки данных
Цель работы:
1. Изучить методы сортировки данных.
2. Получить навыки разработки программ сортировки данных.
Краткие сведения из теории
Сортировка данных при решении задач на ЭВМ занимает значительную часть времени. В настоящее время разработано большое число алгоритмов сортировки (упорядочения), отличающихся друг от друга различными признаками: сложностью алгоритма, временем решения, затратами памяти ЭВМ, числом сортируемых элементов, до какой степени элементы уже отсортированы, где располагаются сортируемые данные: во внешней памяти (например, на диске) или в оперативной памяти. Очевидно, что с отсортированными данными работать легче, чем с произвольно расположенными данными. Когда элементы отсортированы, их проще найти или определить, что их нет среди данных.
|
|
|
Наиболее простыми алгоритмами сортировки считаются алгоритмы, известные в литературе под названиями - обменная (или пузырьковая) сортировка и сортировка выбором. Эти алгоритмы, в худшем случае, решают задачу сортировки за время пропорциональное N2, где N - число сортируемых элементов. Такие алгоритмы называют алгоритмами с квадратичной сложностью. Эти алгоритмы используют, когда число сортируемых элементов относительно не велико (до 1000). Для сортировки данных больших объемов используют более сложные, с точки зрения реализации, алгоритмы. Сложность этих алгоритмов определяется по формулам: N*ln N или N*log2N. Такие алгоритмы называют алгоритмами с логарифмической сложностью или быстрой сортировки. Эти алгоритмы используют чаще всего при сортировке данных в оперативной памяти, например в массивах или в динамических списках. Для сортировки данных во внешней памяти можно использовать алгоритм сортировки слиянием.
|
|
|
Сортировка выбором
В литературе описано несколько различных модификаций сортировки выбором, но суть их всех заключается в том, что на очередном шаге выбирается необходимый элемент, и он помещается на заданное место в сортируемой последовательности. Рассмотрим одну их модификаций сортировки выбором.
Пусть дан одномерный неупорядоченный массив, содержащий целые числа М={mi}, i=1,n; n - число элементов. Необходимо упорядочить элементы этого массива по возрастанию их значений.
На первом шаге из элементов массива выбирается минимальный, и он меняется местами с элементом, стоящем на первом месте. На втором шаге из оставшихся неупорядоченных элементов, начиная со второго, выбирается следующий минимальный элемент, и он меняется местами с элементом, стоящем на втором месте. Процесс повторяется до тех пор, пока не будут переставлены все элементы. Последний элемент можно не проверять, так как к этому времени все элементы уже будут стоять на своих местах.
В том случае, если требуется упорядочить элементы по убыванию их значений, осуществляется поиск и обмен максимального элемента.Рассмотрим работу алгоритма по схеме.
|
|
|
Схема алгоритма сортировки выбором 
Min - минимальный элемент
i_min - адрес минимального элемента
Текст программы сортировки выбором
Uses crt;
Var
M:array[1..1000] of integer;
n, i, j, Min, i_min:integer;
Begin
Clrscr;
Write(' Введите длину массива n = ');
Readln(n);
{ Вместо ввода с клавиатуры заполним массив случайными числами из диапазона от 0 до 500}
For i:=1 to n do M[i]:=Random(500);
For i:=1 to n-1 do
Begin
{принимаем за минимум i-й элемент}
Min:=M[i]; i_min:=i;
For j:=i+1 to n do
If M[j]<Min then
|
|
|
Begin {найдено меньшее число - запоминаем его и его адрес}
Min:=M[j]; i_min:=j;
End;
{Обмен}
M[i_min]:=M[i];
M[i]:=Min;
End;
Writeln(' Упорядоченный массив');
For i:=1 to n do write(M[i],' ');
readkey;
End .
Обменная сортировка
Обменная сортировка основывается на последовательном сравнении двух рядом стоящих элементов и если порядок следования нарушен, элементы меняются местами. Сравнения производятся до тех пор, пока при очередном цикле просмотра всех рядом стоящих пар элементов, ни одна пара элементов не будет меняться местами. В том случае, если элементы массива уже упорядочены, алгоритм закончит свою работу после одного цикла просмотра всех рядом стоящих пар.
Просмотр пар может начинаться с начала массива или с его конца, в последнем случае алгоритм называют алгоритмом пузырьковой сортировки. Рассмотрим работу алгоритма по схеме.
Дата добавления: 2021-01-21; просмотров: 36; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!