Merge Sort Java
https://stackoverflow.com/questions/1735863
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, eine Merge-Sortiermethode zu machen, aber es hält auf die falschen Arten gibt. Wo muss ich ändern es tatsächlich sortieren das Array zu machen? Welcher Teil des Codes hat, anders zu sein? Vielen Dank für Ihre Zeit.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
int elements = (rHigh - lHigh +1) ;
int[] temp = new int[elements];
int num = left;
while ((left <= lHigh) && (right <= rHigh)){
if (a[left] <= array[right]) {
temp[num] = array[left];
left++;
}
else {
temp[num] = array[right];
right++;
}
num++;
}
while (left <= right){
temp[num] = array[left]; // I'm getting an exception here, and is it because of the num???
left += 1;
num += 1;
}
while (right <= rHigh) {
temp[num] = array[right];
right += 1;
num += 1;
}
for (int i=0; i < elements; i++){
array[rHigh] = temp[rHigh];
rHigh -= 1;
}
EDIT: jetzt die MergeSort Art nicht wirklich die Zahlen, kann mir jemand sagen, wo es speziell ist? vor allem, wenn ich die „Testing merge sort“ drucken Teil.
Lösung
Zunächst einmal bin ich davon aus, das akademisch eher als praktisch, da Sie kein in Sortierfunktion eingebaut werden. That being said, hier ist etwas Hilfe Sie in die richtige Richtung zu bekommen:
In der Regel kann man denken an eine Mergesort als zwei verschiedene Methoden: eine Zusammenführung () Funktion, dass verschmilzt zwei Listen in eine sortierte Liste sortiert und MergeSort (), die rekursiv die Liste in einzelnen Elementlisten bricht. Da eine einzelne Element Liste bereits sortiert ist, verschmelzen Sie dann alle die Listen zu einer großen sortierten Liste.
Hier einig Off-Hand Pseudo-Code:
merge(A, B):
C = empty list
While A and B are not empty:
If the first element of A is smaller than the first element of B:
Remove first element of A.
Add it to the end of C.
Otherwise:
Remove first element of B.
Add it to the end of C.
If A or B still contains elements, add them to the end of C.
mergeSort(A):
if length of A is 1:
return A
Split A into two lists, L and R.
Q = merge(mergeSort(L), mergeSort(R))
return Q
Vielleicht aufklären, dass wird helfen, wo Sie hinwollen.
Wenn nicht, gibt es immer MergeSort bei wikipedia.
Weitere :
Ihnen helfen, sind hier einige Kommentare inline in Ihrem Code.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
// what do lHigh and rHigh represent?
int elements = (rHigh - lHigh +1) ;
int[] temp = new int[elements];
int num = left;
// what does this while loop do **conceptually**?
while ((left <= lHigh) && (right <= rHigh)){
if (a[left] <= a[right]) {
// where is 'pos' declared or defined?
temp[pos] = a[left];
// where is leftLow declared or defined? Did you mean 'left' instead?
leftLow ++;
}
else {
temp[num] = a[right];
right ++;
}
num++;
}
// what does this while loop do **conceptually**?
while (left <= right){
// At this point, what is the value of 'num'?
temp[num] = a[left];
left += 1;
num += 1;
}
while (right <= rHigh) {
temp[num] = a[right];
right += 1;
num += 1;
}
// Maybe you meant a[i] = temp[i]?
for (int i=0; i < elements; i++){
// what happens if rHigh is less than elements at this point? Could
// rHigh ever become negative? This would be a runtime error if it did
a[rHigh] = temp[rHigh];
rHigh -= 1;
}
Ich bin zu sein absichtlich vage, so denken Sie über den Algorithmus. Versuchen Sie, Ihre eigenen Kommentare in den Code einzufügen. Wenn Sie schreiben, was konzeptionell geschieht, dann können Sie nicht brauchen Stack-Überlauf:)
Meine Gedanken hier sind, dass Sie das nicht richtig implementieren. Dies liegt daran, es sieht aus wie Sie nur die Elemente des Arrays zu berühren nur einmal (oder in der Nähe nur einmal). Das heißt, Sie haben ein Worst-Case-Szenario von O (N) allgemein Sortierung mindestens O(N * log N) nimmt und aus was ich weiß, sind die einfacheren Versionen von Mergesort tatsächlich O(N^2).
Mehr:
In der stark vereinfachteste Implementierung von Mergesort, würde ich erwarten, dass irgendeine Art von Rekursion im MergeSort () Methode. Dies liegt daran, Mergesort im Allgemeinen rekursiv definiert ist. Es gibt Möglichkeiten, diese iterativ unter Verwendung für und While-Schleifen zu tun, aber ich es als Lernwerkzeug definitiv nicht empfehlen, bis Sie es rekursiv erhalten.
Ehrlich gesagt, ich schlage vor, entweder meinen Pseudo-Code oder den Pseudo-Code nimmt Sie in einem Wikipedia-Artikel finden können dies zu implementieren und mit dem Code von vorn beginnen. Wenn Sie das tun und es nicht richtig noch funktionieren, per Post hier und wir werden Ihnen die Knicke trainieren helfen.
Cheers!
Und schließlich:
// Precondition: array[left..lHigh] is sorted and array[right...rHigh] is sorted.
// Postcondition: array[left..rHigh] contains the same elements of the above parts, sorted.
public static void mergeSort(int[] array, int left, int lHigh, int right, int rHigh) {
// temp[] needs to be as large as the number of elements you're sorting (not half!)
//int elements = (rHigh - lHigh +1) ;
int elements = rHigh - left;
int[] temp = new int[elements];
// this is your index into the temp array
int num = left;
// now you need to create indices into your two lists
int iL = left;
int iR = right;
// Pseudo code... when you code this, make use of iR, iL, and num!
while( temp is not full ) {
if( left side is all used up ) {
copy rest of right side in.
make sure that at the end of this temp is full so the
while loop quits.
}
else if ( right side is all used up) {
copy rest of left side in.
make sure that at the end of this temp is full so the
while loop quits.
}
else if (array[iL] < array[iR]) { ... }
else if (array[iL] >= array[iR]) { ... }
}
}
Andere Tipps
public class MergeSort {
public static void main(String[] args) {
int[] arr = {5, 4, 7, 2, 3, 1, 6, 2};
print(arr);
new MergeSort().sort(arr, 0, arr.length - 1);
}
private void sort(int[] arr, int lo, int hi) {
if (lo < hi) {
int mid = (lo + hi) / 2;
sort(arr, lo, mid); // recursive call to divide the sub-list
sort(arr, mid + 1, hi); // recursive call to divide the sub-list
merge(arr, lo, mid, hi); // merge the sorted sub-lists.
print(arr);
}
}
private void merge(int[] arr, int lo, int mid, int hi) {
// allocate enough space so that the extra 'sentinel' value
// can be added. Each of the 'left' and 'right' sub-lists are pre-sorted.
// This function only merges them into a sorted list.
int[] left = new int[(mid - lo) + 2];
int[] right = new int[hi - mid + 1];
// create the left and right sub-list for merging into original list.
System.arraycopy(arr, lo, left, 0, left.length - 1);
System.arraycopy(arr, mid + 1, right, 0, left.length - 1);
// giving a sentinal value to marking the end of the sub-list.
// Note: The list to be sorted is assumed to contain numbers less than 100.
left[left.length - 1] = 100;
right[right.length - 1] = 100;
int i = 0;
int j = 0;
// loop to merge the sorted sequence from the 2 sub-lists(left and right)
// into the main list.
for (; lo <= hi; lo++) {
if (left[i] <= right[j]) {
arr[lo] = left[i];
i++;
} else {
arr[lo] = right[j];
j++;
}
}
}
// print the array to console.
private static void print(int[] arr) {
System.out.println();
for (int i : arr) {
System.out.print(i + ", ");
}
}
}
Hier ist eine andere!
private static int[] mergeSort(int[] input){
if (input.length == 1)
return input;
int length = input.length/2;
int[] left = new int[length];
int[] right = new int[input.length - length];
for (int i = 0; i < length; i++)
left[i] = input[i];
for (int i = length; i < input.length; i++)
right[i-length] = input[i];
return merge(mergeSort(left),mergeSort(right));
}
private static int[] merge(int[] left, int[] right){
int[] merged = new int[left.length+right.length];
int lengthLeft = left.length;
int lengthRight = right.length;
while (lengthLeft > 0 && lengthRight > 0){
if (left[left.length - lengthLeft] < right[right.length - lengthRight]){
merged[merged.length -lengthLeft-lengthRight] = left[left.length - lengthLeft];
lengthLeft--;
}else{
merged[merged.length - lengthLeft-lengthRight] = right[right.length - lengthRight];
lengthRight--;
}
}
while (lengthLeft > 0){
merged[merged.length - lengthLeft] = left[left.length-lengthLeft];
lengthLeft--;
}
while (lengthRight > 0){
merged[merged.length - lengthRight] = right[right.length-lengthRight];
lengthRight--;
}
return merged;
}
static void mergeSort(int arr[],int p, int r) {
if(p<r) {
System.out.println("Pass "+k++);
int q = (p+r)/2;
mergeSort(arr,p,q);
mergeSort(arr,q+1,r);
//System.out.println(p+" "+q+" "+r);
merge(arr,p,q,r);
}
}
static void merge(int arr[],int p,int q,int r) {
int temp1[],temp2[];
//lower limit array
temp1 = new int[q-p+1];
//upper limit array
temp2 = new int[r-q];
for(int i=0 ; i< (q-p+1); i++){
temp1[i] = arr[p+i];
}
for(int j=0; j< (r-q); j++){
temp2[j] = arr[q+j+1];
}
int i = 0,j=0;
for(int k=p;k<=r;k++){
// This logic eliminates the so called sentinel card logic mentioned in Coreman
if(i!= temp1.length
&& (j==temp2.length || temp1[i] < temp2[j])
) {
arr[k] = temp1[i];
// System.out.println(temp1[i]);
i++;
}
else {
//System.out.println(temp2[j]);
arr[k] = temp2[j];
j++;
}
}
}
>
Merge Sort Mit Sentinel
Diese Codes funktionieren völlig in Ordnung.
public void mergeSort(int a[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
public void merge(int a[], int low, int mid, int high) {
int n1 = mid - low + 1;// length of an array a1
int n2 = high - mid; // length of an array a2
int a1[] = new int[n1 + 1];
int a2[] = new int[n2 + 1];
int lowRange = low;
for (int i = 0; i < n1; i++) {
a1[i] = a[lowRange];
lowRange++;
}
for (int j = 0; j < n2; j++) {
a2[j] = a[mid + j + 1];
}
a1[n1] = Integer.MAX_VALUE; // inserting sentinel at the end of array a1
a2[n2] = Integer.MAX_VALUE; // inserting sentinel at the end of array a2
int i = 0;
int j = 0;
int k = low;
for (k = low; k <= high; k++) {
if (a1[i] >= a2[j]) {
a[k] = a2[j];
j++;
} else {
a[k] = a1[i];
i++;
}
}
if (a2.length >= a1.length) {
for (int ab = k; ab < a2.length; ab++) {
a[k] = a2[ab];
k++;
}
} else if (a1.length >= a2.length) {
for (int ab = k; ab < a1.length; ab++) {
a[k] = a1[ab];
k++;
}
}
}
Hier ist eine andere Alternative:
public class MergeSort {
public static void merge(int[]a,int[] aux, int f, int m, int l) {
for (int k = f; k <= l; k++) {
aux[k] = a[k];
}
int i = f, j = m+1;
for (int k = f; k <= l; k++) {
if(i>m) a[k]=aux[j++];
else if (j>l) a[k]=aux[i++];
else if(aux[j] > aux[i]) a[k]=aux[j++];
else a[k]=aux[i++];
}
}
public static void sort(int[]a,int[] aux, int f, int l) {
if (l<=f) return;
int m = f + (l-f)/2;
sort(a, aux, f, m);
sort(a, aux, m+1, l);
merge(a, aux, f, m, l);
}
public static int[] sort(int[]a) {
int[] aux = new int[a.length];
sort(a, aux, 0, a.length-1);
return a;
}
}
Hier ist ein einfacher Mergesort-Algorithmus in Java:
Guter Tipp: Verwenden Sie immer int middle = low + (high-low)/2 statt int middle = (low + high)/2.
public static int[] mergesort(int[] arr) {
int lowindex = 0;
int highindex = arr.length-1;
mergesort(arr, lowindex, highindex);
return arr;
}
private static void mergesort(int[] arr, int low, int high) {
if (low == high) {
return;
} else {
int midIndex = low + (high-low)/2;
mergesort(arr, low, midIndex);
mergesort(arr, midIndex + 1, high);
merge(arr, low, midIndex, high);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] left = new int[mid-low+2];
for (int i = low; i <= mid; i++) {
left[i-low] = arr[i];
}
left[mid-low+1] = Integer.MAX_VALUE;
int[] right = new int[high-mid+1];
for (int i = mid+1; i <= high; i++) {
right[i-mid-1] = arr[i];
}
right[high - mid] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for (int k = low; k <= high; k++) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
}
}
Paket com;
public class Test {
int count = 0;
public static void main(String[] args) {
int a[] = {1,3,5,7,9,10,14,15,16};
int b[] = {2,4,6,8,11,12,13,17,18};
int sizec = a.length+b.length;
int c[] = new int[sizec];
int i=0;int j=0;int k=0;
while(k<sizec)
{
if(i == a.length || j == b.length)
{
int sizeDifference = 0;
if(i==a.length)
{
sizeDifference = b.length-j;
for (int m =0;m<sizeDifference;m++)
{
c[k] = b[m+j];
if(k<sizec)
k++;
}
break;
}
else if(j== b.length)
{
sizeDifference = a.length-i;
for (int m =0;m<sizeDifference;m++)
{
c[k] = a[m+i];
if(k<sizec)
k++;
}
break;
}
else
{
c[k] = b[j];
j++;
}
}
if(i < a.length || j < b.length )
{
if(a[i]>b[j] )
{
c[k]=b[j];
j++;
}
else if(a[i]<b[j])
{
c[k]=a[i];
i++;
}
}
k++;
}
for(int l=0;l<sizec;l++)
{
System.out.println(c[l]);
}
}
}
