Quicksort algoritem

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!).

aja, sedaj razumem! dobro hvala.

Zadeva sicer vsebuje en subtilen bug:

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

tle bi moralo bit:

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

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

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

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.

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.

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.