Форум программистов, компьютерный форум, киберфорум
Sasha
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  

Линейная сортировка (возрастание, убывание) (Selection Sort)

Запись от Sasha размещена 12.03.2014 в 16:00
Показов 7690 Комментарии 1

Здравствуйте!!! На форуме очень много раз выкладывались алгоритмы различных сортировок и хотелось бы посвятить немного времени на написание функции на одну из них. А именно Линейной Сортировке.

Название метода линейная сортировка происходит от последовательного просмотра всех элементов массива, находящихся в их исходном линейном порядке.
В этом методе при отборе каждого 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 скриншоте сортировка идёт по возрастанию.

Нажмите на изображение для увеличения
Название: Безымянный.JPG
Просмотров: 884
Размер:	11.2 Кб
ID:	2148

Для того чтобы сделать сортировку по убыванию, необходимо в этой строке:

C++
1
2
 
if (mass[ij]>mass[iCan])

поменять знак на противоположный т.е сделать вот так

C++
1
if (mass[ij]<mass[iCan])

Как показано на 2 скриншоте сортировка идёт по убыванию.

Нажмите на изображение для увеличения
Название: Безымянный1.JPG
Просмотров: 848
Размер:	11.3 Кб
ID:	2149

Программа создавалась в среде разработки С++Builder 6


Источник: Федоренко Ю.П "Алгоритмы и программы на С++ Builder" г. Москва, 2010 г.
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 1
Комментарии
  1. Старый комментарий
    Аватар для Avazart
    Почему линейная?
    https://ru.wikipedia.org/wiki/... E%F0%EE%EC
    Запись от Avazart размещена 09.05.2015 в 00:32 Avazart вне форума
 
Новые блоги и статьи
Лето уходит
kumehtar 17.08.2026
Мысли в слух
kumehtar 17.08.2026
Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега
Maks 17.08.2026
Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .
Саморегулирующийся социальный контракт для сервера cross-section.
Hrethgir 14.08.2026
С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru