Clasa a V-a lecția 6 S22

Metode de sortare

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

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

Interclasare vectori (merge)

Se dau două şiruri a şi b, cu n, respectiv m elemente, numere naturale, ordonate crescător. Să se construiască un al treilea şir, c, care să conţină, în ordine crescătoare, elementele din şirurile a şi b.

O soluție ar fi să copiem toate elementele în cel de-al treilea vector și apoi să îl ordonăm. Există însă o soluție mai bună, bazată pe faptul că vectorii sînt deja ordonați. Să observăm că primul element din vectorul final este minimul dintre primele elemente din vectorii inițiali. Îl putem deci copia și apoi îl eliminăm din vectorul din care face parte. Apoi reluăm procedura. La un moment dat unul din vectori se va goli. În acel moment copiem ceea ce a rămas din vectorul nevid. Vom folosi trei indici i, j și k care vor avansa în vectorii corespunzători, pe măsură ce selectăm elemente. Iată soluția:

#include <stdio.h>

int a[100000], b[100000], c[200000];

int main(){
    int i, j, k, n1, n2;
    FILE *fin = fopen( "interclasare.in", "r" );
    FILE *fout = fopen( "interclasare.out", "w" );

    fscanf( fin, "%d", &n1 );
    for( i = 0; i < n1; i++ )
        fscanf(fin, "%d", &a[i]);
    
    fscanf(fin, "%d", &n2);
    for( i = 0; i < n2; i++ )
        fscanf(fin, "%d", &b[i]);

    i = j = k = 0;
    while( i < n1 && j < n2 ){      // cate vreme mai avem elemente in ambii vectori
        if( a[i] < b[j] )           // daca in a avem elementul mai mic
            c[k++] = a[i++];        // il copiem in vectorul c; avansam in vectorul a si in vectorul c
        else                        // altfel b are elementul cel mai mic
            c[k++] = b[j++];        // il copiem in vectorul c; avansam in vectorul b si in vectorul c

    }
    // in acest moment unul din vectorii a, b este sigur vid,
    while ( i < n1 )                // incercam sa copiem elementele ramase in a, daca exista
        c[k++] = a[i++];

    while ( j < n2 )                // incercam sa copiem elementele ramase in b, daca exista
        c[k++] = b[j++];

    for( i = 0; i < k; i++ ){       // k va fi n1 + n2
        fprintf ( fout, "%d ",  c[i] );        
    }
    fclose( fin );
    fclose( fout );
    return 0;
}

Temă

• Tema din pbinfo - S22
• arme dată la OJI 2012 clasa a 7^a ca aplicație a sortării prin selecție