3. MergeSort Problem

MergeSort Problem

  • I

    Mein MergeSort in C funktioniert leider nicht ganz so wie ich das gerne hätte 😃
    Könntet ihr mir bitte mal weiter helfen. Ich komme gerade echt nicht mehr weiter oO

    double mergeSort(int *array, unsigned int size){
	clock_t start, ende;

	start = clock();

	mergesort(array, 0, size-1);

	ende = clock();

	return (double)(ende-start)/CLOCKS_PER_SEC;
}

void mergesort(int *array, int p, int r){
	if(p < r){
		printf("MergeSort(%d, %d);\n", p, r);
		int q = (p+r) / 2;
		mergesort(array, p, q);
		mergesort(array, q+1, r);
		merge(array, p, q, r);
	}
}

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

	for(i = p; i <= r; i++){
		b[k] = array[i];
		++k;
	}

	i = k = p; j = q+1;

	while(i <= q && j <= r){
		if(b[i] <= b[j])
			array[k++] = b[i++];
		else
			array[k++] = b[j++];
	}

	while(i <= q)
		array[k++] = b[i++];	

	printArray(array, size, 100);

	free(b);
}

    mfg. Dagobert

    0
  • K

    Joa

    EDIT:
    Ich raffe deine Signatur nicht, erklär mal.

    0
  • J

    Bist du denn schon einmal mit einem Debugger schrittweise durchgegangen?

    0
  • I

    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

    0
  • J

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

    0
  • I

    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

    0
  • Mod

    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.

    0
  • I

    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

    0
  • Mod

    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.

    0
  • I

    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

    0
  • Mod

    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.

    0
  • ?

    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

    0
  • ?

    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

    0
Anmelden zum Antworten