Сортиране по метод на пряко вмъкване - метод на картоиграча

Нека имаме предварително въведена редица от стойности - данни. Алгоритъмът за сортиране по метод на пряко вмъкване се среща в литературата и като метод на картоиграча. Това е добре познатият на картоиграчите метод за нареждане на картите, при който картоиграчът, държейки в лявата си ръка картите, ги изважда една по една и ги поставя на правилната им позиция. За вмъкване на картата на правилното място се налага последователното й сравнение с вече наредените карти, до откриване на правилната позиция.

    Имаме масив от елементи от опреден тип, които искаме да сортираме. В основата на алгоритъма за сортиране чрез вмъкване стои достатъчно проста идея. Масивът се разделя на сортирана и несортирана област. Сортираната област обикновено се разполага в началото на масива, като първоначално обхваща само първия му елемент.
    Сортирането протича на n1 стъпки. На i-тата стъпка сортираната област се разширява с един елемент отдясно, като за целта добавяният i-ти елемент (нека го означим с x) се вмъква на подходящо място в сортираната последователност.
    Как става вмъкването? Един очевиден алгоритъм е последователното сравнение и евентуална размяна на x със стоящия вляво от него елемент. Процесът продължава до възникване на една от следните ситуации:
    а)достигане на елемент с ключ, по-малък или равен от този на x;
    б)достигане на първия елемент на масива.

    Двете проверки могат да се обединят в една чрез добавяне на елемент като нулев елемент на масива.

    Това е добре познатият на картоиграчите метод за нареждане на картите, при който играчът, държейки в лявата си ръка картите, ги изважда една по една и ги поставя на правилната им позиция. За вмъкване на картата на правилното място се налага последователното й сравнение с вече наредените карти, до откриване на вярната позиция.
  Имаме масив от елементи от опреден тип, които искаме да сортираме. В основата на алгоритъма за сортиране чрез вмъкване стои достатъчно проста идея. Масивът се разделя на сортирана и несортирана област. Сортираната област обикновено се разполага в началото на масива, като първоначално обхваща само първия му елемент.
  Сортирането протича на n1 стъпки. На i-тата стъпка сортираната област се разширява с един елемент отдясно, като за целта добавяният i-ти елемент (нека го означим с x) се вмъква на подходящо място в сортираната последователност.
  Как става вмъкването? Един очевиден алгоритъм е последователното сравнение и евентуална размяна на x със стоящия вляво от него елемент. Процесът продължава до възникване на една от следните ситуации:
   а)достигане на елемент с ключ, по-малък или равен от този на x;
   б)достигане на първия елемент на масива.

  Двете проверки могат да се обединят в една чрез добавяне на елемент като нулев елемент на масива.
  Следва решена задача с код на примерна програма (DEV C++), реализираща алгоритъм за сортиране по метода на пряко вмъкване - метод на картоиграча:

#include<iostream>

using namespace std;

int main()

{

 const int n=11;

 int mas[n]={0,15,6,8,1,2,3,4,7,9,11};

 int a,I,J,W,razm;


 cout<<"Da se systawi programa, koqto sortira po metoda na kartoigracha\n";

 cout<<"predwaritelno wyweden ednomeren masiw s elementi w granicite\n";

 cout<<"[-100 +100]\n";

 cout<<"Primer: 15;6;8;1;2;3;4;7;9;11 Izhod 1,2,3,4,6,7,8,9,11,15\n";

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

  for (a=1;a<n;a++)
  {cout<<mas[a]<<"; ";}//pechat na nesortiraniq masiw

   cout<<endl;

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

   razm=0;//inicializirane broj izwyrsheni razmeni

   for (I=1;I<n;I++)

    {

       W=mas[I]; mas[0]=W;

       J=I-1;

       while (W<mas[J])

       {//nachalo na wytreshniq cikyl while

         mas[J+1]=mas[J];

         J=J-1;

          razm++;

       }//kraj na while

      mas[J+1]=W;

    for (a=1;a<n;a++)
     {cout<<mas[a]<<"; ";}//pechat na nesortiraniq masiw

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

  }//kraj wynshen for


cout<<"Systoqnie na masiwa sled sortirane: \n";

  for (a=1;a<n;a++)
 {cout<<mas[a]<<"; ";}//pechat na sortiraniq masiw

  cout<<endl;

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

 system("pause");//zadyrva izpylnenieto na programata do natiskane na klawish ot klawiaturata

  return 0; 

} //kraj na programa sortirane - prqko wmykwane 


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

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

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

 
Размер на шрифта
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
Търсене в сайта: