Наредба - сортиране на елементи в масив

наредба - сортиране на елементи в масив
бързо сортиране - метод на Хоор
сортиране чрез пряка размяна - метод на мехурчето
сортиране чрез пряко вмъкване - метод на картоиграча
сортиране чрез пряка селекция - пряк избор
сливане на две наредени редици

Подреждане, сортиране на данни по определен признак, сортиране на елементи в масив е един от основните процеси при обработване на данни. Причината е ускоряване на следващо търсене в същата структура от данни било масив, било последователен файл или файл с директен достъп. Сложността на процеса на сортиране нараства изключително бързо с увеличаване броя на елементите. Не случайно Доналд Кнут отделя толкова голямо внимание на процеса сортиране в многотомния си труд. Нека споменем част от методите за сортиране - алгоритми за сортиране:

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

алгоритъм за наредба - сортиране

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

#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <time.h>
using namespace std;
int const broi=10, kolko=15, dist=3;
//kolko >broi; dist - za opredelqne shirina pri izwevdane  (kolko znaka)

void naredba();//funkciq generira i izwevda sluchajni chisla

int main()
{  char ose;
   time_t t;//polzwa tekushoto wreme
   srand( time(&t));//inicializira generator na suchajni chisla
   cout<<"Imate N broq celi chisla ot interwala [0..M], kydeto N>=M.\n";
   cout<<"Chislata sa sluchajni i ne nepremenno razlichni.\n";
   cout<<"Da se systawi programa, chrez koqto se generirat N broq\n";
   cout<<"celi chisla i se izwevdat podredeni wyw wyzhodqsh red.\n";
  do {
  naredba();//izwyrshwa sortirane - naredba
   cout<<"Velaete li prowerka s drugi chisla <y/n>: ";cin>>ose;
 } while (ose=='y' || ose=='Y');
   system("pause");       
   return 0;
}//kraj na programa naredba - sortirane

void naredba()
{ int i,j,chis,mas[broi];
  for(i=0; i<broi; i++) mas[i]= 0;//nachalna inicializaciq
  cout<<"She generiram "<<kolko<<" sluchajni chisla ot interwala [0.."<<broi<<"]\n";   
  cout<<"Nachalno systoqnie:\n";
   for(i=0; i<kolko;i++)
    {chis=rand () % broi;//generirane na sluchajni chisla
     mas[chis]++; //syotwetnata kletka na masiwa
    cout<<setw(dist)<<chis<<"; ";
    }//for i
    cout<<endl;
     cout<<"Izwevdane wyw wyzhodqsh red:\n";
     for(i=0; i<broi; i++)
     {if (mas[i]) 
      { for (j=0;j<mas[i];j++)  cout<<setw(dist)<<i<<"; ";}//if
     }//for i
  cout<<endl;   
} //kraj programa naredba - sortirane   

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

бързо сортиране - алгоритъм на Хоор

Методът бързо сортиране е предложен от К. Хоор през 1962 г. и е един от най-добрите методи за сортиране по отношение на бързодействието. Основната причина за високата му ефективност е, че се разменят местата на елементи от масив намиращи се на големи разстояния помежду си. Самият Хоор твърди за този алгоритъм, че колкото са по-разбъркани стойностите в самото начало, толкова по-бързо се осъществява процесът на сортиране.

Тук се описва алгоритъм за сортиране във възходящ ред на стойностите. Избира се случаен елемент x от декларирания масив (най-често средния елемент на масива). Претърсваме масива отпред към средата до намирането на елемент по-голям или равен на x. След това претърсваме масива от края към средата до намирането на елемент по-малък или равен на x. В случая равенството е необходимо – то се използва като ограничение при проверяване стойностите в масива. Разменят се местата на тези елементи. Алгоритъмът продължава по аналогичен начин процеса на претърсване с размяна докато границите на двете претърсвания на масива отпред и отзад не се “срещнат” в определена позиция от масива. Така се получава условно разделяне на масива на две части – предната се състои само от елементи, по-малки или равни на x, а дясната – от елементи, по-големи или равни на x. Двете части в общия случай не са равни. Сортират се поотделно всяка от двете части на масива. В примерната програма сортирането на всяка от частите на масива се извършва с рекурсивно извикване. При всяко следващо рекурсивно извикване дължината на обработваната част от масива се намалява с 1 Това гарантира, че винаги ще бъде достигнато дъното на рекурсията, т.е. завършване на процеса за сортиране на елементите от началния масив.

#include <iostream>
using namespace std;
int const broi=20;
int mas[]= {20,19,17,1,18,16,2,15,13,3,14,12,4,11,9,5,10,8,6,7};

void pechat()
{ int i;
   for (i=0;i<broi;i++) cout<<mas[i]<<"; ";
   cout<<endl;
}//pechat

void qsort( int l,int r)// Quick Sort - Hoor
{ int k,i,j,pom,x;
   k=(l+r)/2;
   x=mas[k]; //sredata
   i=l; j=r;
  do
  { while(mas[i]<x) i++;
     while(mas[j]>x) j--;
     if(i<=j)//izwyrshwa razmqna chrez treta promenliwa
     {pom=mas[i];
      mas[i]=mas[j];
      mas[j]=pom;
      i++;
       j--;
   }//razmqnata
 }while(i<=j);
//sledwashite dwa reda osyshestwqwat rekursiwno izwikwane
  if(l<j) qsort(l,j);
  if(r>i) qsort(i,r);
}//sortirane 

int main ()
{cout<<"Imate predwaritelno wywedena redica ot N estestweni chisla,\n";
  cout<<"prinadlevashi na interwala [1..101].\n";
  cout<<"Da se systawi programa, chrez koqto  se podrevadat wyw wyzhodqsh\n"; 
  cout<<"red wywedenite chisla. da se izpolzwa algoritym za sortirane na Hoor.\n";
  cout<<"Nachalno systoqnie - predi sortirane \n";   
  pechat();//pechat predi sortirane 
  qsort( 0, broi-1);//rekursiwna funkciq za sortirane
  cout<<"Krajno systoqnie - sled sortirane:\n";    
  pechat();//pechat sled sortirane 
  system("pause");
 return 0;
}//kraj na programa sortirane; 

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

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