Сортировка массива в делфи

Сортировка массива в делфи

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

Следует отметить, что максимальное необходимое количество циклов проверки соседних элементов массива равно количеству элементов массива минус один. Вместе с тем возможно, что массив реально будет упорядочен за меньшее число циклов. Например, последовательность чисел 5 1 2 3 4, если ее рассматривать как представление массива, будет упорядочена за один цикл, и выполнение оставшихся трех циклов не будет иметь смысла.

Поэтому в программу введена логическая переменная changed, которой перед выполнением очередного цикла присваивается значение FALSE. Процесс сортировки (цикл repeat) завершается, если после выполнения очередного цикла проверки соседних элементов массива (цикл for) ни один элемент массива не был обменен с соседним, и, следовательно, массив уже упорядочен.

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

Таким образом, быстрая сортировка — это рекурсивный алгоритм, то есть алгоритм вызывающий сам себя. Время быстрой сортировки пропорционально n*log(n) . Однако, у алгоритма быстрой сортировки есть и недостатки. Массив случайных чисел сортируется очень быстро, однако только что отсортированный массив повторно процедура может обрабатывать крайне медленно, вплоть до полного исчерпания ёмкости стека, так как эффективность алгоритма крайне зависит от удачного выбора опорного элемента.

Читайте также:  Как открыть домофон метаком без ключа видео

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

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

Лучшим выбором для опорного элемента является средний элемент в массиве. Поэтому нужно выбирать опорным элемент, имеющий средний индекс. Это позволяет минимизировать вероятность самого неблагоприятного выбора — наименьшего элемента в массиве. Ещё лучше в качестве опорного выбирать элемент со средним значением из элементов с первым, последним и средним индексом.

Псевдокод алгоритма быстрой сортировки:

Процедура QuickSort(A: массив, min — начальный индекс, max — конечный индекс);
Начало
1. Выбрать supp — элемент со средним индексом (опорный):
2. Начать просмотр с начала массива и найти элемент, больший опорного A[i]>supp
3. Начать просмотр с конца массива и найти элемент, меньший опорного A[j]

Вот реализация алгоритма быстрой сортировки в Delphi:

type TArray: Array of Integer; //Параметры массива нужно определить до вызова процедуры

procedure qSort(var A: TArray; min, max: Integer);
var i, j, supp, tmp: Integer;
begin
supp:=A[max-((max-min) div 2)];
i:=min; j:=max;
while i supp do j:=j-1;
if i

Читайте также:  Как открыть файл рег

Теперь для сортировки динамического массива A можно использовать вызов qSort со следующими параметрами:

qSort(A, 0, High(A)); //0 — начальный индекс, High(A) — конечный индекс массива A

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

Что такое массив

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

Синтаксис и размер массива Delphi

В языке delphi формирование массива осуществляется при помощи ключевого слова “array”. Объявляется массив в области var и имеет следующую, обобщенную конструкцию:

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

В квадратных скобках следует указывать через две точки “..”, начальный и конечный индексы. Выглядеть это будет так:

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

Методы сортировки массива Delphi

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

Читайте также:  A data dashdrive durable hd710 2tb

Еще один популярный способ – это сортировка массива Delphi методом рекурсии. Суть его заключается в том, что берется в качестве опорного, произвольный элемент массива и с ним сравниваются все остальные. Результатом будет то, что слева от опорного будет находиться элементы с меньшим значение, а справа с большим. Далее аналогично выбирается опять опорный элемент в каждой части и производится упорядочивание. Такая сортировка массива происходит до тех пор, пока при очередном проходе в одной части будет всего один элемент.

Разумеется, что производить такие операции в ручном режиме, очень долго и не практично. Полноценная сортировка массива Delphi осуществляется при помощи циклов.

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

Ссылка на основную публикацию
Adblock detector