Clasa a 6-a lectia 25

From Algopedia
Revision as of 13:37, 5 April 2019 by Bella (talk | contribs) (Created page with "= Lectie = == Metode de sortare == === 1 Sortarea prin interschimbare directa === Se dă un vector de <tt>n</tt> elemente. Să se sorteze prin metoda interschimbarii directe....")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Lectie

Metode de sortare

1 Sortarea prin interschimbare directa

Se dă un vector de n elemente. Să se sorteze prin metoda interschimbarii directe. Metoda interschimbarii directe: Vom compara fiecare element v[i] cu toate elementele de la dreapta lor, si oridecate ori gasim un element mai mic ca acesta, vom interschimba valoarea din v[i] cu valoarea din v[j].

for ( i = 0; i < n - 1; i++ )  
  for ( j = i + 1; j < n; j++ )
    if ( v[i] > v[j] ) {         
      aux = v[i];
      v[i] = v[j];
      v[j] = aux;
    }
}

2 Metoda bulelor

Descrierea metodei: se parcurge vectorul și se compară fiecare element cu succesorul său. Dacă nu sunt în ordine cele două elemente se interschimbă între ele. Vectorul se parcurge de mai multe ori, până când la o parcurgere completă nu se mai execută nicio interschimbare între elemente (vectorul este sortat). Vom folosi o variabilă steguleţ pentru a marca faptul ca am efectuat o interschimbare, marcare care ne semnalează că incă vectorul nu a devenit sortat.

do {
ok = 1;                       // pp ca vectorul este sortat
for ( i = 0; i < n - 1; i++ ) // parcurgem toate perechile de elemente vecine si le comparam
    if ( v[i] > v[i+1] ) {    // daca am gasit un element mai mare decat vecinul sau din dreapta     
      aux = v[i];             // interschimbam cele doua valori vecine
      v[i] = v[i+1];
      v[i+1] = aux;
      ok = 1;                 // si marcam ca am facut o modificare, deci nu a fost sortat
    }
}while(!ok);                  // repetam parcurgerea cata vreme nu avem sortat vectorul
}

Optimizare: Cum metoda garanteaza ca la prima parcurgere, pe ultima pozitie va ajunge cel mai mare element, la urmatoarea parcurgere nu mai este necesar sa luam in calcul si acest element. De asemenea, la a doua parcurgere, avem garantia ca pe penultima pozitie va ajunge cel mai mare element din elementele ramase, deci la urmatoarea parcurgere nu il vom mai lua in calcul nici pe acesta. ca o generalizare, la o parcurgere p, vom avea de sortat doar n-p valori.

do {
ok = 1;                       // pp ca vectorul este sortat
p = 1;                        // numarul de parcurgerii vectorului curente
for ( i = 0; i < n - p; i++ ) // parcurgem toate perechile de elemente vecine si le comparam
    if ( v[i] > v[i+1] ) {    // daca am gasit un element mai mare decat vecinul sau din dreapta     
      aux = v[i];             // interschimbam cele doua valori vecine
      v[i] = v[i+1];
      v[i+1] = aux;
      ok = 1;                 // si marcam ca am facut o modificare, deci nu a fost sortat
    }
    p++;                      // trecem la urmatoarea parcurgere a vectorului
}while(!ok);                  // repetam parcurgerea cata vreme nu avem sortat vectorul
}

3 Sortarea prin selecție (select sort)

Se dă un vector de n elemente. Să se sorteze prin metoda selecției. Prin sortare înțelegem ordonare crescătoare a elementelor vectorului. Metoda selecției este următoarea: vom găsi maximul din vector, împreună cu poziția sa. Apoi vom interschimba maximul cu ultimul element din vector. Astfel ne vom asigura că ultimul element este chiar cel corect în vectorul ordonat. Ne-a rămas astfel un vector cu n-1 elemente, care trebuie sortat. Vom proceda la fel: vom găsi maximul în subvectorul de n-1 elemente, precum și poziția lui, și-l vom muta la coadă, rezultînd un vector de n-2 elemente. Continuăm procedura pînă ce vectorul este sortat.

Iată o exemplificare grafică:

9 2 8 3 6 5 3 9 6 |
6 2 8 3 6 5 3 9 | 9
6 2 8 3 6 5 3 | 9 9
6 2 3 3 6 5 | 8 9 9
5 2 3 3 6 | 6 8 9 9
5 2 3 3 | 6 6 8 9 9
3 2 3 | 5 6 6 8 9 9
3 2 | 3 5 6 6 8 9 9
2 | 3 3 5 6 6 8 9 9
| 2 3 3 5 6 6 8 9 9

Iată programul:

// avem vectorul v de n elemente
for ( i = n – 1; i > 0; i-- ) {   // pozitia ultimului element din subvector
  max = v[0];
  p = 0;                          // p este poziția maximului
  for ( j = 1; j <= i; i++ )
    if ( v[j] > max ) {          // memoram noul maxim si pozitia lui
      max = v[j];
      p = j;
    }
  // interschimbam maximul de pe pozitia p cu ultimul element, pe pozitia i
  v[p] = v[u];
  v[u] = max;
}

O alta modalitate de a implementa aceasta metoda este de a cauta minimul si a-l aduce pe prima pozitie in vector.

for ( i = 0; i < n - 1; i++ ){
    min = div[i]; p = i;
    for ( j = i + 1; j < n; j++ )
      if ( min > v[j]  ){
        max = v[j];
        p = j;
    }
    v[p] = v[i];
    v[i] = max;
  }

Vă recomand folosirea algoritmului de sortare prin selecție și nu a sortării cu bule, deoarece face mai puține operații. În practică el este de cinci pînă la zece ori mai rapid. Desigur, și mai rapidă este sortarea prin vectori de frecvență, numită și sortare prin numărare, atunci cînd ea poate fi aplicată (cînd numerele sînt foarte mici).

4 Sortarea prin insertie

#include <iostream>

using namespace std;

#include <stdio.h>

int main(){
  int n, i, v[1000], x;

  // citim sirul de n elemente si le inseram in vector inainte de ultimul element mai mare ca el
  scanf( "%d", &n );

  for( i = 0; i < n; i++ ) {
    scanf( "%d", &x );         // citim elem de pe pozitia i, deci pana acum am pus elem pana la i-1
    int p = i - 1;             // pornim de la ultimul element adaugat in vector
    while(p >= 0 && v[p] > x ) // cata vreme elementul curent e mai mare decat x
        v[p + 1] = v[p], p --; // il mut la dreapta
    v[p + 1] = x;              // acum a[p] e mai mic sau egal cu x, si a[p+1] e liber
  }

  for( i = 0; i < n; i++ )
    printf( "%d ", v[i] );

  return 0;
}

5 Sortarea prin numarare

Acest tip de sortare l-am folosit cand am studiat vectorii caracteristi ( de frecventa )

5 Sortarea rapida - Quicksort

Algoritmul acestui tip de sortare va fi studiat in clasa a 10-a. Putem sorta rapid insa folosing functia predefinita din biblioteca algorithm care are complexitate O( n log n)

#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
  int n, i, j, v[1000], aux;

  // citim sirul de n elemente si  memoram valorile sale in vectorul v
  scanf( "%d", &n );
  for( i = 0; i < n; i++ )
    scanf( "%d", &v[i] );

  sort( v, v + n );
  for( i = 0; i < n; i++ )
    printf( "%d ", v[i] );

  return 0;
}

Aplicatii

Implementare sortare prin interschimbare

Ordonare

- sortare crescatoare Se dă un sir cu n(1 ≤ n ≤ 1000) elemente numere naturale xi < 1.000.000.000. Să se ordoneze crescător elementele vectorului. - sortare descrescatoare ( impllemntati probleme Sortare )

// Metoda interschimbarii directe - complexitate O(n^2)
// Fiecare element v[i] va fi comparat cu elementele din dreapta v[j].
// Daca v[j] e mai mic, interschimbam valorile de pe cele doua pozitii i si j
#include <stdio.h>

int main(){
  int n, i, j, v[1000], aux;
  
  // citim sirul de n elemente si  memoram valorile sale in vecotrul v
  scanf( "%d", &n );
  for( i = 0; i < n; i++ )
    scanf( "%d", &v[i] );
  
  // sortam elementele 
  for ( i = 0; i < n - 1; i++ )
      for ( j = i + 1; j < n; j++ )
        if ( v[i] > v[j] ) {
          aux = v[i];
          v[i] = v[j];
          v[j] = aux;
        }

  for( i = 0; i < n; i++ )
    printf( "%d ", v[i] );

  return 0;
}

halfsort

Să se scrie un program care ordonează crescător elementele din prima jumătate a unui vector și descrescător elementele din a doua jumătate.

#include <stdio.h>
#include <stdlib.h>

int v[100];

int main(){
  FILE *fin = fopen( "halfsort.in", "r" );
  FILE *fout = fopen( "halfsort.out", "w" );
  int n, i, j, aux;
  fscanf(fin, "%d", &n);

  for( i = 0; i < n; i++ )
      fscanf( fin, "%d", &v[i] );

  // sortam crescator elem din prima jumatate
  for( i = 0; i < n / 2; i ++ )
    for(j = i + 1; j < n / 2; j ++ )
      if( v[i] > v[j] ){
        aux = v[i];
        v[i] = v[j];
        v[j] = aux;
      }
  // sortam descrescator elem din a doua jumatate
  for( i = n / 2; i < n; i ++ )
    for( j = i + 1; j < n; j ++ )
      if( v[i] < v[j] ){
        aux = v[i];
        v[i] = v[j];
        v[j] = aux;
      }

  for( i = 0; i < n; i++ )
    fprintf( fout, "%d ", v[i] );
  fclose( fin );
  fclose( fout );
  return 0;
}

Alternativa mai rapida de sortare :

#include<cstdio>
#include<algorithm>
using namespace std;
int v[102];
int cmp(int a, int b){
    return a > b;
}
int main() {
	FILE *fin, *fout;
	int n, i, j, aux;

    fin = fopen("halfsort.in", "r");
    fout = fopen("halfsort.out", "w");
    fscanf(fin, "%d", &n );
    for (i = 0; i < n; i++)
       fscanf( fin, "%d", &v[i] );
    sort(v , v + n / 2 );
    sort(v + n / 2 , v + n, cmp );

    for (i = 0; i < n; i++)
      fprintf(fout, "%d ", v[i]);
	fclose(fin);
	fclose(fout);
	return 0;
}

Implementare Select Sort

Arhitectura

Se citesc n numere naturale reprezentând înălțimile a n clădiri. Cerința problemei este de a realiza un proiect de arhitectură în care clădirile sunt ordonate descrescător după înălțimea lor.

#include <stdio.h>
int v[1000];
int main()
{
    int i, n, p, max, j;
    scanf ( "%d", &n );
    for ( i = 0; i < n; i ++ ) {
       scanf ( "%d", &v[i] );
    }
    for ( i = 0; i < n - 1; i ++ ){
       max = 0;
       for ( j = i; j < n; j ++ ){;
          if ( max < v[j] ){
            max = v[j];
            p = j;
          }
       }
       v[p] = v[i];
       v[i] = max;
    }
    for ( i = 0; i < n; i ++ )
      printf ( "%d ", v[i] );
    return 0;
}

Sortare Divizori

// Metoda de sortare select sort + numarare divizori folosind descompunerea in factori primi

#include <stdio.h>

int main(){
  int n, i, j, v[1000], div[1000], aux, nrdiv, d ;
  FILE *fin = fopen( "sortare_divizori.in", "r" );
	FILE *fout = fopen ( "sortare_divizori.out", "w" );

  fscanf( fin,"%d", &n );
  for( i = 0; i < n; i++ ){
    fscanf( fin, "%d", & v[i] );
    nrdiv = 1;
    d = 2;
    int x = v[i], p;
    while ( d * d <= x ){
      p = 0;
      while ( x % d == 0 ){
        x = x / d;
        p ++;
      }
      nrdiv *= ( p + 1 );
      d ++;
    }
    if ( x > 1 )
      nrdiv *= 2;
    div[i] = nrdiv;
  }

  // sortam elementele dupa nr de divizori in ordine crescatoare
  int poz, max;
  for ( i = 0; i < n - 1; i++ ){
    max = div[i]; poz = i;
    for ( j = i + 1; j < n; j++ )
      if ( max < div[j] || ( max == div[j] && v[poz] > v[j]) ){
        max = div[j];
        poz = j;
    }
    aux = v[poz];
    v[poz] = v[i];
    v[i] = aux;
    div[poz] = div[i];
    div[i] = max;
  }
  // afisam vectorul sortat
  for( i = 0; i < n; i++ )
    fprintf( fout, "%d ", v[i] );

  return 0;
}

Sortarea prin numarare

Aplicatie: arhitectura 2 Pentru aceasta problema am ales sortarea prin vector de frecventa deoarece, daca am sorta toate de le n = 2 milioane de elemente folosind algoritmii invatati, am avea o complexitate O(n*n) ceea ce ar conduce la depasirea timpului cerut de exectutie.

// Sortare prin numarare ( folosim vector de frecventa )
#include <stdio.h>
#include <stdlib.h>

int v[100001];	  // val maxima este 100000
int a[2000002];   // 2mil de elemente + 2 pseudocladiri ( santinele )
int main(){
    FILE *fin , *fout;
    fin = fopen ( "arhitectura2.in", "r" );
    fout = fopen ( "arhitectura2.out", "w" );
    int n, k, i, nr;
    
    // construim un vector de frecventa pentru a sorta cele n valori
    fscanf ( fin , "%d", &n );
    for ( i = 0; i < n; i++ ){
        fscanf ( fin , "%d", &nr );
        v[nr] ++;
    }
    
    // parcurgem vectorul de frecventa si reconstruim sirul de n valori, in ordine descrescatoare
    k = 0;
    for ( i = 100000; i >= 0; i-- )
        while ( v[i] != 0 ){
            a[++k] = i;
            v[i]--;
            fprintf ( fout , "%d ", a[k] );            
        }        
    fprintf ( fout, "\n");
    
    // pentru fiecare element din sir verificam daca e media valorilor vecine
    a[0] = a[k+1] = 0;          // pseudocladirile : santinele
    for ( i = 1; i <= k; i++ ){
        if ( 2 * a[i] == a[ i - 1 ] + a[ i + 1 ]  )
            fprintf ( fout , "1 " );
        else
            fprintf ( fout , "0 " );
    }
    fclose ( fin );
    fclose ( fout );
    return 0;
}

Ca o alternativa mai rapid de implemntat in conditii de olimpiada aveti algormul de mai jos, cu complexitate apropiata de cea a algoritmului anterior, dar care intra in timp. Complexitatea fiin O( n log n ) data de complexitatea algoritmului rapid de sortare definit in biblioteca algorithm.

// Sol cu qsort -sort de biblioteca
#include<bits/stdc++.h>
using namespace std;
int v[2000003];
int cmp(int a, int b){
    return a>b;
}
int main(){
    ifstream fin("arhitectura2.in");
    ofstream fout("arhitectura2.out");
    int n;
    fin >> n;
    for(int i=1; i <= n; i++)
        fin >> v[i];
    sort(v+1, v+n+1, cmp);
    for(int i=1; i <= n; i++)
        fout << v[i] << " ";
    fout << '\n';
    for(int i=1; i <= n; i++){
        if(2*v[i]==v[i-1]+v[i+1])
            fout << "1 ";
        else fout << "0 ";
    }
}

Tema

Runda pbinfo

Optional

Probleme de studiu

  • iepurasi - Pancake sorting. Sortati conform indicatiilor, fara sa tineti cont ca se cere numarul minim de tap-uri.