三路归并排序问题未能正确排序

huangapple go评论78阅读模式
英文:

Three way merge sort problem not sorting correctly

问题

我一直在研究这个三路归并排序算法,它是基于我的普通归并排序代码的基础上编写的;然而,它没有正确排序,所以我认为我的代码中可能有一个小错误。请帮帮我好吗?我已经花了3个小时来查找问题,但是找到问题证明是困难的。

public class TriMergeSort {

	void merge(int arr[], int low, int mid1, int mid2, int high) { 
		int sizeA = mid1 - low + 1; 
		int sizeB =  mid2 - mid1;
		int sizeC = high - mid2;

		int A[] = new int[sizeA]; 
		int B[] = new int[sizeB]; 
		int C[] = new int[sizeC];

		for (int i = 0; i < sizeA; i++) 
			A[i] = arr[low + i]; 
		for (int j = 0; j < sizeB; j++) 
			B[j] = arr[mid1 + j + 1]; 
		for (int x = 0; x < sizeC; x++) 
			C[x] = arr[mid2 + x + 1];

		int i = 0, j = 0, x = 0; 
		int k = low; 
		
		while (i < sizeA && j < sizeB && x < sizeC) {
			
			if (A[i] < B[j] && A[i] < C[x]) { 
				arr[k] = A[i]; 
				i++; 
			} else
		    if (A[i] >= B[j] && B[j] < C[x]) { 
				arr[k] = B[j]; 
				j++; 
			} else
			if (A[i] > C[x] && B[j] >= C[x]) { 
				arr[k] = C[x]; 
				x++; 
			} 
			k++; 
		} 

		while (i < sizeA) { 
			arr[k] = A[i]; 
			i++; 
			k++; 
		} 

		while (j < sizeB) { 
			arr[k] = B[j]; 
			j++; 
			k++; 
		} 
		
		while (x < sizeC) { 
			arr[k] = C[x]; 
			x++; 
			k++; 
		}
	} 

	void sort(int arr[], int low, int high) { 
		
		if (low < high) {  
			int mid1 = low + ((high - low) / 3); 
	        int mid2 = low + 2 * ((high - low) / 3) + 1;

			sort(arr, low, mid1); 
			sort(arr, mid1 + 1, mid2); 
			sort(arr, mid2 + 1, high);

			merge(arr, low, mid1, mid2, high); 
		} 
	} 

	static void print(int arr[]) { 
		int n = arr.length; 
		for (int i = 0; i < n; ++i) 
			System.out.print(arr[i] + " "); 
		System.out.println(); 
	} 

	public static void main(String args[]) { 
		int arr[] = { 15, 2, 6, 7, 55, 0, 28, 41, 12 }; 

		TriMergeSort test = new TriMergeSort(); 
		test.sort(arr, 0, arr.length - 1); 

		print(arr); 
	}
}
英文:

I've been working on this three way merge sort algorithm which I based off of my normal merge sort code; however, it isn't sorting correctly and so I believe there might be a minor mistake in my code. Any help please? I've been looking into the code for 3 hours trying to find the problem but it has proven difficult.

public class TriMergeSort {
void merge(int arr[], int low, int mid1, int mid2, int high) { 
int sizeA = mid1 - low + 1; 
int sizeB =  mid2 - mid1;
int sizeC = high - mid2;
int A[] = new int[sizeA]; 
int B[] = new int[sizeB]; 
int C[] = new int[sizeC];
for (int i = 0; i &lt; sizeA; i++) 
A[i] = arr[low + i]; 
for (int j = 0; j &lt; sizeB; j++) 
B[j] = arr[mid1 + j + 1]; 
for (int x = 0; x &lt; sizeC; x++) 
C[x] = arr[mid2 + x + 1];
int i = 0, j = 0, x = 0; 
int k = low; 
while (i &lt; sizeA &amp;&amp; j &lt; sizeB &amp;&amp; x &lt; sizeC) {
if (A[i] &lt; B[j] &amp;&amp; A[i] &lt; C[x]) { 
arr[k] = A[i]; 
i++; 
} else
if (A[i] &gt;= B[j] &amp;&amp; B[j] &lt; C[x]) { 
arr[k] = B[j]; 
j++; 
} else
if (A[i] &gt; C[x] &amp;&amp; B[j] &gt;= C[x]) { 
arr[k] = C[x]; 
x++; 
} 
k++; 
} 
while (i &lt; sizeA) { 
arr[k] = A[i]; 
i++; 
k++; 
} 
while (j &lt; sizeB) { 
arr[k] = B[j]; 
j++; 
k++; 
} 
while (x &lt; sizeC) { 
arr[k] = C[x]; 
x++; 
k++; 
}
} 
void sort(int arr[], int low, int high) { 
if (low &lt; high) {  
int mid1 = low + ((high - low) / 3); 
int mid2 = low + 2 * ((high - low) / 3) + 1;
sort(arr, low, mid1); 
sort(arr, mid1 + 1, mid2); 
sort(arr, mid2 + 1, high);
merge(arr, low, mid1, mid2, high); 
} 
} 
static void print(int arr[]) { 
int n = arr.length; 
for (int i = 0; i &lt; n; ++i) 
System.out.print(arr[i] + &quot; &quot;); 
System.out.println(); 
} 
public static void main(String args[]) { 
int arr[] = { 15, 2, 6, 7, 55, 0, 28, 41, 12 }; 
TriMergeSort test = new TriMergeSort(); 
test.sort(arr, 0, arr.length - 1); 
print(arr); 
}
} 

答案1

得分: 2

以下是翻译好的代码部分:

public class TriMergeSort {

    void merge(int arr[], int low, int mid1, int mid2, int high) { 
        int sizeA = mid1 - low; 
        int sizeB = mid2 - mid1;
        int sizeC = high - mid2;

        int A[] = new int[sizeA]; 
        int B[] = new int[sizeB]; 
        int C[] = new int[sizeC];

        for (int i = 0; i < sizeA; i++) 
            A[i] = arr[low + i]; 
        for (int j = 0; j < sizeB; j++) 
            B[j] = arr[mid1 + j]; 
        for (int k = 0; k < sizeC; k++) 
            C[k] = arr[mid2 + k];

        int i = 0, j = 0, k = 0;
        
        while (low < high) {
            if (i < sizeA && (j >= sizeB || A[i] <= B[j])) {
                if (k >= sizeC || A[i] <= C[k]) {
                    arr[low++] = A[i++];
                } else {
                    arr[low++] = C[k++];
                }
            } else {
                if (j < sizeB && (k >= sizeC || B[j] <= C[k])) {
                    arr[low++] = B[j++];
                } else {
                    arr[low++] = C[k++];
                }
            }
        } 
    } 

    void sort(int arr[], int low, int high) { 
        if (high - low >= 2) {  
            int mid1 = low + (high - low) / 3; 
            int mid2 = low + (high - low) * 2 / 3;
            sort(arr, low, mid1); 
            sort(arr, mid1, mid2); 
            sort(arr, mid2, high);
            merge(arr, low, mid1, mid2, high); 
        } 
    } 

    static void print(int arr[]) { 
        int n = arr.length; 
        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println(); 
    } 

    public static void main(String args[]) { 
        int arr[] = { 15, 2, 6, 7, 55, 0, 28, 41, 12 }; 
        TriMergeSort test = new TriMergeSort(); 
        test.sort(arr, 0, arr.length); 
        print(arr); 
    }
}

最后两段更简化的 while 循环部分:

while (low < high) {
    arr[low++] = (i < sizeA && (j >= sizeB || A[i] <= B[j])) ?
        ((k >= sizeC || A[i] <= C[k]) ? A[i++] : C[k++]) :
        (j < sizeB && (k >= sizeC || B[j] <= C[k])) ? B[j++] : C[k++];
}
英文:

The code posted in the question works fine. You did not post the 3-way merge code you have problems with.

Note that instead of passing high as the index to the last item in the slice to sort, you should pass the index of the first element beyond the slice. This allows for simpler code, without confusing and error prone +1/-1 adjustments.

Here is a modified version:

public class MergeSort { 

    void merge(int arr[], int low, int mid, int high) { 
        int sizeA = mid - low; 
        int sizeB = high - mid; 

        int A[] = new int[sizeA]; 
        int B[] = new int[sizeB]; 

        for (int i = 0; i &lt; sizeA; i++) 
            A[i] = arr[low + i]; 
        for (int j = 0; j &lt; sizeB; j++) 
            B[j] = arr[mid + j]; 

        int i = 0, j = 0; 
        int k = low; 
        
        while (i &lt; sizeA &amp;&amp; j &lt; sizeB) { 
            if (A[i] &lt;= B[j]) { 
                arr[k++] = A[i++]; 
            } else { 
                arr[k++] = B[j++]; 
            } 
        } 

        while (i &lt; sizeA) {
            arr[k++] = A[i++];
        } 

        while (j &lt; sizeB) { 
            arr[k++] = B[j++];
        } 
    } 

    void sort(int arr[], int low, int high) { 
        if (high - low &gt;= 2) {  
            int mid = low + (high - low) / 2; 
            sort(arr, low, mid); 
            sort(arr, mid, high); 
            merge(arr, low, mid, high); 
        } 
    } 

    static void print(int arr[]) { 
        int n = arr.length; 
        for (int i = 0; i &lt; n; ++i) {
            System.out.print(arr[i] + &quot; &quot;);
        }
        System.out.println(); 
    } 

    public static void main(String args[]) { 
        int arr[] = { 15, 2, 6, 7, 55, 0, 28, 41, 12, 10, 59 }; 
        MergeSort test = new MergeSort(); 
        test.sort(arr, 0, arr.length); 
        print(arr); 
    } 
}

To convert this into a 3-way merge version, sort3 must follow these steps:

  • split the range into 3 slices instead of 2. The first slice runs from low to mid1 = low + (high - low)/3 excluded, the second from mid1 to mid2 = low + (high - low)*2/3 excluded and the third from mid2 to high excluded.
  • sort each of the 3 subslices recursively
  • call merge3(arr, low, mid1, mid2, high)
    • make copies of the 3 subslices
    • write a loop for 3 index values running the 3 slices until one of them is exhausted
    • write 3 loops for the 2 remaining slices (A and B) or (B and C) or (A and C),
    • write 3 loops to copy the remaining elements from the remaining slice, A, B or C

EDIT: the merge function in your TriMergeSort class is missing the 3 loops that merge 2 slices once one of the 3 initial slices is exhausted. This explains why the array does not get properly sorted. After the 3-way merge loop, you should have:

    while (i &lt; sizeA &amp;&amp; j &lt; sizeB) {
...
}
while (i &lt; sizeA &amp;&amp; x &lt; sizeC) {
...
}
while (j &lt; sizeB &amp;&amp; x &lt; sizeC) {
...
}

To avoid all these repeated loops, you could combine tests on the index values into a single loop body:

public class TriMergeSort {

    void merge(int arr[], int low, int mid1, int mid2, int high) { 
        int sizeA = mid1 - low; 
        int sizeB = mid2 - mid1;
        int sizeC = high - mid2;

        int A[] = new int[sizeA]; 
        int B[] = new int[sizeB]; 
        int C[] = new int[sizeC];

        for (int i = 0; i &lt; sizeA; i++) 
            A[i] = arr[low + i]; 
        for (int j = 0; j &lt; sizeB; j++) 
            B[j] = arr[mid1 + j]; 
        for (int k = 0; k &lt; sizeC; k++) 
            C[k] = arr[mid2 + k];

        int i = 0, j = 0, k = 0;
        
        while (low &lt; high) {
            if (i &lt; sizeA &amp;&amp; (j &gt;= sizeB || A[i] &lt;= B[j])) {
                if (k &gt;= sizeC || A[i] &lt;= C[k]) {
                    arr[low++] = A[i++];
                } else {
                    arr[low++] = C[k++];
                }
            } else {
                if (j &lt; sizeB &amp;&amp; (k &gt;= sizeC || B[j] &lt;= C[k])) {
                    arr[low++] = B[j++];
                } else {
                    arr[low++] = C[k++];
                }
            }
        } 
    } 

    void sort(int arr[], int low, int high) { 
        if (high - low &gt;= 2) {  
            int mid1 = low + (high - low) / 3; 
            int mid2 = low + (high - low) * 2 / 3;
            sort(arr, low, mid1); 
            sort(arr, mid1, mid2); 
            sort(arr, mid2, high);
            merge(arr, low, mid1, mid2, high); 
        } 
    } 

    static void print(int arr[]) { 
        int n = arr.length; 
        for (int i = 0; i &lt; n; ++i) {
            System.out.print(arr[i] + &quot; &quot;);
        }
        System.out.println(); 
    } 

    public static void main(String args[]) { 
        int arr[] = { 15, 2, 6, 7, 55, 0, 28, 41, 12 }; 
        TriMergeSort test = new TriMergeSort(); 
        test.sort(arr, 0, arr.length); 
        print(arr); 
    }
}

The while loop above can be further simplified but somewhat less readable as:

    while (low &lt; high) {
if (i &lt; sizeA &amp;&amp; (j &gt;= sizeB || A[i] &lt;= B[j])) {
arr[low++] = (k &gt;= sizeC || A[i] &lt;= C[k]) ? A[i++] : C[k++];
} else {
arr[low++] = (j &lt; sizeB &amp;&amp; (k &gt;= sizeC || B[j] &lt;= C[k])) ? B[j++] : C[k++];
}
} 

And even one step further:

    while (low &lt; high) {
arr[low++] = (i &lt; sizeA &amp;&amp; (j &gt;= sizeB || A[i] &lt;= B[j])) ?
((k &gt;= sizeC || A[i] &lt;= C[k]) ? A[i++] : C[k++]) :
(j &lt; sizeB &amp;&amp; (k &gt;= sizeC || B[j] &lt;= C[k])) ? B[j++] : C[k++];
} 

huangapple
  • 本文由 发表于 2020年9月30日 00:40:11
  • 转载请务必保留本文链接:https://go.coder-hub.com/64123996.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定