Ministerul Educației Naționale
Colegiul Național ”Petru Rareș”

Metode de sortare

Indrumador:
Prof. Marius Ududec
Absolvent,
Iascu Andrei

Introducere

Motivarea alegerii temei:

Am ales tema ”Metode de sortare” deoarece cunoașterea unor algoritmi de sortare este esențiala in programare, dar și in viața reală, fiind de mare ajutor in construirea și modificarea bazelor de date. De asemenea,este necesar și cunoașterea unor criterii de clasificare care indica metoda de sortare ideala pentru problema în cauză.

 

Descrierea Sortării

Se consideră un set finit de obiecte, fiecare având asociată o caracteristică, numită cheie, ce ia valori într-o mulțime pe care este definită o relație de ordine. Sortarea este procesul prin care elementele setului sunt rearanjate astfel încât cheile lor să se afle într-o anumită ordine.

Ex: Considerăm setul de valori întregi: (5,8,3,1,6). în acest caz cheia de sortare coincide cu valoarea elementului. Prin sortare crescătoare se obține setul (1,3,5,6,8) iar prin sortare descrescătoare se obține (8,6,5,3,1).

Sortarea este des folosită in lucrul cu liste. Un exemplu de folosire a sortării îl reprezintă motoarele de căutare web, care folosesc astfel de algoritmi (Google, Yahoo, MSN).

 

Metode de sortare

Stabilitate. O metodă de sortare este considerată stabilă dacă ordinea relativă a elementelor ce au aceeași valoare a cheii și nu se modifică în procesul de sortare.

Naturalețe. O metodă de sortare este considerată naturală dacă numărul de operații scade odată cu distanța dintre tabloul inițial și cel sortat. O măsură a acestei distanțe poate fi numărul de inversiuni al permutării corespunzătoare tabloului inițial.

Eficientă. O metodă este considerată eficientă dacă nu necesită un volum mare de resurse. Din punctul de vedere al spațiului de memorie o metodă de sortare pe loc este mai eficientă decât una bazată pe o zonă de manevră de dimensiunea tabloului. Din punct de vedere al timpului de execuție este important să fie efectuate cât mai puține operații. În general, în analiză se iau în considerare doar operațiile efectuate asupra elementelor tabloului (comparații și mutări). O metodă este considerată optimală dacă ordinul său de complexitate este cel mai mic din clasa de metode din care face parte.

Simplitate. O metodă este considerată simplă dacă este intuitivă si ușor de înțeles.

După cum bine știm, fiecare algoritm de sortare are nevoie de un anumit spațiu și un anumit timp pentru executarea algoritmului. Pentru măsurarea complexității vom folosi notația complexității „O(n)” (n reprezintă numărul de comparații ale algoritmului).

Cazul Mediu - situația in care probabilitatea duratei execuției algoritmului se apropie de media timpului de execuție al algoritmului respectiv.

Cazul defavorabil - situația in care timpul de execuție al algoritmului este cel mai ridicat.

Memorie folosită – memoria necesară sortării vectorului.

 
Tipuri de sortari
 

Bubble sort

Prin această metodă se parcurge vectorul şi se compară fiecare element cu succesorul său. Dacă cele două elemente nu sunt în ordine, ele se interschimbă. Vectorul se parcurge de mai multe ori, până când la o parcurgere completă nu se mai execută nicio interschimbare.
Se utilizează variabila sortat de tip int care se iniţializează cu valoarea 1 la începutul parcurgerii (se presupune că vectorul este sortat) şi, dacă în timpul parcurgerii se execută o interschimbare, variabilei sortat i se atribuie valoarea 0 (vectorul nu este sortat): Parcurgerea repetată a vectorului se termină atunci când, la sfârşitul unei parcurgeri, variabila sortat nu îşi modifică valoarea (îşi păstrează valoarea 1).

 

Algoritm

Subalgoritm  Metoda_bulelor (A)
1: k=n {k va fi limita superioara pana unde se interschimba elemente}
2: repeta
3:     ok = adevărat
4:     pentru i=1,k-1 execută
5:           dacă a[i] > a[i+1] atunci
6:                  ok = fals
7:                  aux = a[i]
8:                  a[i] = a[i+1]
9:                  a[i+1] = aux
10:                j=i  
11:    k=j;  {ultimul indice pentru care s-a facut interchimbare}
12: pana cand ok


Cazul mediu : O(N^2)

 Cazul defavorabil : O(N^2)

Memorie folosita : O(1)

Stabil : DA

 

Algoritmul de sortare prin metoda selectiei directe

Prin această metodă se aduce pe prima poziţie elementul cu valoarea

cea mai mică din cele n elemente ale vectorului, apoi se aduce pe poziţia a doua

elementul cu cea mai mică valoare din ultimele n-1 elemente ale vectorului, apoi se

aduce pe a treia poziţie elementul cu cea mai mica valoare din ultimele n-2 elemente

ale vectorului ş.a.d.m.

 

 

#include <iostream>

using namespace.std;
int v[25],n,i,j,aux;
int main()
{

cout<<„nr de elemente=”;

cin>>n;

for(i=0;i<n;i++)

{

cout<<„v[„<<i<<„]=”;

cin>>v[i];}

for(i=0;i<n;i++)

cout<<v[i]<<”  „;

for(i=0;i<n-1;i++)

  for(j=i+1;j<n;j++)

    if( v[i ]> v[j] )

     {

      aux=v[j];  v[j]=v[i]; v[i]=aux;

     }

cout<<endl;

for(i=0;i<n;i++)

cout<<v[i]<<” „;

}

 

Merge sort - interclasare

           In cazul sortarii prin interclasare vectorii care se interclaseaza sunt doua

secvente ordonate din acelasi vector.

            Sortarea prin interclasare utilizeaza metoda Divide et Impera:

 - se imparte vectorul in secvente din ce in ce mai mici., astfel incat fiecare secventa sa

fie ordonata la un moment dat si interclasata cu o alta secventa din vector

corespunzatoare.

            - practic interclasarea va incepe cand se ajunge la o secventa formata din doua

elemente.

           Aceasta odata ordonata se va interclasa cu o alta corespunzatoare. Cele doua

secvente vor alcatui in subsir ordonat din vector mai mare care la randul lui se va

interclasa cu subsirul corespunzator s.a.m.d.

Algoritm:

void mergesort(int left, int right) {

    if (left == right)

        return;

    int middle = (left + right) / 2;

    mergesort(left, middle);

    mergesort(middle + 1, right);

 

    //interclaseaza cele 2 siruri de la left la middle, si de la middle + 1 la right

    .....

    .....

}

 

Heap sort - selectie

Algoritmul HeapSort este cel mai slab algoritm de clasă O(N log2N) Este mai

slab (dar nu cu mult) decât algoritmii din familia QuickSort, dar are marele avantaj față

de aceștia că nu este recursiv. Algoritmii recursivi rulează rapid, dar consumă o mare

cantitate de memorie, ceea ce nu le permite să sorteze tablouri de dimensiuni oricât de mari HeapSort este un algoritm care "împăca" viteză cu consumul relativ mic de

memorie.

            Cazul mediu : O(N log N)

            Cazul defavorabil : O(N log N)

            Memorie folosita : O(1)

            Stabil : NU

Algoritm:

void swap(int a[],int i,int j)

{

 int aux = a[i];

 a[i] = a[j];

 a[j] = aux;

 

}

void downheap(int a[],int v,int n)

{

 int w = 2 * v + 1; // primul descendent al lui v

 while (w<n)

 {

 if (w+1<n) // mai exista unul?

 if (a[w+1]>a[w]) w++; //crescator

 // w este decendentul lui v

 if (a[v]>=a[w]) return; //crescator

 swap(a,v, w); // interschimbam v cu w

 v = w; // continuam

 w = 2 * v + 1;

 }

}

void heapsort(int a[],int n)

{

 for (int v = n/2-1; v >= 0; v--) //creem heap`ul

 downheap (a,v,n);

 while (n>1)

 {

 n--;

 swap(a,0, n);

 downheap (a,0,n);

 }

}

 

Quick sort - partionare

Quick Sorț este unul dintre cei mai rapizi și mai utilizați algoritmi de sortare până

în acest moment,bazându`se pe tehnică "divide et impera".Deși cazul cel mai

nefavorabil este O(N^2) ,în practică,QuickSort oferă rezultate mai bune decât restul

algoritmilor de sortare din clasă "O(N log N)".

            Cazul mediu : O(N log N)

            Cazul cel mai nefavorabil : O(N^2)

            Memorie folosita : O(log N)

Algoritm:

void qSort(int vector[],int st,int dr)

{

 int temp,min,max,mijl;

 

 mijl = vector[st+(dr-st)/2]; //luam mijlocul intervalului

 min = st; max = dr;

 do

 {

 while(vector[min] < mijl) min++;

 while(vector[max] > mijl) max--;

 if(min <= max) //interschimbare

 {

 temp = vector[min];

 vector[min++] = vector[max];

 vector[max--] = temp;

 }

 }while(min <= max); //la fiecare pas sortam "mai bine" intervalul st-dr

 //cand numai avem ce face schimbam intervalul

 if(st < max) qSort(vector,st,max); //crescator

 if(dr > min) qSort(vector,min,dr); //crescator

}

 
 

©2018 by Metode de sortare. Proudly created with Wix.com

This site was designed with the
.com
website builder. Create your website today.
Start Now