Алгебра

Сортиране чрез пряка селекция - пряк избор

Съдържание

Сортиране е процес на нареждане елементи по определен признак. Нека имаме предварително въведена редица от стойности - данни. Алгоритъмът за сортиране чрез пряка селекция, прекия избор (selection sort) е един от основните методи за сортиране. Той е със сложност O(n^2).

   Нека имаме редица с n броя елементи.
   Чрез този алгоритъм се обхожда редицата n–1 пъти и се поставя на "правилното" място всяка отделна стойност.
   При алгоритъма на пряка селекция, последователните действия са:
   (1) Избиране на минимална стойност като предварително се запомня мястото й в редицата (масива).
   (2) Освобождаване на позицията, на която избраната стойност трябва да бъде записана.
   (3) Записване на избраната стойност на полагаемото й се място.
   Смяната на местата на отделните елементи се извършва посредством оператори за присвояване на стойност – най-често с трета – допълнителна променлива.
   Ако има частично подредена редица алгоритъмът ще продължава проверката дори и всички елементи да са заели правилните си места. Това на практика довежда до продължаваща работа на алгоритъма без промяна наредбата на елементите. В случая е илюстрирано чрез повторение на последните 4 стъпки (7,8,9 и 10).
   В описания по-долу пример е показан обратния случай - първо се нареждат най-големите елементи.
   Начално състояние на редицата: 15;6;8;1;2;3;4;7;9;11
   1-ви етап: 11;6;8;1;2;3;4;7;9;15
   2-ри етап: 9;6;8;1;2;3;4;7;11;15
   3-ти етап: 7;6;8;1;2;3;4;9;11;15
   4-ти етап: 4;6;7;1;2;3;8;9;11;15
   5-ти етап: 3;4;5;1;2;7;8;9;11;15
   6-ти етап: 2;3;4;1;6;7;8;9;11;15
   7-ми етап: 1;2;3;4;6;7;8;9;11;15
   8-ми етап: 1;2;3;4;6;7;8;9;11;15
   9-ти етап: 1;2;3;4;6;7;8;9;11;15
   10-ти етап: 1;2;3;4;6;7;8;9;11;15

   Търси се най-големият елемент и той си разменя мястото с последния елемент от редицата. Това продължава толкова пъти колкото са елементите в редицата

  Следва код на примерна програма даваща решена задача с алгоритъм за сортиране по метод на пряка селекция - метод на прекия избор:
   Имате предварително въведен едномерен масив с елементи от интервала [1..100]
   Да се състави програма за сортиране на стойностите на масива чрез метода "сортиране чрез пряка селекция".
   Пример: 15; 6; 8; 1; 2; 3; 4; 7; 9; 11;
   Изход: 1; 2; 3; 4; 6; 7; 8; 9; 11; 15;

#include <iostream>

using namespace std;

int main() 

{//nachalo na programa

const int N=10;//razmer na masiwa

int P,J,K,L,A,razm,mas[N]={15,6,8,1,2,3,4,7,9,11};


  cout<<"Da se systawi programa za sortirane na predwaritelno wyweden \n";

  cout<<"ednomeren masiw ot estestweni chisla. Programata da realizira \n";

  cout<<"metoda 'sortirane chrez selekcia'.\n";
  
  cout<<"Algoritymyt na tozi metod e sledniqt:\n";

  cout<<"1. Tyrsi se naj-golemiqt element.\n";

  cout<<"2. Namereniqt naj-golqm element razmenq mqstoto si s \n";

  cout<<"posledniq element na masiwa.\n";

  cout<<"3. Goreopisanite stypki se powtarqt s pyrwite N-1 elementa, posle\n";

  cout<<"s pyrwite N-2 elementa i t.n., dokato ostane samo edin element.\n";

  cout<<endl;

  cout<<"Nachalno systoqnie na masiwa:\n";

   for (P = 0;P < N;P++) {cout<<mas[P]<<"; ";}

  cout<<endl;

  razm=0;//inicializira broq izwyrsheni razmeni

  cout<<"Zapochwa sortirowka..\n";

  for (P = N-1;P >= 0;P--)//elementite w masiwa sa N, no zapochwat ot 0-wiq

  { //nachalo na wynshniq for

    K=P; 
     L=mas[K];//tekushiq posleden element

  for (J=0;J<=P;J++)

   {

    if (mas[J]>L)//prowerqwa za nepodreden element

    { K=J;

      L=mas[J];
     mas[K]=mas[P]; mas[P]=L;//razmqna na elementite

     razm++;

    }//kraj if

    }//kraj na wytreshniq for J

  for (A = 0;A < N;A++) {cout<<mas[A]<<"; ";}//dawa tekushoto podrevdane

  cout<<" - etap na sortirane \n";

 }//kraj na wynshniq cikyl for P

   cout<<"Krajno systoqnie na masiwa:\n";//masiwyt e okonchatelno sortiran

   for (P = 0;P < N;P++) {cout<<mas[P]<<"; ";}

   cout<<endl;

  cout<<"Broj izwyrsheni razmeni: "<<razm<<endl;

  system("pause");

   return 0;

} //kraj na programa sortirane prqka selekcia

Блок схемата на алгоритъма за пряка селекция е в приложените електронни уроци.

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

Начало на страницата

Размер на шрифта

Търсене в сайта:

Полезни връзки

Изпълними приложения за

Сортиране чрез пряка селекция - пряк избор

Съдържание