Quicksort problem z sortowanie po wywołaniu rekurencyjnym

Dla specjalistów Programowanie
#1 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LICZBA_ELEMENTOW 10
int tab[LICZBA_ELEMENTOW];

void wyswietl(int *tab){
printf("\n");
    int i;
    for(i=0;LICZBA_ELEMENTOW>i;++i)
        printf("%d,",tab[i]);
printf("\n");
}
void zamiana(int *tab,int x,int y){
    int a;
    a=tab[y];
    tab[y]=tab[x];
    tab[x]=a;
}
void bubble_sort(int *tab){
    int j;
    int jj=0;
    for(j=1;LICZBA_ELEMENTOW>j;++j){
        if(tab[j-1]>tab[j]){
            zamiana(tab,j,j-1);
            jj++;
        }
    }
    if(jj!=0)
        bubble_sort(tab);
}
void insert_sort(int *tab){
    int i,j;
    for(j=1;LICZBA_ELEMENTOW>j;++j){
        i=0;
        while(tab[j-i-1]>tab[j-i]){
            zamiana(tab,j-i,j-i-1);
            i++;
        }
    }
}
void quick_sort(int *tab,int x,int y){
    int a=x;
    int b=y;
    while(a<b){
        while(tab[a]<=tab[b] && b>0)
            b--;
        if(tab[a]>tab[b])
            zamiana(tab,a,b);
        while(tab[a]<=tab[b] && b>a)
            a++;
        if(tab[a]>tab[b])
            zamiana(tab,a,b);
    wyswietl(tab);

    }
///////////////////////////////////////
    if(x<y){
        quick_sort(tab,x,b);
        quick_sort(tab,a,y);
    }
//////////////////////////////////////
}
int main()
{
    int i;
    int x=0;
    int y=LICZBA_ELEMENTOW-1;
    srand(time(NULL));
    for (i=0;LICZBA_ELEMENTOW>i;++i){
        tab[i]=1+rand()%100;
        printf("%d,",tab[i]);
    }
    //bubble_sort(tab);
    //insert_sort(tab);
    quick_sort(tab,x,y);
    wyswietl(tab);
return 0;
}

Jeszcze mam mały problem z debugerem po zaznaczeniu lini na którym ma się program zatrzymać ignoruje to zaznaczenie i kompiluje do końca.(code blox)

#2

Hmm. Bo jakby ci powiedzieć program zawsze skompiluje się do końca po mimo wstawienia breakpoint-ów. Debugger jest narzędziem czasu wykonania, a nie kompilacji. Jeśli debugger nie zatrzymuje się na breakpoint-cie to zapewne sterowanie nie dochodzi do tego miejsca przykładowo:

 

if (1 != 1) {
    // tu wstaw breakpoint. na nim nie zatrzyma się wykonanie.
}

Na breakpoint powinieneś patrzeć, jak na wstawienie instrukcji o specjalnym kodzie na który zareaguje nadzorujący wykonanie watchdog, zatrzymując tym samym wykonanie programu. Jeśli sterowanie gdzieś nie dotrze (instrukcja nie zostanie odłożona do wykonania przez procesor), to się nie zatrzyma.

#3

Hm gdzie bym nie postawił breakpoint to nie działa;/ a jak dam debug–>step into to moge sie przesuwać tylko po linijkach w main do funcji nie przechodzi.

 

 

 

 

Dalej ne rozgryzłem tego błędu.

void quick_sort(int *tab,int x,int y){
    int a=x;
    int b=y;
    while(a<b){
        while(tab[a]<=tab[b] && b>0)
            b--;
        if(tab[a]>tab[b])
            zamiana(tab,a,b);
        while(tab[a]<=tab[b] && b>a)
            a++;
        if(tab[a]>tab[b])
            zamiana(tab,a,b);
    wyswietl(tab);

    }
///////////////////////////////////////
    if(x<y){
        quick_sort(tab,x,b);
        quick_sort(tab,a,y);
    }
//////////////////////////////////////
}
#4

Ale w czym problem, nie sortuje poprawnie czy się wysypuje?

#5

działa w nieskończoność, tzn dokładniej  po podziale na pół z lewej strony sortuje, a z prawej już nie, tak jak by nie przekazywał nowych argumentów do funkcij .

#6

Cóż ogólnie to ciężko coś w tym znaleźć, strasznie napisany kod, brak rozdzielenia partition, pivota i ogólnie zamysł jakby nieudolnie, bez mózgu próbować przepisać pseudokod. Brakuje trochę +/- 1 no i się pętli. Generalnie, nie chce mi się sprawdzać brzydkiego kodu. Porównaj z moim:

 

#include <cstdio>

void swap(int* a, int* b) {
	int t = *a;
	*a = *b;
	*b = t;
}

int partition(int* A, int l, int r) {
	int pivot = A[r];
	int i = l-1;
	
	for (int j = l; j < r; j++) {
		if (A[j] <= pivot) {
			swap(&A[++i], &A[j]);
		}
	}
	
	swap(&A[++i], &A[r]);
	
	return i;
}

void quicksort(int* A, int l, int r) {
	if (l < r) {
		int pivot = partition(A, l, r);
		
                quicksort(A, l, pivot-1);
		quicksort(A, pivot+1, r);
	}
}

int main() {
	int A[] = {1,6,3,9,2,4,7,8,5};
	int length = sizeof(A)/sizeof(int);
	
	quicksort(A, 0, length - 1);
	
	for (int i = 0; i < length; i++) {
		printf("%d ", A[i]);
	}
	
	return 0;
}

Hmm ty w ogóle uruchamiasz go w trybie debugowania? Korzystałeś kiedyś z jakiegokolwiek debuggera? Zainstalowałem przed chwilą code blocks’a i mi wszystko działa (używam go może 3 raz w życiu, bo używanie go chociażby przy eclipsie CDT, to jak pukanie się w czoło). Nagraj może jakiś filmik, co robisz, bo niestety nie jestem w stanie stwierdzić co tobie nie działa.

#7

Tak na pierwszy rzut ok to wogóle działa bo mam wielkie wątpiliwości, w jakim jezyku programujesz,(swap(&A[++i], &A[r]); --> jeżeli C,C++ to coś takiego jest niedopouszczalne).

  1. Warunek do sortowania w drógą strone ale to bez znaczenia.

  2. swap(&A[++i], &A[r]); zamieniasz to samą wartość po co ?

3.  if (A[j] <= pivot)           swap(&A[++i], &A[j]);

 pivot - stała wartość nadana przed pentlą, zwiekszasz j++ ok. Późnje zamieniasz A z A[j] gdzie i++ zwiekszasz ok. Teraz magiczne pytanie do Ciebie zamieniasz wartość do której nie masz pewności czy jest mniejsza czy wieksza bez SENSU!

Takich algorytmów jak tówj w necie jest pełno, oraz jest pełno dużo lepiej napisanych. Pytanie zadane na forum było inne!

 

A co do debuger tak użwyam go w trybie debug nie release, a co do uściślenia teraz zauważyłęm że na widows 8.1 jest problem chyba bo na 7 mi działa.

 

Teraz mały komentarz do autora powyższego posta kostek135.

Ja wiem jak ten algorytm napisać inaczej a nie tego dotyczyło pytanie. Funkcje nie są po to żeby program ładnie wyglądał

Bez mózgu przepisywać pseudokod, skomentuje to tak Pozdrawiam.

 

Rozwiązanie teraz jeszcze trzeba pomyśleć jak nie przeżucać nie potrzebnie elementy wiem, że można wybrać odrazu jakiś punkt tablicy i ją podzielić ale szukaminnych innych rozwiązań

void quick_sort(int *tab,int x,int y){
    int a=x;
    int b=y;
    while(ab){
        while(tab[a]=tab[b] ba)
            b--;
        if(ba)
            zamiana(tab,a,b);
        while(tab[a]=tab[b] ba)
            a++;
        if(ba)
            zamiana(tab,a,b);
    }
///////////////////////////////////////
    if(xy){
        quick_sort(tab,x,b-1);
        quick_sort(tab,a+1,y);
    }
//////////////////////////////////////
}
void quick_sort_ver2(int *tab,int x,int y){
    int a=x;
    int b=y;
    while(ab){
        while(tab[a]=tab[b] ba)
            b--;
        while(tab[a]=tab[b] ba)
            a++;
        if(ba)
            zamiana(tab,a,b);
    }
    if(xy){
        quick_sort(tab,x,b-1);
        quick_sort(tab,a+1,y);
    }
}
#8

Trzeba było skompilować i uruchomić, a nie mieć wątpliwości.

 

Jest jak najbardziej dopuszczalne. Równie dobrze mogłem zapisać to tak

swap(A + (++i), (A + r));

no ale jak dla mnie odwołanie się do elementu tablicy i potem podanie, że oczekuje adresu jest czytelniejsze od arytmetyki wskaźnikowej. Nie mniej kompilatory tłumaczą to na identyczny asembler. Poza tym, programuje w C, przy czym tak naprawdę trzeba zamienić tylko nagłówek biblioteki bo podałem ten dla C++ z rozpędu.

 

Jaką tę samą wartość. Przekazuje za każdym razem dwa różne adresy, i zamieniam miejscami elementy pod nimi.