Limbajul PHP. Ordonarea unui sir numeric cu un algoritm "ineficient"

Codul urmator implementeaza probabil cel mai trivial algoritm de sortare, bazat pe urmatoarele consideratii.

1) Fie cel mai defavorabil caz al unui sir pentru care se doreste ordonarea crescatoare, adica, presupunand ca este vorba de un sir de 4 numere intregi,

$i = array(4, 3, 2, 1);

2) Ne propunem ca pentru $k = 0, $k < 4, pentru fiecare situatie $i[$k] >= $i[$k + 1] sa inversam valorile celor doua elemente, folosind in acest scop variabila intermediara $temp:

$temp = $i[$k]; $i[$k] = $i[$k + 1]; $[k + 1] = $temp;

3) Initial suntem in situatia:

index:   0          1          2          3

val:       4          3          2          1

k = 0     4          3          2          1

inversare

k = 1     3         4          2          1

inversare

k = 2     3         2          4          1

inversare

k = 3     3         2          1          4

Am incheiat astfel, dupa trei inversari, o prima parcurgere completa a sirului $i si constatam imediat ca mai sunt necesare inca doua parcurgeri:

            2          1          3          4  (a 2-a parcurgere)

            1          2          3          4  (a 3-a parcurgere)           

Putem trage concluzia ca pentru un tablou cu un numar n oarecare de elemente valori numerice, sunt necesare n - 1 parcugeri ale tabloului in vederea ordonarii cu o functie precum cea descrisa mai sus. 

Desigur, algoritmul este ineficient pentru ca indiferent de pozitia initiala a elementelor el va itera de (n - 1) x (n - 1) ori (parcurgeri complete ale tabloui x iteratii in vederea stabilirii si corectarii relatiei de ordine).

De pilda, pentru sirul {1, 2, 3, 4, 5, 6} se vor efectua 5 x 5 = 25 de iteratii inutile, sirul fiind deja ordonatJ 

Metoda bubble sort corecteaza partial aceasta ineficienta, setand o variabila de test care ramane nemodificata daca o parcurgere completa a sirului nu detecteaza elemente inversate (dar se modifica in caz contrar).

Script-ul PHP pentru rulare in consola + print-screenul

<?php

// Problema ordonarii. Codul citeste elementele unui tablou de dimensiune specificata dupa care

// ordoneaza tabloul si il afiseaza

echo "\nIntroduceti dimensiunea tabloului:";

$dim = trim(fgets(STDIN));

$tab = array();

$i = 0;

// tabloul va fi populat cu elemente ale caror chei sunt intregi ordonati

echo "\nPopulati tabloul cu cele ".$dim." elemente.\n";

while($i < $dim)

{

            echo "Elementul ".$i.":";

            $tab[$i] = trim(fgets(STDIN));

            $i++;

}

echo "\nAfisam tabloul introdus:\n";

foreach($tab as $val) echo "$val ";

function Ordonare(array &$a, $k) // primul parametru transmis prin referinta

{

                        if($a[$k + 1] < $a[$k])

                        {

                                    $temp = $a[$k];

                                    $a[$k] = $a[$k + 1];

                                    $a[$k + 1] = $temp;

                        }

                       

}

$count = 0;

for($j = 0; $j < $i - 1; $j++)

            for($m = 0; $m < $i - 1; $m++)

            {

                        Ordonare($tab, $m);

                        $count++;

            }

echo "\nAfisam tabloul ordonat:\n";

foreach($tab as $val) echo "$val ";

echo "\nS-au efectuat ".$count." iteratii.";

?>