Алгебра

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

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

    Имаме масив от елементи от опреден тип, които искаме да сортираме. В основата на алгоритъма за сортиране чрез вмъкване стои достатъчно проста идея. Масивът се разделя на сортирана и несортирана област. Сортираната област обикновено се разполага в началото на масива, като първоначално обхваща само първия му елемент.
    Сортирането протича на 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

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

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

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

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

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

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

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

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