Здравствуйте!!! На форуме очень много раз выкладывались алгоритмы различных сортировок и хотелось бы посвятить немного времени на написание функции на одну из них. А именно Линейной Сортировке.
Название метода линейная сортировка происходит от последовательного просмотра всех элементов массива, находящихся в их исходном линейном порядке.
В этом методе при отборе каждого ij-го элемента массива требуется выполнять его сравнениеи с последующими элементами, имеющие номера: ij+1, ij+2, ij+3,...,ij+n-1. и каждый из них может оказаться текущим кандидатом искомого элемента упорядочиваемого ряда. Поэтому переменную обозначающую номер такого дежурного кандидата, назовём iCan (от candidat).
Поскольку число сопоставлений в каждом цикле отбора минимального значения всегда известно, то удобнее всего применить цикл for, переменная iCan будет играть в нём роль параметра цикла.
C++ | 1
2
3
4
5
6
| for(int iCan = ij+1, iByf; iCan < list->Count; ++iCan) //iByf от Byfer, iCan от Candidat
{
if(mass[ij]>mass[iCan]) //по возрастанию
{
//Меняем местами содержимое ячеек
} |
|
Здесь логический блок оператора if осуществляет перестановку элементов mass[ij] и mass[iCan]. Если на место элемента mass[ij] поместить элемент mass[iCan], то прежнее значение в ячейке mass[ij] исчезнет на всегда; если же, наоборот, ячейке mass[iCan] присвоить величину из
mass[ij], то оакажется потеряным значение в mass[iCan]. Однако такие потери недопустимы, поскольку mass[ij] и mass[iCan] должны быть соответствующими элементами отсортированного массива. Поэтому для временного хранения mass[ij] (или mass[iCan]) в разделе инициализации цикла for введена переменная iBuf (от Byfer). В этом случае перестановку элементов можно организовать следующей последовательностью операторов:
C++ | 1
2
3
| iByf = mass[ij];
mass[ij] = mass[iCan];
mass[iCan] = iByf; |
|
Число циклов сравнения также полностью определяется количеством элементов массива, поэтому было бы менее разумным для изменения номера отбираемого элемента применять вместо цикла for иной цикл.
В этом примере я использовал такие компоненты как:
Edit1(InputMas)
Edit2(OutputMas)
Button1(Power)
Label1(In Mas) // для подписи к Edit1(InputMas)
Label2(Out Mas) // для подписи к Edit2(OutputMas)
В первый InputMas будем вводить через пробел числа для сортировки. При нажатии на Power числа в отсортированном виде будут выводиться в OutputMas.
Перетягиваем на форму вышеперечисленные компонеты и пишем фунцию. Функция выглядит таким образом:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| AnsiString SelectionSort(AnsiString asd)
{
TStringList * list = new TStringList(); //создаём динамически объект класса TStringList
list->DelimitedText = Trim(asd); //разделяем строки в объекте list и удаляем передний и задний пробел в строке
list->Delimiter = ' '; //разделитель
asd ="";
int *mass = new int[list->Count]; //создаём массив с текущей длиной по количеству строк объекта list класса TStringList();
for(int d = 0; d < list->Count; d++)
{
mass[d] = list->Strings[d].ToInt(); //заносим данные в массив
}
// Линейная сортировка
for(int ij = 0; ij < list->Count-1;++ij)
{
for(int iCan = ij+1, iByf; iCan < list->Count; ++iCan) //iByf от Byfer, iCan от Candidat
{
if(mass[ij]>mass[iCan]) //по возрастанию
{
//Меняем местами содержимое ячеек
iByf = mass[ij];
mass[ij] = mass[iCan];
mass[iCan] = iByf;
}
}
}
for (int s = 0; s < list->Count; s++)
{
asd+=IntToStr(mass[s])+ " "; // вывод массива в переменную asd
}
delete [] mass; // удаление объекта массива созданного динамически
mass = NULL;
delete list; // удаление объекта list созданного динамически
list = NULL;
return asd;
} |
|
Вызов функции будет таким:
C++ | 1
2
3
4
5
6
7
8
9
10
| void __fastcall TForm1::PowerClick(TObject *Sender)
{
if(InputMas->Text.IsEmpty())
{
ShowMessage("Введите в поле через пробел вещественные числа ");
InputMas->SetFocus();
return;
}
OutputMas->Text = SelectionSort(InputMas->Text); //вызов функции SelectionSort
} |
|
Как показано на 1 скриншоте сортировка идёт по возрастанию.
Для того чтобы сделать сортировку по убыванию, необходимо в этой строке:
C++ | 1
2
|
if (mass[ij]>mass[iCan]) |
|
поменять знак на противоположный т.е сделать вот так
C++ | 1
| if (mass[ij]<mass[iCan]) |
|
Как показано на 2 скриншоте сортировка идёт по убыванию.
Программа создавалась в среде разработки С++Builder 6
Источник: Федоренко Ю.П "Алгоритмы и программы на С++ Builder" г. Москва, 2010 г. |