[C] quick sort

Odpowiedz Nowy wątek
2010-04-13 20:55
0

Mam problem, napisalem quicksorta i on zle sortuje tj. przewaznie okolo 2 elementy sa zle wstawione

z gory dzieki za pomoc

#include <stdio.h>
#include <time.h>
#define N 10
void quicksort(int t[], int p, int r);
int partition(int t[], int p, int q);

int main(){
 srand(time(0));
 int t[N];
 int i=0;

 for (i; i<N; ++i)
    t[i]=rand()%43;

 for (i=0; i<N; ++i)
    printf("%d\t", t[i]);

 quicksort(t,0,N);
 printf("\n\n\n");

 for (i=0; i<N; ++i)
    printf("%d\t", t[i]);

return 0;
}
void quicksort(int t[], int p, int r){
 if (p<r){
    int q=partition(t,p,r);
    quicksort(t,p,q-1);
    quicksort(t,q+1,r);
 }
}
/////////////////////////////////////////////
int partition(int t[], int p, int r){
 int x=t[r-1];
 int i=p-1;
 int j;
 for (j=p; j<=r-2; ++j){
    if (t[j] <= x){
        ++i;
        int k=t[i];
        t[i]=t[j];
        t[j]=k;
    }
 }
 int g=t[i+1];
 t[i+1]=t[r-1];
 t[r-1]=g;
 return i+1;
}

Pozostało 580 znaków

2010-04-14 02:39
0
void quickSort( int l, int r, int *tab )
{
    int i = l;
    int j = r;
    int x = tab[ ( l + r ) / 2 ];

    while( i <= j )
    {
        while( tab[ i ] < x )
            ++i;

        while( x < tab[ j ] )
            --j;

        if( i <= j )
        {
            swap( tab[ i ], tab[ j ] );
            ++i;
            --j;
        }
    }

    if( j > l )
        quickSort( l, j, tab );

    if( i < r )
        quickSort( i, r, tab );

    return;
}

Znalazłem swoją starą wersję, może Ci się przyda. Przeanalizuj sobie i sprawdź.
pozdrawiam


"..."
"odp"
"qtMaster"

Pozostało 580 znaków

2010-04-14 23:29
0

ok, dzieki
tylko podzial jest u Ciebie wedlug Hoare'a, a to udalo mi sie napisac...

a widzi ktos moze blad u mnie w moojej wersji, bo ja juz nie mam pomyslow...

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0