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

Съдържание

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

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

сортиране чрез пряко вмъкване - метод на картоиграча;
сортиране чрез вмъкване с намаляваща стъпка - алгоритъм на Шел
сортиране чрез пряка размяна - метода на мехурчето;
сортиране чрез клатене
бързо сортиране на Хоор
метод на "зайците и костенурките”
сортиране чрез пряка селекция - пряк избор
пирамидално сортиране на Уйлямс
сортиране чрез трансформация
сортиране чрез множество
сортиране чрез броене
метод на бройните система
сортиране чрез пермутация
паралелно сортиране
сортиране чрез сливане MergeSort - прилагане на метода Разделяй и владей.

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

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

   Тук се разглежда обратната задача: имаме N броя цели числа, за които заделяме по-голям обем памет от необходимата. Описваният алгоритъм за сортиране е с линейна сложност, но в замяна изисква допълнителна памет.
   Следващата примерна програма използва едномерен масив с M елемента и работи с цели числа от интервала [0..N], където N<M. Броят на числата е P>=M>=N.
   Преди началото на въвеждане новите случайни числа се извършва индексиране на целия масив - всички стойности стават равни на 0. Генерират се P броя случайни числа, които може и да се повтарят.
   В масив в клетка с номер = новото число се добавя 1. При извеждане съдържанието на масива се извеждат толкова пъти индекса на тази клетка, колкото броя такива числа са били въведени в началния масив.

  Следва примерна програма даваща решена задача използваща описания азлгоритъм за сортиране на елементи в масив:

#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; 

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

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

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