Algoritm Renditje - QuickSort

[ReniX]

Quicksort - Java



Quicksort eshte nje algoritem per renditje rikorsiv qe nuk perdor memorie shtes, si mergesort (do e shpjegojme temen tjeter) ai perdor tekniken "divide et impera" (nda dhe pushto, e pedour nga romaket). Ai zgjedh nje element (pivot) dhe i ndan elementet e tjere duke vendosur nga e majta ata me te vegjelit dhe nga e djathta ata me te medhenjte dhe me pas ben krahasime dhe zevendesime.
Quicksort eshte shume i thjeshte per tu implementuar por nqs do te benim ndonje ndryshim ka mundesi qe ai te behet teper i veshtire duke na prishur pune. Kompleksiteti në rastin mesatar është nlog , por ne rastin me te keq ai ngrihet ne katror.


Pseudokodi quicksort anglisht:

function quicksort(array) 
     var list less, greater 
     if length(array) ≤ 1   
         return array   
     select and remove a pivot value pivot from array 
     for each x in array 
         if x ≤ pivot then append x to less 
         else append x to greater 
     return concatenate(quicksort(less), pivot, quicksort(greater))  

Ketu keni nje shembull te implementuar ne Java te Quicksort:

// Vini re: per nisjen fin duhet te jete i barabarte me v.length-1 
public void QuickSort( int [] v , int in , int fin ){ 
        if( fin<=in )return; 
            int pos=ndarje( v,in,fin ); 
            QuickSort( v,in,pos-1 );  //Ndarja e majte 
            QuickSort( v,pos+1,fin ); //Ndarja e djathte 
    } 
  
public int ndarje( int[]v , int in , int fin ){ 
      // Elementi pivot eshte i pari (pozcioni 0) 
        int i=in+1,j=fin; 
        while( i<=j ){ 
            while( (i<=fin) && (v[i]<=v[fin]) ) i++; 
                while( v[j]>v[in] ) j--; 
                if( i<=j ){ 
                      // Ndrysho 
                    int t=v[i]; 
                    v[i]=v[j]; 
                    v[j]=t; 
                } 
        } 
          // Ndrysho 
        int tt=v[in]; 
        v[in]=v[i-1]; 
        v[i-1]=tt; 
  
        return i-1; 
    }  

per Lirenti.com 2009, ReniX
Imazhi dhe nje pjese e algoritmint nga wikipedia

[kristimcs]

nk mora vesh gje..per cfare sherben kjo?