Quicksort algoritem @ Slo-Tech

Forum » Programiranje »
Quicksort algoritem

Quicksort algoritem

marjan_h :: 30. okt 2012, 12:07

Poskušam obrniti algoritem, da bi sortiral števila od največjega pa do najmanjšega in NE obratno kot deluje sedaj. Pa mi nekako ne uspeva. Zgleda da ne razumem dober kode, tam pri komentarju ne vem zakaj se preverja

i <= j

, in ne indeksa v tabeli tab.


    public static void quicksort(int tab[], int low, int high){
        int i = low, j = high;
        int pivot = tab[ (int) (i + j) / 2];
        
        while (i <= j){
            while (tab[i] < pivot)
                i++;
            
            while (tab[j] > pivot)
                j--;
            // tuki sem poskusal zamenjati predznak v >= pa ne deluje
            if (i <= j){
                int temp = tab[i];
                tab[i] = tab[j];
                tab[j] = temp;
                i++;
                j--;
            }
        }
        if (low < j){
            quicksort(tab,low, j);
        }
        if ( i < high){
            quicksort(tab,i,high);
        }
        
    }

Hvala za pomoč.

usoban :: 30. okt 2012, 12:33

saj i pa j sta indeksa v tabeli.

on povecuje i, dokler je element tab[i] manjsi od pivota
in zmanjsuje j, dokler je tab[j] vecji od pivota.
Ko to konca, ves da imas v tab[i] element, ki je manjsi od pivota, tab[j] pa vecji od pivota => tab[j] > tab[i]

Tukaj zamenjaj predznaka:

        while (tab[i] > pivot)
            i++;
         
        while (tab[j] < pivot)
            j--;

tisti if s komentarjem je pa tam zato, da zamenjas elementa samo, v kolikor je i na levi in j na desni oz. ce sta enaka (ce sta enaka, swap ni potreben, je pa potrebno povecat i in zmanjsat j, sicer ni pravilno particionirano!).

Zgodovina sprememb…

spremenil: usoban (30. okt 2012 ob 12:36)

mk818764 :: 30. okt 2012, 12:47

fej, kako grdo programiranje.
No, tudi jaz sem tako programil v prvem letniku

marjan_h :: 30. okt 2012, 13:00

aja, sedaj razumem! dobro hvala.

usoban :: 30. okt 2012, 13:29

usoban je 30. okt 2012 ob 12:33 izjavil:

Ko to konca, ves da imas v tab[i] element, ki je manjsi od pivota, tab[j] pa vecji od pivota => tab[j] > tab[i]

tle sem se zmotil, pravzaprav je ravno obratno.

ko konca oba while loopa, imas v tab[i] element, ki je vecji oz. kvecjemu enak pivotu, v tab[j] pa element, ki je manjsi oz. kvecjemu enak pivotu, iz cesar sledi da je tab[i] > tab[j] oz. kvecjemu tab[i] == tab[j]

Spura :: 30. okt 2012, 14:24

Zadeva sicer vsebuje en subtilen bug:

int pivot = tab[ (int) (i + j) / 2];

tle bi moralo bit:

int pivot = tab[(j-i)/2 + i];

golobich :: 30. okt 2012, 14:44

Uf, java. Če se prav spomnem, a nima JAVA že vgrajen QuickSort algoritem?
Mislim da moreš rečt Array.sort(tabela)
Če želiš pa v obratnem vrstnem redu pa mislim da je Collections.reverseOrder() neki na to foro je to vem. Probi se malo poigrat ;)

lp, golobich

Spura :: 30. okt 2012, 14:50

Pomojem ni tle poanta, da bi uporabljal ze napisan algoritem.

marjan_h :: 23. nov 2012, 22:13

Ali se da v javi napisati QuickSort algoritem za ArrayListe. Jaz sem ga poskusil, vendar mi program zmrzne ko ga poženem. V bistvu sem samo zamenjal tab[i] z tab.get(i)..itd. Moral bi delati.

krneki0001 :: 23. nov 2012, 22:30

quicksort 1

#include<iostream>
#include<ctime>
using namespace std;

int const N=10000;      //max st elementov polja
int const STR=1000000; //straza

//zamenjava dveh elementov
void Zamenjaj(int &a, int &b)
{
    int tmp=a;
    a=b; b=tmp;
}

void Vnos_rocni(int polje[], int vel)
{
    for(int i=0; i<vel; i++)
    {
        cout<<"vnesi "<<i+1<<". element:\n";
        cin>>polje[i];
    }
    polje[vel]=STR; //straza zaporedja
}

void Vnos_rand(int polje[], int vel)
{
   for(int i=0; i<vel; i++)
   {
    polje[i]=rand();
   }
   polje[vel]= STR; //straza zaporedja
}

void Izpis(int polje[], int vel)
{
    for(int i=0; i<vel; i++)
    {
        cout<<polje[i]<<"\n";
    }
    cout<<"\n";
}

int Deli(int polje[], int dno, int vrh)
{
    int w, i, j;
    w=polje[dno];
    i=dno;
    j=vrh+1;
    for(; ;)
    {
        do
        {
            j -=1;
        }
        while(polje[j]>w);

        do
        {
            i +=1;
        }
        while(polje[i]<w);

        if (i<j)
        {
            Zamenjaj(polje[i],polje[j]);
        }
        else
        {
            Zamenjaj(polje[j], polje[dno]);
            return j;
        }
    }
}

void HitroUredi( int polje[], int dno, int vrh)
{
    int delIndeks;
    if (dno<vrh)
    {
       delIndeks= Deli(polje, dno, vrh);
       HitroUredi(polje, dno, delIndeks-1);
       HitroUredi(polje, delIndeks+1, vrh);
    }
}





int main()
{
    int zaporedje[N];
    int vel;
    int izbira=0;
    srand(time(NULL));

    for(; ;)
    {
        cout<<"Hitro uredi - izbira:\n";
        cout<<"1 Vnos podatkov - rocni\n";
        cout<<"2 Generiranje nakljucnih podatkov\n";
        cout<<"3 Zagon algoritma Hitro uredi\n";
        cout<<"4 Izpis zaporedja\n";
        cout<<"5 Konec\n";
        cin>>izbira;
        switch (izbira)
        {
            case 1:
            {
                cout<<"vnesi velikost zaporedja:\n";
                cin>>vel;
                Vnos_rocni(zaporedje, vel);
                break;
            }
            case 2:
            {
                cout<<"vnesi velikost zaporedja:\n";
                cin>>vel;
                Vnos_rand(zaporedje,vel);
                break;
            }
            case 3:
            {
                cout<<"HitroUredi se je zagnal:\n";
                HitroUredi(zaporedje,0,vel-1);
                cout<<"HitroUredi se je zakljucil:\n\n";
                break;
            }

            case 4:
            {
                cout<<"Zaporedje:\n";
                Izpis(zaporedje, vel);
                break;
            }
            case 5:
            {exit(0);}
        }
    }


    return 0;
}

quicksort 2

//quickSort.cpp

#include <iostream.h>

typedef int aType;


//  prototypes
void Quicksort( aType a[], int first, int last );
int Pivot( aType a[], int first, int last );

void  Swap( aType &v1, aType &v2 );
void  PrintArray( aType A[], int nElements );


int main()
{
    aType testArray[] = { 3, 7, 1, 9, 12, 2, 4 };
    int nA = sizeof(testArray)/sizeof(aType);

    cout << "Cifer je: "  << nA << endl;

    cout << "Zacetno polje:" << endl;
    PrintArray( testArray, nA );

    Quicksort( testArray, 0, nA-1 );

    cout << "Koncno polje:" << endl;
    PrintArray( testArray, nA );
}
//quicksort
void Quicksort( aType a[], int first, int last ) 
{
    int pivot;
    cout << "          Vrednosti za Drevo " << first << " " << last << endl;
    if( first < last ) {
        pivot = Pivot( a, first, last );
        Quicksort( a, first, pivot-1 );
//      cout << "         Levo Drevo " << first << " " << last << endl;
        Quicksort( a, pivot+1, last );
//      cout << "        Desno Drevo " << first << " " << last << endl;
    }
}


//  Pivot:  Najde in vrne index elementa tabele.
int Pivot( aType a[], int first, int last ) 
{
    int  p = first;
    aType pivot = a[first];

    for( int i = first+1 ; i <= last ; i++ ) {
        if( a[i] <= pivot ) {
            p++;
            Swap( a[i], a[p] );
            cout << "Zamenjaj " << a[i]<< " in " << a[p] << endl;
        }
    }

    Swap( a[p], a[first] );

    return p;
}


//  Zamenjava:  Zamenjaj dve števili.
void  Swap( aType &v1, aType &v2 )
{
    aType  tmpVal;

    tmpVal = v1;
    v1 = v2;
    v2 = tmpVal;
}


// Izpiši polje
void  PrintArray( aType A[], int nElements )
{
    cout << "[ ";

    for( int i = 0 ; i < nElements ; i++ )
    {
        cout << A[i] ;
        if( i < nElements-1 )
           cout << " , ";
    }

    cout << " ] " << endl;
}

quicksort 3

#include <iostream>

using namespace std;


void show (int size, float *a)
{
int i;
for (i = 0; i < size; i++)
cout << a[i] << " ";
cout << endl;
}
void sort (int size, float *a, int pivotindex)
{
int smidx, idx;
float temp;
float pivot = a[pivotindex];
show (9, a);
a[pivotindex] = a[0];
a[0] = pivot;
cout << "swap(" << 0 << ", " << pivotindex << ")";
cout << " (pivot = " << pivot << ")" << endl;
show (9, a);
smidx = 0;
for (idx = 1; idx < size; idx++)
{
if ( a[idx] < pivot )
{
smidx++;
temp = a[smidx];
a[smidx] = a[idx];
a[idx] = temp;
cout << "swap(" << smidx << ", " << idx << ")" << endl;
show (9,a);
}
}
temp = a[smidx];
a[smidx] = a[0];
a[0] = temp;
cout << "swap(" << 0 << ", " << smidx << ")" << endl;
show (9,a);
}


int main(int)
{
static float a[] = {45, 82, 25, 94, 50, 60, 78, 32, 92};
sort (9, a, 4);
}

Zgodovina sprememb…

spremenilo: krneki0001 (23. nov 2012 ob 22:37)

marjan_h :: 24. nov 2012, 11:50

Nebivedu, hvala za odgovor, vendar to je napisano v c++. Če želite vam pokažem kodo kako sem naredil, da ne boste imeli velik dela.

No tako sem naredil, vendar mi vrne Exception.


public static void quicksort(ArrayList<Integer> list, int low, int high){
        int i = low, j = high;
        int pivot = list.get((int)list.size()/2);
        
        while (i <= j){
            while (list.get(i) < pivot)
                i++;
            
            while (list.get(j) > pivot)
                j--;
            if (i <= j){
                int temp = list.get(i);
                list.remove(i);
                list.add(i,list.get(j));
                list.remove(j);
                list.add(j,temp);
                i++;
                j--;
            }
        }
        if (low < j){
            quicksort(list,low, j);
        }
        if ( i < high){
            quicksort(list,i,high);
        }
        
    }
    
    
    public static void main (String args[]){
        ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(10);
        al.add(21);
        al.add(9);
        al.add(7);
        al.add(43);
        al.add(11);
        al.add(2);
        
        quicksort(al,0,al.size()-1);
        for(Integer e: al){
            System.out.println(e);
        }
    }

krneki0001 :: 24. nov 2012, 14:38

In kaj je problem, če je v C++? Iz takega programa se da javo al pa C# konvertirat z lahkoto. Vsak programer ti bo povedal, da je to 2 minuti dela.

marjan_h :: 24. nov 2012, 15:02

Hvala za tvoj trud, vendar pri javi ima ArrayList metode get() pa remove(). QuickSort ni problem, tega sem že napisal za tabele.

Sedaj edino, kar ne vem je zakaj mi vrne napako pri zgornjem algortimu. Izkušen programer bi ziher opazil kaj sem narobe naredil, jaz se še samo učim :).

Hvala

krneki0001 :: 24. nov 2012, 16:36

Spremeni v javo drugi program iz mojega posta, pa ti bo vse jasno, kaj manjka. atype spremeni v arraylist, pa imaš že skoraj vse narejeno, potem pa boš takoj našel napako pri tebi.

Seveda bi ti lahko takoj povedal, kaj je napaka, ampak daj raje še malo sam pomisli. Iz te napake se boš dost naučil, ker je taka začetniška, ki jo ponavljajo občasno tudi izkušeni programerji.

Zgodovina sprememb…

spremenilo: krneki0001 (24. nov 2012 ob 16:37)

marjan_h :: 24. nov 2012, 16:58

Ja edino, kar jaz vidim je vrstica za pivot. Tole si verjetno mislil.

    public static void quicksort(ArrayList<Integer> list, int low, int high){
        int i = low, j = high;

        //tale vrstica je bila narobe

        int pivot = list.get(low + (high - low) / 2);
        
        while (i <= j){
            while (list.get(i) < pivot)
                i++;
            
            while (list.get(j) > pivot)
                j--;
            if (i <= j){
                int temp = list.get(i);
                list.remove(i);
                list.add(i,list.get(j));
                list.remove(j);
                list.add(j,temp);
                i++;
                j--;
            }
        }
        if (low < j){
            quicksort(list,low, j);
        }
        if ( i < high){
            quicksort(list,i,high);
        }
        
    }
    
    
    public static void main (String args[]){
        ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(10);
        al.add(21);
        al.add(9);
        al.add(7);
        al.add(43);
        al.add(11);
        al.add(2);
        
        quicksort(al,0,al.size()-2);
        for(Integer e: al){
            System.out.println(e);
        }
    }

Samo če kličem quicksort z al.size() - 1 mi še vedno vrže exception. Če jo pa kličem takole, mi pa ne uredi elementov po vrsti.

Zanimivo. Jaz več ne vidim napak, če jih kdo vidi naj pove. Če se to izkušenim programerjem dogaja, potem se lahko tudi meni :).

marjan_h :: 24. nov 2012, 20:05

Evo, sedaj sem pa najdu napako. Popravil sem tale if stavek.

            if (i <= j){
                int temp = list.get(i);
                list.set(i,list.get(j));
                list.set(j,temp);
                i++;
                j--;
            }

Namesto add pa remove sem zamenjal tole z set, kar nisem vedel da obstaja. Sedaj dela normalno, če bo kdo to temo bral, sedaj ve.

Hvala vsem za pomoč, vas bom enkrat na pivo povabil.

krneki0001 :: 24. nov 2012, 20:27

Poglej, sam si omenil metode na začetku, potem pa jih nisi uporabil. Standardna napaka začetnika, pa tut izkušenemu programerju se naredi.

Upam, da si povlekel kaj znanja iz tega.

Vredno ogleda ...

	Tema	Sporočila	Ogledi	Zadnje sporočilo
	Tema	Sporočila	Ogledi	Zadnje sporočilo
»	Java passing uro1001 Oddelek: Programiranje	20	3600 (3253)	mihibo5 12. jan 2015 19:45:41
»	[Java] Quicksort EWER115 Oddelek: Programiranje	6	735 (571)	MrBrdo 28. maj 2011 15:59:25
»	[C++] Insertion sort - problem golobich Oddelek: Programiranje	19	1101 (940)	Thomas 10. nov 2010 23:19:19
»	It means business (strani: 1 2 3 4 5 6 7 8 ) Thomas Oddelek: Znanost in tehnologija	374	28283 (14282)	Thomas 26. sep 2008 18:14:06
»	[c++]Urejanjepolja purki Oddelek: Programiranje	9	1355 (1176)	purki 24. maj 2007 07:47:05

Več podobnih tem

Zadnje novice

Zadnji članki

Išči:

Forum » Programiranje »
Quicksort algoritem

Quicksort algoritem