Алгоритмы сортировки одномерных массивов

ВВЕДЕНИЕ

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

С понятием "массив" приходится сталкиваться при решении  научно-технических и экономических  задач обработки совокупностей  большого количества значений. Массивы  упрощают процесс управления данными, когда используется несколько десятков или более элементов данных одного типа, и они дают прекрасное введение в методики работы с базами данных. Массивы полезны тем, что они помогают обрабатывать большие объемы данных такими способами, которые оказались бы нереализуемыми при использовании традиционных переменных.

В данной курсовой работе рассматривается один из способов обработки массивов - сортировка массива.

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

Научная значимость данной работы состоит в описании и исследовании наиболее популярных методов сортировки. Практическая значимость темы «Сортировка массивов» состоит  в анализе проблем реализации и использовании различных видов сортировок.

 

ГЛАВА 1. ИССЛЕДОВАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ

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

1.1.  ПРЕДПРОЭКТНОЕ ОБСЛЕДОВАНИЕ

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

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

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

В качестве элементов  массива можно использовать и  любой другой ранее описанный тип, поэтому вполне правомерно существование массивов записей, массивов указателей, массивов строк, массивов массивов и т.д. Элементами массива могут быть данные любого типа, включая структурированные. Тип элементов массива называется базовым. Особенностью языка Паскаль является то, "что число элементов массива фиксируется при описании и в процессе выполнения программы не меняется.

Элементы, образующие массив, упорядочены таким образом, что  каждому элементу соответствует  совокупность номеров (индексов), определяющих его местоположение в общей последовательности. Доступ к каждому отдельному элементу осуществляется путем индексирования элементов массива. Индексы представляют собой выражения любого скалярного типа, кроме вещественного. Тип индекса определяет границы изменения значений индекса. Для описания массива предназначено словосочетание array of (массив из).

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

Если в такой форме  описания массива задан один индекс, массив называется одномерным, если два индекса - двумерным, если n индексов - n-мерным. Одномерный массив соответствует понятию линейной таблицы (вектора), двумерный - понятию прямоугольной таблицы (матрицы, набору векторов). Размерность ограничена только объемом памяти конкретного компьютера. Одномерные массивы обычно используются для представления векторов, а двумерные - для представления матриц.

Элементы массива располагаются  в памяти последовательно. Элементы с меньшими значениями индекса хранятся в более низких адресах памяти. Многомерные массивы располагаются таким образом, что самый правый индекс возрастает самым первым.

Динамическим называется массив, размер которого может меняться во время  исполнения программы. Для изменения размера динамического массива язык программирования, поддерживающий такие массивы, должен предоставлять встроенную функцию или оператор. Динамические массивы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объёмы данных, а регулировать размер массива в соответствии с реально необходимыми объёмами. Обычные, не динамические массивы называют ещё статическими.

 

1.1.1  Действия над массивами

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

1.1.2.  Действия над  элементами массива

После объявления массива  каждый его элемент можно обработать, указав идентификатор (имя) массива  и индекс элемента в квадратных скобках. Например, запись Mas[2], VectorZ[10] позволяет обратиться ко второму элементу массива Mas и десятому элементу массива VectorZ. При работе с двумерным массивом указываются два индекса, с п-мерным массивом - n индексов. Например, запись MartU[4,4] делает доступным для обработки значение элемента, находящегося в четвертой строке четвертого столбца массива MartU.

Индексированные элементы массива называются индексированными переменными и могут быть использованы так же, как и простые переменные. Например, они могут находиться в выражениях в качестве операндов, использоваться в операторах for, while, repeat, входить в качестве параметров в операторы Readln, Read, Writeln, Write; им можно присваивать любые значения, соответствующие их типу.

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

 

1.2.  СОРТИРОВКА МАССИВОВ

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

Существует множество  алгоритмов сортировки массивов, с  разной эффективностью.

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

 

 

2. Глава   Разработка программы «Сортировка массива».

 

1.  Постановка задачи

Задачами  курсовой работы является:

- Организовать загрузку массива в память.

- Создать средства отображения.

- Обеспечить манипуляции  над массивом (сортировка, фильтры).

Сформулируем задание  на курсовую работу:

Программа производит открытие текстового файла с данными для массива и загружает их в динамический индексированный массив.

Предусмотрена возможность  подготовить текстовый файл для  работы программы и загружать  его данные для обработки. Просмотра, поиска данных, а также добавление, удаление  записей (строчек).

Для отображения данных используется StringGrid (далее таблица).

Возможность навигации  построена на обычных кнопках.

Сортировка массива  происходит в памяти (сортируется  сам массив), а таблица только отображает данные с учетом параметров. Параметры следующий: количество строк отображаемых в таблице, номер страницы, условия сортировки и фильтров.

При работе с фильтрами  будет создан массив индексов с ссылками на индексы в основном массиве.

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

 

2. Функциональная и логическая структура программы.

Соответственно описанной выше методике составим блок–схему сортировки массивов данных

 

 

 

3. Математическое обеспечение программы

ФОРМУЛЫ, ОПИСАТЬ КОТОРЫЕ ИСПОЛЬЗУЮТСЯ

Использование сортировки методом «пузырьков».

 

 

2.4. Разработка алгоритма программы

В проекте будут использоваться стандартные компоненты Delphi.

Для визуализации вывода массива используется компонент  StringGrid (рис. 1). Наиболее часто будет  использоваться метод доступа к  ячейкам, чтобы разместить содержимое массива в таблица.

Рис 1.

Будут использованы методы предка tStringGrid, MoveColumn – для размещения колонок в удобном для пользователя порядке. Сортировка будет производится щелчком манипулятора мышь по заголовку колонки.

Также будут задействованы  свойства StringGrid, ColCount и  
RowCount – для заданию нужного количества строк и колонок в зависимости от просматриваемых данных массива.

Также будет использован  компонент TMenu – в котором будут  расположены основные операции.

Из кнопок tButton будет  собрана панель навигации по массиву, а также задание количества выводимых строк массива в StringGrid.

2.5  Описание пользовательского  интерфейса

2.6  Принцип построения  комплекса технических средств

С какими техническими средствами она совметима , скакими программами  работает минимальные требования

 

 

 

Список литературы