momente şi schiţe de informatică

Extinderea obiectului Array cu o metodă quickSort()

Creat: 2008/nov       Comentarii

Array | javaScript | qsort

Obiecte, proprietăţi, metode (în Javascript)

Un obiect are asociate proprietăţi şi metode; o proprietate a unui obiect poate fi accesată prin "operatorul punct": objectName.propertyName; se poate adăuga obiectului o proprietate, indicând un nume şi asignând o valoare: objectName.newPropertyName = value; analog se poate adăuga o nouă metodă (funcţie): objectName.myMethod = function() {...};. Pentru exemplu:

<script type="text/javascript">
    var x = Math.PI;         // proprietatea .PI a obiectului predefinit Math  
    alert ( Math.sin(x/6) ); // metoda .sin() a obiectului Math
    // extinde Math cu o metodă de calcul a secantei trigonometrice:      
    Math.secanta = function(t) { return 1 / Math.cos(t); };
    alert ( Math.secanta(x/3) ); 
</script>

Un obiect poate fi instanţiat în program folosind operatorul new: var unObArr = new Array(); obiectul creat astfel moşteneşte toate proprietăţile şi metodele obiectului din care a fost instanţiat prin new, precum şi pe cele ale prototipurilor acestuia. Există o proprietate (predefinită) care este comună tuturor obiectelor (exceptând Math), anume .prototype; aceasta serveşte în Javascript pentru extinderea obiectelor (pe parcursul execuţiei).

Când în program este referită o proprietate (dintr-un obiect existent), Javascript caută numele respectiv întâi între proprietăţile obiectului faţă de care este referită (prin obiect.propName); dacă numele respectiv nu este găsit aici, atunci Javascript îl caută între proprietăţile prototipurilor (şi ale prototipurilor prototipurilor, etc.) acelui obiect (analog în cazul unei metode a obiectului).

Tablouri în Javascript

În Javascript, tablourile sunt obiecte Array: conţin nu doar valorile propriu-zise (accesibile prin []), dar şi diverse proprietăţi şi metode (accesibile prin "operatorul de selecţie" .); de exemplu:

var unArr = new Array();  // altă posibilitate: var unArr = [];
unArr[0] = 123;
unArr.push(5, 6, 7);  // invocă metoda .push() adăugând alte elemente
unArr[5] = "un şir ..."; // unArr[4] are valoarea "undefined"
unArr.flag = true;  // adaugă proprietatea '.flag' (cu valoarea 'true')
alert(unArr + '\nLungimea tabloului: ' + unArr.length);

Executând acest script, se verifică faptul că un Array poate conţine valori de diverse tipuri (numere, întregi sau nu; şiruri de caractere; valori undefined; etc.); nu este necesar să se precizeze numărul de elemente (valoarea fiind menţinută intern în proprietatea .length a obiectului).
O metodă obişnuită pentru "executare" decurge astfel: se creează un fişier text cu extensia .html; se înscrie tagul <script>; apoi se pastează scriptul de executat (exemplul de mai sus) şi se adaugă tagul </script>; se salvează, apoi se deschide acest fişier din browser.

Pe lângă metodele predefinite (.push(), .pop(), .join() etc.; vezi Core Javascript 1.5) - pot fi adăugate unui obiect Array şi metode noi:

    var unArr = [ 1, 2, 3, 'foo', 'bar', 3.1415 ]; 
    unArr.print = function() { 
               alert( this.join(' / ') + '\nlungime: ' + this.length ); 
    };
    unArr.print();
    var altArr = [1,2,3,4,5,6,7,8,9];
    altArr.print();  // print() nu este vizibilă şi din altArr

Astfel mai sus, am adăugat obiectului unArr metoda .print(); aceasta nu este însă accesibilă şi din obiectul altArr, creat ulterior. Pentru ca metoda să fie vizibilă şi altora dintre obiectele Array, ea trebuie definită pentru însuşi obiectul Array, folosind prototype:

    Array.prototype.print = function() { 
        alert(this.join(' / ') + '\nlungime: ' + this.length); 
    };
    var unArr = [ 1, 2, 3, 'foo', 'bar']; 
    unArr.print();
    [1,2,3,4,5,6,7,8,9].print();    

Să precizăm că this este o referinţă la însuşi obiectul pentru care se va invoca metoda (în cazul de faţă la unArr şi respectiv la tabloul anonim [1,2,..., 9]).

Metoda sort şi… q_sort (?)

Obiectul Array are metoda nativă sort():

  ["Foo", "Bar", "bar", "Baz"].sort()
    // va produce tabloul ordonat lexicografic ["Bar", "Baz", "Foo", "bar"]
  [30, 7, 300, 31].sort()
    // produce tabloul ordonat lexicografic [30, 300, 31, 7]
  [30, 7, 300, 31].sort( function(a,b) { return a - b; } )
    // va produce tabloul ordonat numeric [7, 30, 31, 300]

În ultimul exemplu, metodei sort() i s-a transmis ca parametru o funcţie de comparare a elementelor; fiindcă a — b nu se poate interpreta altfel decât ca "scădere a două numere", elementele tabloului sunt considerate ca numere (încât se abandonează ordonarea implicită - cea lexicografică). În Javascript, funcţiile sunt şi ele nişte obiecte - putând fi utilizate la fel ca oricare variabile (inclusiv ca parametri pentru alte funcţii: mai sus, funcţia sort() a primit ca parametru o funcţie de comparare).

Intenţia noastră aici ar fi aceea de a extinde Array cu o metodă de sortare bazată pe "QuickSort"; dar trebuie să observăm că o asemenea "extindere" ar putea avea doar raţiuni didactice… De exemplu, căutând la code.google.com/p/v8 putem vedea că de fapt sort este implementată folosind şi "QuickSort" (cel puţin, pentru browserul Chrome). Putem adăuga totuşi o metodă .q_sort (transcriind în fond un program prezentat în multe manuale de C) astfel:

Array.prototype.q_sort = function (beg, end) {
    var at_beg = beg;
    var at_end = end;
    var pivot = this[beg];
    while (beg < end) {
        while ((this[end] >= pivot) && (beg < end)) 
            end--; 
        if (beg != end) 
            this[beg++] = this[end];
        while ((this[beg] <= pivot) && (beg < end)) 
            beg++;
        if (beg != end) 
            this[end--] = this[beg];
    }
    this[beg] = pivot;
    if (at_beg < beg) this.q_sort(at_beg, beg - 1);
    if (at_end > beg) this.q_sort(beg + 1, at_end);
}

Pentru testare desigur, putem folosi de exemplu:

  var lista = ['Ionescu','Ababei','Popescu','Barbu'];
  lista.q_sort(0, lista.length - 1);
  alert(lista); // numele, în ordine alfabetică
  var listn = new Array();
  for(var i=0; i< 100; i++) listn[i] = Math.round(100*Math.random());
  listn.q_sort(0, listn.length - 1);
  alert(listn); // numerele, ordonate crescător

q_sort ordonează corect şi numerele, fără să implicăm o funcţie de comparare ca în cazul metodei native sort; dar acest fapt nu-i neapărat un avantaj: implicarea unei funcţii de comparare a elementelor creează posibilitatea de a folosi sort şi pe tablouri mai complicate, de exemplu având drept elemente alte tablouri. Şirurile de caractere sunt ordonate corect (lexicografic), dar numai dacă e vorba de caractere ASCII standard - altfel (ca şi în cazul sort) este necesară implicarea unei funcţii de comparare.

Trebuie să subliniem că adăugarea unei noi metode la un obiect predefinit trebuie făcută cu prudenţă şi numai dacă într-adevăr este nevoie; nu are rost - decât cel mult "didactic", ca în cazul de aici - să adaugi o metodă (precum q_sort-ul nostru) care de fapt se cam suprapune peste una existentă (peste sort, în cazul de faţă).

Media Dinamică

Articolul 50

Drumuri

ŞahStartTemp

25
32
17
4
19
34
14
3
26
33
16
5
31
24
15
18
35
20
2
13
27
6
9
23
30
11
8
21
28
12
22
29
10
7

Ambiţiile Cavalerului

Localităţi

Judeţ:

Constituirea unei baze de date colectând cu Python de pe web

Bliţuri

Load another random Bliţ

//slightchess

Decoraţiuni hiperbolice

SALARII 2017, 2018

//bacMath
variante BAC matematică

Bacalaureat 2015 -
de la forma microsoftizată, la R

modelare ŞAH, I-XX
construcţia unui PGN-browser()

Linux şi aplicaţii Web
în 24 de ore

Orar şcolar - exemplu
după un orar generat de "aSc Orare"

Orar Adjust
ajustează orarul şcolar