Shell_sort trøbbel. Hjelp til debugging.

[Simon Zimmermann]

Hei,

 

Jeg har lekt meg litt med en sorterings algoritme, eller i hvert fall forsøkt å lage en såkalt Shell_sort i C. Resultatet er dessverre ikke helt som ventet. I henhold til egen logikk kom jeg frem til at denne koden burde virke, men output er for meg litt merkelig. Så om noen ser hva jeg gjør feil her ville jeg satt pris på å få litt hjelp.

 

Den åpenbare feilen er jo at det første tallet ikke ser ut til å bli sortert. noe som er merkelig. Når programmet kjøres i linux gir det meg også andre resultater enn i win 32. I linux byttes det første tallet ut med 0, og dersom tallrekken jeg bruker som input er stor vil der komme flere 0 på starten.

 

#include <stdio.h>
#include <stdlib.h>

static void shell_sort(int a[], int size) {

int i,j, tmp;

int gap = 5;

// Looping the array.
for(i = 0; i < size; i++){

	// loop increasing with gap sequence(5 - 3 - 1)
	for(j = i; j < size; j += gap){

		// check if current number a[i] is bigger then the next in gap sequence
		if(a[i] > a[j + gap]){
			// swap numbers, dirty and easy way;)
			printf("swap %d with %d \n", a[i], a[j + gap]);
			tmp = a[i];
			a[i] = a[j + gap];
			a[j + gap] = tmp;
		}
	}

	// reset the loop and decrease gap size.
	if(gap > 1) {
		   gap -= 2;
		   i = 0;	  
	}
}
}  

/* enkel main for å kjøre scriptet. Regner med at folk er for late til å lage sjæl :P */   
int main(int argc, char *argv[]) {

	int *a;
	int i;

	a = (int*) malloc((argc - 1) * sizeof(int));

	for (i = 0; i < argc - 1; i++){
		 *(a+i) = atoi(argv[i + 1]);
	 }
	shell_sort(a, argc - 1);

   for (i = 0; i < argc - 1; i++)
		printf("%d ", a[i]);
	printf("\n");

	free(a);
	return 0;
}

 

/* OUTPUT win 32

17-numbers for debugging: 50 68 79 39 2 67 21 28 38 35 55 99 81 8 9 73 37 32

 

F:\Web\C\lab3>shell_sort.exe 50 68 79 39 2 67 21

swap 68 with 2

swap 79 with 39

swap 39 with 21

swap 79 with 68

swap 68 with 67

swap 67 with 39

swap 79 with 68

swap 68 with 67

swap 79 with 68

50 2 21 39 67 68 79

 

------

OUTPUT linux 32 bit, gcc compiler

 

simon@simon-laptop:~/fag/is-105/lab3$ ./shell_sort 50 68 79 39 2 67 21

swap 50 with 0

swap 68 with 2

swap 79 with 39

swap 39 with 21

swap 79 with 68

swap 68 with 67

swap 67 with 39

swap 79 with 68

swap 68 with 67

swap 79 with 68

0 2 21 39 67 68 79

 

*/

 

takk for all hjelp

[zotbar1234]

(...)

static void shell_sort(int a[], int size) {

int i,j, tmp;
  int gap = 5;

// Looping the array.
for(i = 0; i < size; i++){
	// loop increasing with gap sequence(5 - 3 - 1)
	for(j = i; j < size; j += gap){
		// check if current number a[i] is bigger then the next in gap sequence
		if(a[i] > a[j + gap]){

 

Dersom i == size-1, og j == i, er j+gap innenfor arrayens grenser?

 

/* enkel main for å kjøre scriptet. Regner med at folk er for late til å lage sjæl :P */   
int main(int argc, char *argv[]) {

	int *a;
	int i;

	a = (int*) malloc((argc - 1) * sizeof(int));

 

Bare et lite tips. Jeg synes det er veldig mye enklere å skrive slik:

 

int *a = malloc((argc-1) * sizeof *a);

 

... så slipper du å tenke på typen til det som a peker på på høyre siden. typecast er heller ikke nødvendig i dette tilfellet i C.

 

/* OUTPUT win 32

17-numbers for debugging: 50 68 79 21 28 39 2 67 38 35 55 99 81 8 9 73 37 32

 

Jeg ser 18 tall, ikke 17.

[Simon Zimmermann]

Takk for svar. zotbar. Den feilen var jo egentlig ganske åpenbar. når jeg skrev det testet jeg ikke for det for jeg tenkte at arrayet ikke var større enn size. Uansett. så sliter jeg fremdeles med en liten irriterende greie. Nedenfor ser dere min funksjon. med a > a[j] tester jeg om en verdi i arrayet er større enn et annet, og basert på resultatet bytter så verdien plass. Dette fungerer helt top, furuten om første gang spørringen utføres.

F.eks. om min input er: 50 68 79 39 2 67 21 28 38 35 55 99 81 8 9 73 37 32

er resultatet, nesten sortert:50 2 8 9 21 28 32 35 37 38 39 55 67 68 73 79 81 99

 

alle tall foruten om det første, i eksempelet 50, blir sortert riktig. Jeg har forsøkt å debugge med ddd, men skjønner ikke hvorfor spørringen ikke returnerer som forventet.

 

Dette er forresten første gang jeg prøver meg på C, så jeg er ukjent med hele malloc greia, så takk for tipset.

 

static void shell_sort(int a[], int size) {

int i,j, tmp;

int gap = 5;

// Looping the array.
for(i = 0; i < size; i++){

	// loop increasing with gap sequence(5 - 3 - 1)
	for(j = i + gap; j < size; j += gap){

		// check if current number a[i] is bigger then the next in gap sequence
		if(a[i] > a[j] && j < size){
			// swap numbers, dirty and easy way;)
			printf("swap %d with %d \n", a[i], a[j]);
			tmp = a[i];
			a[i] = a[j];
			a[j] = tmp;
		}
	}

	// reset the loop and decrease gap size.
	if(gap > 1) {
		   gap -= 2;
		   i = 0;	  
	}
}
}

Endret 20. januar 2009 av Yali

[zotbar1234]

Takk for svar. zotbar. Den feilen var jo egentlig ganske åpenbar.

 

valgrind er din venn.

 

når jeg skrev det testet jeg ikke for det for jeg tenkte at arrayet ikke var større enn size. Uansett. så sliter jeg fremdeles med en liten irriterende greie. Nedenfor ser dere min funksjon. med a > a[j] tester jeg om en verdi i arrayet er større enn et annet, og basert på resultatet bytter så verdien plass. Dette fungerer helt top, furuten om første gang spørringen utføres.

F.eks. om min input er: 50 68 79 39 2 67 21 28 38 35 55 99 81 8 9 73 37 32

er resultatet, nesten sortert:50 2 8 9 21 28 32 35 37 38 39 55 67 68 73 79 81 99

 

alle tall foruten om det første, i eksempelet 50, blir sortert riktig. Jeg har forsøkt å debugge med ddd, men skjønner ikke hvorfor spørringen ikke returnerer som forventet.

 

Fordi at a[0] sammenlignes med a[5], a[10], a[15] *men kun disse*. Du justerer riktignok skrittlengden, men det gjør du før i inkrementeres. Det gir overhodet ingenting mening. Med Shell sort foretar man en viss mengde pass over hele datasettet som skal sorteres i stadig mer krympende skritt (det siste passet er insertion sort, egentlig).