merge sort implentieren

Neue Frage »

Auf diesen Beitrag antworten »
dereuler merge sort implentieren

Meine Frage:
implementieren sie die Methode merge()


public class mergesort {
public static void merge(int A[], int p, int q, int r){
/* Hier Code ergänzen */
}

public static void testeBeispiel(int[] beispiel){
int n = beispiel.length-1;
System.out.print("Unsortiert: ");
for(int i=1; i <= n; i++) System.out.print(beispiel[i] + " ");
System.out.println("");

merge(beispiel, 1, n/2, n);

System.out.print("Sortiert : ");
for(int i=1; i <= n; i++) System.out.print(beispiel[i] + " ");
System.out.println("");
System.out.println("_____________________________________________");
}

public static void main(String[] args){
testeBeispiel(Beispiele.beispielA());
testeBeispiel(Beispiele.beispielB());
testeBeispiel(Beispiele.beispielC());
testeBeispiel(Beispiele.bespielD());
}

Meine Ideen:
ich weiß leider nicht wie ich vorgehen soll,wenn jemand für mich einen Ansatz hätte würde es super

danke im Voraus
 
Auf diesen Beitrag antworten »
Shizmo

Du suchst dir den Pseudocode von Merge-Sort bzw. Merge raus (zB Wikipedia) und implementierst ihn in Java.

Zum Beispiel:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
       public static void merge(int[] a, int p, int q, int r){
		int n1 = q-p+1;
		int n2 = r-q;
		
		int[] L = new int[n1+1];
		int[] R = new int[n2+1];
				
		for(int i = 1; i < L.length; i++)
			L[i-1] = a[p+i-1];
		for(int j = 1; j < R.length; j++)
			R[j-1] = a[q+j];
		
		
		L[n1] = Integer.MAX_VALUE;
		R[n2] = Integer.MAX_VALUE;
		
		int i = 0, j = 0;
		
		for(int k = p; k < r+1; k++){
			if(L[i] <= R[j]){
				a[k] = L[i];
				i++;
			}
			else{
				a[k] = R[j];
				j++;
			}
		}
	}


Das ist allerdings nur die Merge-Methode, Merge-Sort würde dann so aussehen:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
public static void mergeSort(int[] a, int p, int r){
		if(p < r){
			int q = (p+r)/2;
			mergeSort(a,p,q);
			mergeSort(a,q+1,r);
			merge(a,p,q,r);
		}
	}
Auf diesen Beitrag antworten »
dereuler

Was ist denn genau der Unterschied zwischen merge sort und Methode ??

In der Aufgabe stand ich soll die Methode merge implementieren deshalb
Auf diesen Beitrag antworten »
Shizmo

Am besten du liest dir mal durch was Merge-Sort überhaupt ist, was es macht und wie er arbeitet, ist wirklich nicht schwer zu verstehen: https://de.wikipedia.org/wiki/Mergesort#Implementierung

Dann weißt du auch für was Merge-Sort Merge braucht Augenzwinkern
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »