Упорядочивание (сортировка) массива
В большинстве случаев, массивы применяются для хранения большого количества однотипной информации, создания и организации баз данных и банков данных и т.д. Во многих случаях номер (индекс) элемента в массиве не играет большой роли. Важно именно его значение, т.е. сама информация. Базы и банки данных, в свою очередь, необходимы не только для того, чтобы "складывать" в них информацию, но и для того, чтобы в любой момент была возможность удобного и быстрого доступа к ней. В обычном "неотсортированном" массиве информацию найти можно, но только уже известными вам способами последовательного перебора-просмотра всех его элементов, до тех пор, пока нужный элемент не будет обнаружен. Этот самый простой метод обладает только одним но очень существенным недостатком — на поиск одного элемента уходит много времени. все остальные методы поиска информации намного эффективнее, быстрее, но применяются только в упорядоченных, отсортированных массивах. Поэтому часто возникает задача об упорядочивании массива.
Рассмотрим простой случай такой задачи: дан числовой массив x1, x2, … , xn, элементы которого попарно различны; требуется переставить элементы массива так, чтобы после перестановки они были упорядочены в порядке возрастания: x1<x2< … <xn.
Существует несколько алгоритмов решения этой задачи. Мы рассмотрим два наиболее популярных.
Алгоритм сортировки выбором
Очевидно, что первое место в массиве должен занять минимальный элемент массива, второе — наименьший из всех остальных, третий — наименьший из оставшихся и т.д.
Для этого необходимо выполнить следующую последовательность действий:
1. Определить минимальный элемент массива.
2. Поменять его местами с первым элементом.
3. Определить минимальный элемент среди оставшихся.
4. Поменять его местами со вторым элементом и т.д.
Эта последовательность действий должна выполняться до тех пор , пока не будет определен последний минимальный элемент.
Предлагаемая программа покажет вам, как это делается:
Procedure TForm1.Button1Click(Sender:TObject);
Type mas=array[1..20]of Real;
Var a:mas;
min:Real;
I,t,k:Integer;
Begin
For i:=1 to 20 do
a[i]:=StrToFloat(StringGrid1.Cells[i,1]);
For i:=1 to 19 do
Begin
min:=a[i];
t:=i;
For k:=(i+1) to 20 do
If min>a[i] then
Begin
min:=a[k];
t:=k;
End;
a[t]:=a[i];
a[i]:=min;
End;
For i:=1 to 20 do
StringGrid2.Cells[i,1]:=FloatToStr(a[i,1]);
End;
Алгоритм "пузырьковой" сортировки
Алгоритм так называемой "пузырьковой" сортировки более оригинален и в большинстве случаев более эффективен. При использовании этого алгоритма весь массив просматривается несколько раз подряд. При каждом таком просмотре сравниваются последовательно только соседние элементы массива: сначала первый со вторым, потом второй с третьим, и в конце предпоследний с последним. Если при сравнении окажется, что предыдущий элемент больше следующего, они меняются местами, описанным выше способом. Так в результате одного последовательного просмотра элементы, значение которых больше, "всплывают" образно говоря на поверхность, т.е. ближе к концу массива. Если провести такой последовательный просмотр массива несколько раз, то "тяжелые" элементы окончательно "затонут" и массив окажется отсортированным. Остается нерешенным еще один вопрос. сколько раз необходимо выполнять такой просмотр? Ведь может оказаться, что и одного просмотра будет достаточно. Столько, сколько нужно для полной сортировки, т.е. пока при просмотре элементы не будут меняться местами. Для этого удобно организовать логическую переменную p, и присваивать ей значение ложь в случае, если замена происходила хотя бы один раз. Если значением этой переменной останется истина, то просмотры необходимо прекратить.
Предлагаемая вам ниже программа реализована на основе метода пузырьковой сортировки. Она выполняет полную сортировку массива, состоящего из 10 действительных чисел по возрастанию.
Procedure TForm1.Button1Click(Sender:TObject);
Type mas=array[1..10] of Real;
Var a:mas;
p:Boolean;
v:Real;
i:Integer;
Begin
For i:=1 to 10 do {Ввод элементов массива}
a[i]:=StrToFloat(StringGrid1.Cells[i,1]);
Repeat
p:=True; {Предположим, что массив уже отсортирован}
For i:=1 to 9 do {Цикл для организации просмотра}
If a[i]>a[i+1] then {Сравнение двух соседних элементов}
Begin {Меняем соседние элементы местами}
v:=a[i];
a[i]:=a[i+1];
a[i+1]:=v;
p:=False; {Как оказалось, массив неотсортирован}
End;
Until p; {Выполняем просмотры, пока р=True}
For i:=1 to 10 do {Вывод массива}
StringGrid2.Cells[i,1]:=FloatToStr(a[i]);
End;
Контрольные вопросы:
1. Опишите идею сортировки массива методом выбора и последовательность действий для его реализации на языке Delphi.
2. Опишите идею сортировки массива "пузырьковым" методом и последовательность действий для его реализации на языке Delphi.