Алгебра

Сортиране чрез пряка размяна - метод на мехурчето

Съдържание

Нека имаме предварително въведена редица от стойности - данни. Алгоритъмът за сортиране чрез пряка размяна извършва на всяка "обиколка" на редицата от данни n-1 сравнения – т.е. сравнява елемент 1 с елемент 2, елемент 2 с елемент 3 .... елемент n-1 с елемент n. Ако при сравняването по двойки се окаже, че в дадена съседска двойка има инверсия, т.е. елементите не са правилно поставени се извършава размяна на местата им. Процесът продължава, докато при поредната обиколка на редицата не се извърши нито една размяна на елементи. Алгоритъмът за сортиране чрез пряка размяна се нарича също метод на мехурчето - най-лекия елемент плавно изплува към мястото си, а най-тежкия елемент потъва още при първото обхождане. Най-тежкия вариант при решаване на задача за сортиране с този алгоритъм е при подредена в обратната последователност редица, а най-лекия вариант е при изцяло или поне частично наредена редица. Описаният алгоритъм е устойчив, т.к. при повторно сортиране няма да се промени наредбата на елементите.

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

   Едно примерно условие на задача за сортиране е:.   Имате предварително въведен едномерен масив с елементи от интервала [-100..100]
  Да се състави програма, която сортира вектора по метода на мехурчето.
  Пример: 6,8,12,2,3,4,7,9,1
  Изход: 1,2,3,4,6,7,8,9,12

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

#include<iostream>

using namespace std;

int main()

{

  const int n=10;//she izpolzwame 0-wiq element za 3-ta promenliwa pri razmqna

   int a1,mas[n]={1001,6,8,12,2,3,4,7,9,1};

  int a,b,razm;

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

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

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

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

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

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

   cout<<endl;

  razm=0;//sledqt se obshiq broj izwyrsheni rezmeni - samo za iliustrirane

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

   b=1;//flag dali e izwyrshwana razmqna na stojnosti - podrevdane

   //ako ima dori 1 razmqna sortiraneto prodylvawa

   while (b>0)

   { //dokato ne preminat wsichki prowerki bez razmqna na stojnost

      b=0;//w nachaloto na obikolkata se priema, che ne e izwyrshwana razmqna

    for (a=2;a<n;a++)

     {//prowerqwat se wsichki elementi ot wtoriq do posledniq element

          if (mas[a]<mas[a-1]) //srawnqwat se tekushiq element s predhodniq

           {  b=1;//izwyrshwa se razmqna na stojnosti

                 mas[0]=mas[a-1];//razmqna na stojnosti chrez treta promenliwa

                mas[a-1]=mas[a];

                mas[a]=mas[0];

                razm++;

            }//kraj if

    }//kraj for

  if  (b) cout<<"Ima izwyrshena razmqna\n"; else cout<<"Nqma izwyrshena razmqna\n";

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

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

       }//kraj while

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

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

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

      cout<<endl;

       system("pause");

     return 0; 

} //kraj na programa sortirane - prqka razmqna

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

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

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

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

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

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

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

Сортиране чрез пряка размяна - метод на мехурчето

Съдържание