Metoda “Divide et impera”Algoritmul de sortare quicksort

I. Descrierea metodei.Metoda “Divide et impera” (desparte şi stăpâneşte) este o metodă generală de elaborare a algoritmilor. Ea constă

în împărţirea repetată a unei probleme de dimensiune mare în două sau mai multe subprobleme de acelaşi tip, urmată de combinarea soluţiilor subproblemelor rezolvate pentru a obţine soluţia problemei iniţiale.

Utilizând aceasta tehnica dorim să rezolvam următoarea problema:

Fiind dat un vector cu elementele in ordine oarecare, să se ordoneze elementele vectorului a in

ordine crescătoare (descrescătoare).

Vom face mai intai o generalizare a problemei a.i. vom obtine urmatoarea problema: fiind data o secventa de sir

cu elementele in ordine oarecare, se cere sa se ordoneze aceasta secventa in ordine crescatoare

(descrescatoare). Mai mult, presupunem că pentru orice p, q numere naturale cu există k astfel încât şi

prelucrarea secvenţei se poate face prelucrând secvenţele şi şi apoi combinând

rezultatele pentru a obţine prelucrarea dorită a întregii secvenţe .

Algoritmul recursiv, general divide et impera de prelucrare a secventei a[p…q] este următorul:

DIV_IMP( p, q; r) unde:- p – indică începutul secvenţei ce trebuie prelucrată;- q – indică sfârşitul secvenţei ce trebuie prelucrată;- r – indică rezultatul prelucrării.Algoritmul se va apela prin DIV_IMP(1, n; r).

DIV_IMP(p, q; r)daca q – p+1 EPS atunci

// q – p +1 numărul de elemente al secvenţei a[p…q]// EPS este dimensiunea la care problema se poate rezolva prin // calcule elementare

SORT(p, q; r)altfel

DIV(p, q; k)DIV_IMP(p, k; )

DIV_IMP(k+1, q; )

COMB( , ; r )sf. daca

sf algoritm

În algoritmul anterior sau folosit notaţiile:

EPS – reprezintă lungimea maxima a unei secvenţe , notată prescurtat a[p...q], pentru care

sortarea se poate face direct, fără a mai fi necesară împărţirea în subprobleme; Procedura SORT – realizează sortarea secvenţelor de acest tip furnizând rezultatul în r. Procedura DIV – determină subsecvenţele a[p…k] şi a[k+1…q] în care se împarte secvenţa a[p…q] şi

furnizează pe k. Procedura COMB – realizează combinarea rezultatelor şi ale prelucrării a două secvenţe vecine a[p…

k] şi a[k+1…q], obţinând rezultatul al prelucrării secvenţei a[p…q].

Observaţie:In cazul algoritmilor de tip divide et impera se urmareste atingerea unuia dintre urmatoarele obiective:

I. Realizarea prin operatii foarte simple a divizarii problemei ceea ce duce la algoritmi mai complecsi de combinare a solutiilor subproblemelor

o Ex:

In cazul algoritmului de sortare prin interclasare algoritmul de divizare era

Pentru combinarea solutiilor se folosea functia de interclasare – ceva mai complexa

II. Sau, realizarea prin operatii mai complexe a divizarii problemei in subprobleme, in schimb, combinarea solutiilor fiind foarte simpla

Algoritmul de sortare rapida quicksort va utiliza cea de a doua strategie.Mai exact, ideea algoritmului este urmatoarea: se alege un element oarecare x din secventa a[p..q], pe care il

vom numi pivot si vom determina o pozitie k care va fi chiar pozitia finala a lui x in sirul a[p..q] sortat, i.e:

In algoritmul urmator, in sirul a[p..q] vom alege ca pivot elementul x = ap

Gasirea pozitiei k de partitionare a secventei a[p..q] se face prin interschimbari repetate care mentin invariante proprietati asemanatoare celei de mai sus.

Se considera doua variabile de tip indice: i cu care se parcurge sirul a[p..q] de la stanga la dreapta si j cu care se parcurge sirul a[p..q] de la dreapta spre stanga.

Initial: i = p+1 j = q

Proprietatile mentinute invariante in timpul procesului de partitionare sunt urmatoarele:

(I1)

(I2)

Pentru aceasta, va trebui sa mutam toate elementele mai mici decat x in stanga sa si toate elementele mai mari decat x in dreapta sa.

Daca in momentul curent sunt procesate elementele a[i], respectiv a[j] cu i<=j, distingem urmatoarele cazuri:

a[i] x, in acest caz inaintam cu indicele din stanga spre dreapta: i++, deci este mentinuta invarianta

proprietatea (I1)

a[j] x, in acest caz inaintam cu indicele din dreapta spre stanga: j--, deci este mentinuta invarianta

proprietatea (I2)

a[i] > x > a[j]. Daca se realizeaza interschimbarea a[i] a[j] si apoi se face inaintarea de la st. spre dr. i++,

respectiv de la dr. spre st. j--, atunci sunt mentinute invariante proprietatile (I1), (I2)

Operatiile de mai sus sunt repetate cat timp i<j, adica, cat timp subsirul a[i..j] mai contine elemente ce inca nu au fost pozitionate relativ la elementul pivot x.

Considerand k = i-1 si interschimband a[i] cu a[p]=x vom obtine partitionarea dorita a vectorului a[p..q].

Dupa pozitionarea lui a[p] pe pozitia sa finala k astfel incat toate numerele mai mici sunt plasate in stanga sa si toate numerele mai mari in dreapta sa rezulta ca pentru a sorta intreg sirul a[p..q], mai ramane sa sortam recursiv subsirurile a[p..k-1] si a[k+1..q] apoi prin combinarea solutiilor (a[p..k-1] sortat) @ a[k] @ (a[k+1..q] sortat) vom obtine sirul initial sortat.

Se observa ca nu mai este necesara combinarea solutiilor deoarece dupa rezolvarea problemelor a[p..k-1] si a[k+1..q] avem:

Observatie: Daca sirul a[p..q]contine un singur element i.e. p=q, atunci nu mai este necesara o partitionare a problemei sirul

fiind gata sortat Daca sirul a[p..q] contine doua elemente, atunci unul dintre ele va fi ales pivot iar cel de al doilea trebuie

pozitinat relativ la elementul pivot apoi trebuie sortat sirul format din elementul ce nu este pivot In concluzie, EPS va avea valoarea 1 i.e. q=p

deci, algoritmul de sortare prin divide et impera poate fi rescris astfel:

qsort(p, q; r)//daca p=q sirul este sortat deci nu mai avem ce sorta

daca p q atunci

// secventa a[p…q] contine cel putin doua elemente//alegem a[p] ca pivot

x = a[p]//determina poziţia k, pentru divizarea secvenţei a[p…q]//in secvenţele a[p…k-1] si a[k+1…q] cu proprietatea:

i = p+1j = q

cat timp i j executa

daca a[i] x atunci i++

daca x a[j] atunci j—

daca i<j si a[i]>x si a[j]<x atunci

a[i] a[j]

i++j—

sf. dacasf. cat timp

k=i-1

a[k] a[p]

//sortează recursiv secvenţa a[p…k-1]qsort(p, k-1; )

//sortează recursiv secvenţa a[k+1…q]qsort(k+1, q; )

//combinrea soluţiilor obţinute prin sortarea secvenţelor a[p…k-1], a[k+1…q] nu mai //este necesara

sf. dacasf algoritm

Exemplu

Programul C/C++#include <iostream.h>

void afisareSir(int a[], int n){

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

cout<<a[i]<<" ";}

void qsort(int a[100], int p, int q){

int k;

if(q > p) //q-p+1 este numarul de elemente ale sirului{

//sirul a contine mai mult de un element//problema prea complexa//divizarea problemei in doua probleme identice//determinam pozitia k pentru divizarea sirului a in subsirurile a[p..k-1], a[k+1..q]int x = a[p];int i, j;int aux;

i = p+1;j = q;

while (i<=j){if (a[i] <= x) i++;if (x <= a[j] ) j--;if (i<j && a[i]>x && x>a[j]){

//interschimba a[i] cu a[j]aux = a[i];a[i] = a[j];a[j] = aux;i++;j--;

}}

k = i-1;//interschimba a[k] cu a[p]aux = a[k];a[k] = a[p];a[p] = aux;

qsort(a, p, k-1);qsort(a, k+1, q);

}}

void main(){

int n, i;int a[100]

//citire sircout<<endl<<"n=";cin>>n;

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

cout<<endl<<"a["<<i<<"]=";cin>>a[i];

}

//afisam sirul acout<<"\nSirul nesortat: ";afisareSir(a, n);qsort(a, 1, n);cout<<"\nSirul sortat: ";afisareSir(a, n);

}//main

Algoritmul qsort prezentat mai sus este optim peste clasa algoritmilor de sortare bazati pe comparatii. De aceea, in bibliotecile limbajului C/C++ exista o functie cu numele qsort care implementeaza algoritmul de sortare rapida quick sort.Ea se gaseste in <stdlib.h> si are urmatorul prototip:

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

unde: base este adresa vectorului ce va fi sortat num este numarul de elemente ale vectorului witdh este numarul de octeti ocupat de un element al vectorului compare este adresa functiei prin care se realizeaza compararea a doua elemente ale vectorului. Ea returneaza:

o 1 daca elem1 > elem2o 0 daca elem1 = elem2o -1 daca elem1 < elem2

Exemplu de utilizare:

#include <stdlib.h>#include <string.h>#include <iostream.h>

int comp( const void * e1, const void * e2 ){

//comparare de numere intregi

int v1 = *(int*)e1;int v2 = *(int*)e2;

if (v1 > v2)return 1;

else if (v1 ==v2)return 0;

else return -1;}

void main(){ int i;

int n=12; int x[100] = {1, 4, -2, -8, 7, 3, 5, 365, 346,46, 46, 4};

qsort( x, n, sizeof( int ), comp );

//sirul sortat for( i = 0; i < n; i++ )

cout<<x[i]<<" ";}