Structuri de Date 2023

Structuri de Date

Laborator 4: Sortări

Laborator 4: Sortari

Sursa quicksort:

#include <iostream>#include <ctime>#include <cstdlib>
using namespace std;
int alege_poz_pivot(int* v, int st, int dr){                                                //cout<<" pivot="<<v[(st+dr)/2]<<" ";    return (st+dr)/2;}
int partition_Hoare(int* v, int st, int dr){    int pivot = v[alege_poz_pivot(v,st,dr)];    int i=st , j=dr;    while (1){        while (v[i]<pivot) i++;        while (v[j]>pivot) j--;        if (i>=j) return j;        swap(v[i],v[j]);        i++;        j--;    }}
int partition_Lomuto(int* v, int st, int dr){    int poz_pivot = alege_poz_pivot(v,st,dr);    swap(v[poz_pivot],v[dr]);    int i=st-1;                                                //for (int i=st;i<=dr;i++) cout<<v[i]<<" "; cout<<endl;    for (int j=st;j<dr;j++){        if (v[j]<v[dr])            {swap(v[++i],v[j]);                                                //for (int i=st;i<=dr;i++) cout<<v[i]<<" "; cout<<endl;            }    }    swap(v[i+1],v[dr]);                                                //for (int i=st;i<=dr;i++) cout<<v[i]<<" "; cout<<endl;    return i+1;}
void quicksort(int* v, int st, int dr, int nivel){    if (st<dr){
        int poz_pivot = partition_Lomuto(v,st,dr);

        quicksort(v,st,poz_pivot,nivel+1);        quicksort(v,poz_pivot+1,dr,nivel+1);
    }}
int partition(int v[], int st, int dr){    int poz_pivot = alege_poz_pivot(v,st,dr);    swap(v[poz_pivot],v[dr]);    int i = st;    for (int j = st; j <= dr - 1; j++) {        if (v[j] <= v[dr])            swap(v[i++], v[j]);    }    swap(v[i], v[dr]);    return i;}
int kth(int v[], int st, int dr, int k){    if (k > 0 && k <= dr - st + 1) {        int poz_pivot = partition(v, st, dr);        if (poz_pivot - st == k - 1)            return v[poz_pivot];        if (poz_pivot - st > k - 1)            return kth(v, st, poz_pivot - 1, k);        return kth(v, poz_pivot + 1, dr, k - poz_pivot + st - 1);    }    return -1;}
int is_sorted(int* v, int st, int dr){    for (int i=st;i<dr;i++)        if (v[i]>v[i+1])            return 0;    return 1;}
int main(){    srand(time(NULL));
    int n=13;    int v[n];
    for (int i=0;i<n;i++)        v[i]=rand()%25;
    for (int i=0;i<n;i++)        cout<<v[i]<<" ";    cout<<endl;    quicksort(v,0,n-1,0);    for (int i=0;i<n;i++)        cout<<v[i]<<" ";    cout<<(is_sorted(v,0,n-1)?"SORTAT":"!!!!NESORTAT")<<endl;
    for (int i=0;i<n;i++)        v[i]=rand()%155;    int k=1+rand()%(n-1);    int kvalue=kth(v,0,n-1,k);    quicksort(v,0,n-1,0);
    for (int i=0;i<n;i++)        cout<<v[i]<<" ";    cout<<endl;
    cout<<"v["<<k<<"]= ";    cout<<kvalue<<endl;
    if (kvalue==v[k-1])        cout<<"CORECT";    else        cout<<"INCORECT";
    return 0;}

Alegerea temei de laborator (link).

MAXIM ~3 STUDENTI PER SEMIGRUPA LA ACEEASI TEMA

🙂 Folosind (quicksort sau mergesort sau heapsort), implementati intersectia a doua multimi. Fiecare multime este un array de intregi, iar rezultatul este un array de intregi, continand elementele din intersectie. O(n log n + m log m) Hint: modificati o interclasare.
🙂 Folosind (quicksort sau mergesort sau heapsort), implementati diferenta a doua multimi. Fiecare multime este un array de intregi, iar rezultatul este un array de intregi, continand elementele din diferenta. O(n log n + m log m) Hint: modificati o interclasare.
🙂 Folosind (quicksort sau mergesort sau heapsort), implementati diferenta simetrica a doua multimi. Fiecare multime este un array de intregi, iar rezultatul este un array de intregi, continand elementele din diferenta simetrica. O(n log n + m log m) Hint: modificati o interclasare.
🙂 Folosind (quicksort sau mergesort sau heapsort), implementati reuniunea a doua multiseturi. Fiecare multiset este un array de perechi (element,aparitii), iar rezultatul este un array de perechi (element,aparitii), continand elementele din reuniune. O(n log n + m log m) Hint: modificati o interclasare. 4a 2b 7c ∪ 2a 4b 3c = 4a 4b 7c -> luam maximum
🙂 Folosind (quicksort sau mergesort sau heapsort), implementati intersectia a doua multiseturi. Fiecare multiset este un array de perechi (element,aparitii), iar rezultatul este un array de perechi (element,aparitii), continand elementele din intersectie. O(n log n + m log m) Hint: modificati o interclasare. 4a 2b 7c ∩ 2a 4b 3c = 2a 2b 3c -> luam minimum
🙂🔨👑 Folosind (quicksort sau mergesort sau heapsort), implementati diferenta a doua multiseturi. Fiecare multiset este un array de perechi (element,aparitii), iar rezultatul este un array de perechi (element,aparitii), continand elementele din diferenta. O(n log n + m log m) Hint: modificati o interclasare. 4a 2b 7c \ 2a 4b 3c = 2a 4c -> luam diferenta
🙂🔨👑 Folosind (quicksort sau mergesort sau heapsort), implementati diferenta simetrica a doua multiseturi. Fiecare multiset este un array de perechi (element,aparitii), iar rezultatul este un array de perechi (element,aparitii), continand elementele din diferenta simetrica. O(n log n + m log m) Hint: modificati o interclasare. 4a 2b 7c ∆ 2a 4b 3c = 2a 2b 4c -> (A\B)∪(B\A)

🙂🔨👑 Probleme pentru smecheri:

A. (3p) Implementati un quicksort care sorteaza partitii mai mici decat k(e.g. =10) folosind alta sortare nerecursiva (e.g. Insertion Sort).

B. (3p) Implementati RadixSort pe intregi fara semn in care radix-ul ales sa fie putere de doi, iar toate operatiile de impartire (adica / si %) sa fie inlocuite cu operatii corespunzatoare la nivel de biti (adica >> si &).

Propunere1: 4 treceri de Count Sort cu radix = 256, deci fiecare intreg are 4 "cifre" egale cu valoarea fiecarui octet.

frecv[256]x/256 = x>>8x%256 = x&255

Varianta2: 8 treceri, radix=16:

frecv[16]x/16 = x>>4x%16 = x&15