Алгоритмы поиска и сортировки данных
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
инципом долговременного взаимовыгодного сотрудничества с нашими партнерами. Мы готовы предоставить в Ваше распоряжение имеющийся у нас производственный и кадровый потенциал, знания и опыт работы на рынке нетканых материалов.
Основные этапы развития компании:
Основание компании.
Выпуск основы для производства столовой клеенки.
Компания - крупнейший в СССР поставщик нетканой основы.
Выпуск иглопробивных полотен.
Выпуск термоскрепленных полотен.
Экспорт продукции.
Выпуск объемных и холстопрошивных полотен.
Внедрение компьютерной информационной системы управления компанией.
Реализация стратегии роста на рынке полотен для автомобильной промышленности.
Выпуск линолеума на нетканой основе.
Реализация инвестиционной программы модернизации производства.
Расширение производства иглопробивных полотен.
Внедрение системы штрихового кодирования продукции.
Реализация инвестиционной программы расширения производства иглопробивных полотен.
Реализация инвестиционной программы расширения производства.
Сертифицирована система качества на соответствие требованиям МС ISO 9001:2000.
Выпуск полипропиленового волокна.
Реализация инвестиционного проекта и увеличение мощностей предприятия по выпуску иглопробивных полотен.
Выпуск полиэфирного волокна.
Увеличение мощностей по выпуску иглопробивных полотен.
-2008 Поэтапное увеличение мощностей предприятия по выпуску полиэфирного волокна.
Увеличение мощностей компании по выпуску иглопробивных и иглопробивных-термоскрепленных полотен.
Компания становится общепризнанным лидером России по производству синтетических волокон.
Увеличение объемов выпуска и расширение ассортимента нетканых материалов для автомобильной промышленности.
Увеличение мощностей по выпуску иглопробивных полотен.
.2 Постановка задачи
В процессе работы на предприятии очень часто возникает необходимость в сортировке и поиске данных. Предприятие имеет дело с большими объемами информации (списки поставщиков, перечень комплектующих, ассортимент продукции, списки сотрудников) и обрабатывать такие массивы вручную - это довольно большие затраты времени. Кроме того при ручной обработке не исключена вероятность ошибок.
Именно для этой цели и поставлена задача разработать программное средство, которое будет выполнять сортировку больших объемов текстовых данных, и выполнять поиск необходимой информации в массивах данных.
2. Основные сведения про используемые алгоритмы
сортировки и поиска
Сортировка выбором:
Сортировка выбором начинается с поиска наименьшего элемента в списке и обмена его с первым элементом (таким образом, наименьший элемент помещается в окончательную позицию в отсортированном списке). Затем сканируется список, начиная со второго элемента, в поисках наименьшего среди оставшихся п - 1 элементов и найденный наименьший элемент обменивается со вторым, т.е. второй наименьший элемент помещается в окончательную позицию в отсортированном списке.
В общем случае, при i-ом проходе по списку (0 i п - 2) алгоритм ищет наименьший элемент среди последних п - i элементов и обменивает его с Ai;
После выполнения п - 1 проходов список оказывается отсортирован. Вот псевдокод данного алгоритма, в котором для простоты предполагается, что список реализован в виде массива.
Алгоритм SelectionSort (A[0..n - 1])
// Сортировка массива методом выбора
// Входные данные: Массив А[0..n - 1] упорядочиваемых элементов
// Выходные данные: Массив A[0..n - 1], отсортированный
// в неубывающем порядке
for i = 0 to n - 2 do
min = ij = i + 1 to n - 1 doA[j] < A[min]= j
Обмен A[i] и A[min]
В качестве примера на рис. 2.1 приведена сортировка выбором следующего списка: 89, 45, 68, 90, 29, 34, 17.
Рис. 2.1. Сортировка выбором списка 89, 45, 68, 90, 29, 34, 17
Пузырьковая сортировка:
Суть метода пузырьковой сортировки состоит в сравнении соседних элементов и их обмене, если они находятся не в надлежащем порядке. Неоднократное выполнение этих действий заставляем наибольший элемент "всплывать" к концу списка. Следующий проход приведет к всплыванию второго наибольшего элемента, и так до тех пор, пока после п - 1 итерации список не будет полностью отсортирован.
Ниже приведен псевдокод данного алгоритма.
Алгоритм BubbleSort (A[0..n - 1])
// Сортировка массива пузырьковой сортировкой
// Входные данные: Массив А[0..n - 1] упорядочиваемых элементов
// Выходные данные: Массив A[0..n - 1], отсортированный
// в неубывающем порядке
for i = 0 to n - 2 do
for j = 0 + 1 to n - 2 - i doA[j + 1] < A[j]
Обмен A[j] и A[j + 1]
Применение описываемого алгоритма к списку 89, 45, 68, 90, 29, 34, 17 показано на рис. 2.2.
Рис. 2.2. Два первых прохода пузырьковой сортировки списка 89, 45, 68, 90, 29, 34, 17
Сортировка вставкой:
Рассмотрим применение метода уменьшения на единицу к сортировке массива А[0..n-1]. Следуя идее метода, полагаем, что задача меньшего размера, а именно сортировка массива А[0..n-2], уже решена и имеется отсортированный массив размером n-1: А[0] … А[n-2]. Каким образом воспользоваться этим решением задачи меньшего размера для получения решения исходной задачи, учитывающей наличие элемента А[n-1]? Очевидно, все, что необходимо, - это найти нужную позицию среди отсортированных элементов и вставить туда элемент А[n - 1].
Для этого используется следующий способ: сканируется отсортированный подмассив слева направо, пока не достигается первый элеме