Разработка программы сортировки данных на языке Turbo Pascal
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
»ученный результат a b c d e f
Алгоритм:
{ сортировка Шелла }Shell (var item: DataArray; count: integer);= 5;, j, k, s, m: integer;: array [1. t] of integer;: DataItem;[1]: =9; h [2]: =5; h [3]: =3; h [4]: =2; h [5]: =1;m: = 1 to t do: =h [m];: =-k;i: = k+1 to count do: = item [i];: = i-k;s=0 then: = - k;: = s+1;[s]: = x;;(x<item [j]) and (j<count) do[j+k]: = item [j];: = j-k;;[j+k]: = x;
end;;; { конец сортировки Шелла }
При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.
Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1, которая использована в показанном выше примере. Следует избегать последовательностей степени двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. (Однако, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно).
Внутренний цикл имеет два условия проверки. Условие "х0" и "j<=count" необходимы для того, чтобы предотвратить выход за пределы массива "item". Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значения. Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки.
Анализ сортировки Шелла требует решения некоторых сложных математических задач. Время выполнения сортировки Шелла пропорционально n1.2 Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки. Однако, прежде чем вы решите использовать сортировку Шелла, следует иметь в виду, что быстрая сортировка дает даже еще лучшие результаты.
3. Внедрение
3.1 Интерфейс программного продукта
Запуск программы осуществляется при открытии файла в Приложении А МETHOD. exe.
Рис.3.1 Основное окно программы.
Далее нужно выбрать метод сортировки и нажать на соответствующую номеру клавишу на клавиатуре.
После этого программа выдаст исходный массив чисел (генерируется случайным выбором) и отсортированный массив (см. рис.3.2).
Чтобы протестировать еще один метод, достаточно нажать "Enter" и выбрать другой номер, соответствующий номеру метода сортировки.
Выход из программы осуществляется нажатием на "0".
Рис.3.2 Осуществление процесса сортировки
При разработке программы использовались следующие конструкции языка приведены ниже:
Условие:условие then begin
…
else
цикл, с постоянным вхождением в цикл:переменная: = 1 to n do оператор;
…;
А так же конструкции вывода и чтения данных:(информация); // вывод данных(переменная); // чтение данных
цикл с предусловием:(условие) do
.
оператор;
.;
оператор выбора условию равенств значения переменной:переменная of
значение 1: оператор;
значение 2: оператор;
.
значение n: оператор;
При создание курсовой работы так же пользовалась функциями библиотеки crt.
3.2 Текст программы
Program Kurs;crt;n = 10;Mas = array [1. n] of integer;: Mas;: char;Menu;;(Выберете метод сортировки: );(1. Пузырьком);(2. Выбором);(3. Вставкой);(4. Шелла);(0. Выйти из программы);();(Автор программы - Орлов Сергей Валерьевич);
Writeln;(: > );;ZapMas;i: integer;;;(Исходный массив: );i: =1 to n do[i]: = random (20) - 10;(a [i]: 3, );;;;Bubble (var item: Mas); {puzirkom},j: integer;: integer;i: = 2 to n doj: = n downto i doitem [j-1] >item [j] then: = item [j-1];[j-1]: = item [j];[j]: = x;;;;Selekt (var item: Mas); { viborom}, j, k: integer;: integer;i: = i to n-1 do: = i;: = item [i];j: = i+1 to n doitem [j] A [i+d] then: = A [i];[i]: = A [i+d];[i+d]: = t;: = true;;;;: = d div 2;;;outmas;i: integer;(Отсортированный: );i: = 1 to n do(a [i]: 3, );;;;: =-;keypressed then: = readkey;k of
1: begin;(a);;;;;
2: begin;(a);;;;;
3: begin; Insert (a);;;;;
4: begin;;;;;;;;k=0;.
Заключение
В ходе курсовой работы была написана программа на языке Turbo Pascal, позволяющая сортировать линейный массив 4-мя методами:
) Методом пузырька;
) Методом вставок;
) Методом выбора;
) Методом Шелла.
Были рассмотрены вопросы: постановка задачи о сортировке, основные алгоритмы сортировки, их принципы действия и области применения.
Рассмотренные в данной курсовой работе методы сортировки имеют как преимущества, так и недостатки. Выбор того или иного алгоритма сортировки зависит от конкретной задачи.
Так, сортировка большого числа элементов пузырьковым методом, методом вставки или выбора потребует много времени, т.к. время выполнения сортировк?/p>