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

Съдържание

Сортиране е процес на нареждане елементи по определен признак. Нека имаме предварително въведена редица от стойности - данни. Алгоритъмът за сортиране чрез пряка селекция, прекия избор (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 


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

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

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

 
Размер на шрифта
Increase Font Size Option 3 Reset Font Size Option 3 Decrease Font Size Option 3
Bulgarian Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish
Търсене в сайта: