MergeSort Problem

Ipschie

Debugger
Ich hab vor 2 Wochen mit C angefangen, haben vorher in der Uni ein Semester Java gehabt, wenn du mir sagst wie ich mit dem gcc Compiler gescheit Debuggen kann
werde ichs mal versuchen.

mfg. Dagobert

Janjan

Google -> "Linux C Debugger". Je früher du lernst mit dem Debugger umzugehen, desto besser.

Ipschie

Ja das ist wohl war, aber dann müsste ich erstmal lernen wie ich auf einem unix sun client software installiere oO

naja wahrscheinlich dauerts wohl noch bis mein MergeSort funzt

mfg. Dagobert

SeppJ

Ipschie schrieb:

Ja das ist wohl war, aber dann müsste ich erstmal lernen wie ich auf einem unix sun client software installiere oO

Wenn du einen gcc installiert hast, ist mit an Sicherheit grenzender Wahrscheinlichkeit auch gdb verfügbar.

Ipschie

Okay ich habs jetzt soweit geschafft das er Zahlen bis 80 Sotiert, danach kommt bis 85 ein segmentation fehler, und dannach ist ganz vorbei das ich in andere bereiche schreibe.
Was ist noch falsch?

void merge(int *array, int p, int q, int r){
	printf("Merge(%d, %d, %d);\n", p, q, r);
	int i, j, k = 0, size = r-p;

	int *b;
	b = malloc(size * sizeof(int));			/* Speicherplatz für die auszulagenden Elemente alocieren */

	for(i = p; i <= r; i++){			/* Elemente vom eigentlichem Feld in ein Hilfsfeld kopieren */
		b[k] = array[i];
		++k;
	}

	i = 0;						/* i = 0 -> erstes Element im Hilfsfeld */
	k = p;						/* k -> position im Array, wo eingefügt wird, */
	j = size/2+1;					/* j = erstes Element der 2 Hälfe im Hilfsfeld */
	printf("i = %d; k = %d, j = %d\n", i, k, j);
	while(i <= q-p && j <= size){			/* solange i <= der 2 Hälfe && j im Feld ist: */
		if(b[i] <= b[j])			/* Gucken welches das kleinere der beiden Teilelemente ist, und ins eignetliche Feld kopieren */
			array[k++] = b[i++];
		else
			array[k++] = b[j++];
	}

	while(i <= q-p)					/* Solange noch Elemente im ersten Teil sind, werden diese hinten dran gehangen */
		array[k++] = b[i++];	

	printArray(b, size, 100);

	free(b);
}

mfg. Dagobert

SeppJ

Wie soll man da durchblicken? Benenn mal deine Variablen vernünftig!

Ist dir bewusst, dass Arrays in C bei 0 anfangen? Die Schleifenabbruchbedingungen sehen mir nämlich verdächtig danach aus, dass du eins zu hoch zählst. Da ich aber keine Ahnung habe wofür p, q, r stehen sollen, habe ich keine Ahnung, ob das bei dir wirklich ein Fehler ist.

Ipschie

Wie soll man da durchblicken? Benenn mal deine Variablen vernünftig!

Ich kann auch nur nach uni Vorgaben arbeiten.
Aber:
p = Anfang des Teil des Feldes welcher sortiert werden soll
r = Ende des Teils
q = Mitte des Teils

Das die Arrays bei 0 anfangen ist mir bewusst, jedoch weiß ich nicht wo ich sie falsch behandel denn dann wäre der ganze post überföüssig oO

mfg. Dagobert

SeppJ

Mindestens die erste while-Schleife ist schon einmal falsch, da b von 0 bis size-1 geht, du über j aber auch auf den Index size zugreifst. Auf gleiche Weise ist die Bedingung für i wahrscheinlich algorithmisch falsch, da q-p bereits über der Mitte ist.

Man muss nicht zig mal neu Speicher anfordern. Es reicht, wenn man's einmal macht. Und da Du in einem C++ Forum und nicht in einem C Forum fragst, kriegst Du auch etwas von C++ zu sehen.

/// performs merge sort on the first size elements of array
/// temp points to an array of at least size elements.
void mergesort_internal(int* array, unsigned size, int* temp)
{
  ...Deine Hausaufgabe...
  (meine Lösung hat hier keine 15 Zeilen)
}

/// performs merge sort on the first size elements of array
void mergesort(int* array, unsigned size)
{
  std::vector<int> buffer (size);  // <--- C++
  mergesort_internal(array,size,&buffer[0]);
}

kk

Ipschie schrieb:

/* Solange noch Elemente im ersten Teil sind, werden diese hinten dran gehangen */

sag mal wo kopierst du eigentlich den rest des zweiten Teils oder gibts den nicht.

lg lolo