I\'m making a mergesort method and when I output the results come out weird pack
ID: 3710605 • Letter: I
Question
I'm making a mergesort method and when I output the results come out weird
package mergesort;
public class MergeSort
{
/* Precondition: Every indexed variable of the array a has a value.
Postcondition: a[0] <= a[1] <=.. <= a[a.length - 1].
*/
public static void sort(int[] a)
{
if (a.length >= 2)
{
int halfLength = a.length / 2;
int [] firstHalf = new int[halfLength];
int [] lastHalf = new int[a.length - halfLength];
divide(a, firstHalf, lastHalf);
sort(firstHalf);
sort(lastHalf);
merge(a, firstHalf, lastHalf);
}
//Else do nothing. a.length == 1, so a is sorted
}
/*Precondition: a.length = firstHalf.length + lasHalf.length
Postcondition: All the elements of a are divided
between the arrays of firstHalf and lastHalf.
*/
private static void divide(int[] a, int[] firstHalf, int[] lastHalf)
{
for (int i = 0; i < firstHalf.length; i++)
firstHalf[i] = a[i];
for (int i = 0; i < lastHalf.length; i++)
lastHalf[i] = a[firstHalf.length + i];
}
/*Precondition: Arrays firstHalf and lastHalf are sorted from
smallest to largest; a.length = firstHalf.length + lastHalf.length
Postcondition: Array a contains all the values from firstHalf
and lastHalf and is sorted from smallest to largest.
*/
private static void merge(int[] a, int[] firstHalf, int[] lastHalf)
{
int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
while ((firstHalfIndex < firstHalf.length) &&
(lastHalfIndex < lastHalf.length))
{
if (firstHalf[firstHalfIndex] < lastHalf[lastHalfIndex])
{
a[aIndex] = firstHalf[firstHalfIndex];
firstHalfIndex++;
}
else
{
a[aIndex] = firstHalf[firstHalfIndex];
lastHalfIndex++;
}
aIndex++;
}
/*At least one of firstHalf and lastHalf has been
completely copied to a.
*/
//Copy rest of firstHalf,if any.
while (firstHalfIndex < firstHalf.length)
{
a[aIndex] = firstHalf[firstHalfIndex];
aIndex++;
firstHalfIndex++;
}
//Copy rest of lastHalf, if any.
while (lastHalfIndex < lastHalf.length)
{
a[aIndex] = lastHalf[lastHalfIndex];
aIndex++;
lastHalfIndex++;
}
}
}
package mergesort;
public class MergeSortDemo
{
public static void main(String[] args)
{
int[] anArray = {7, 5, 11, 2, 16, 4, 18, 14, 12, 30};
System.out.println("Array values before sorting;");
for (int i = 0; i < anArray.length; i++)
System.out.print(anArray[i] + " ");
System.out.println();
MergeSort.sort(anArray);
System.out.println("Array values after sorting:");
for (int i = 0; i < anArray.length; i++)
System.out.print(anArray[i] + " ");
System.out.println();
}
}
When I try to run the demo I get this output:
Array values before sorting;
7 5 11 2 16 4 18 14 12 30
Array values after sorting:
7 7 7 11 11 16 18 18 18 30
i can't figure out where my problem is.
Explanation / Answer
class MergeSort
{
/* Precondition: Every indexed variable of the array a has a value.
Postcondition: a[0] <= a[1] <=.. <= a[a.length - 1].
*/
public static void display(int[] anArray)
{
for (int i = 0; i < anArray.length; i++)
System.out.print(anArray[i] + " ");
System.out.println();
}
public static void sort(int[] a)
{
if (a.length >= 2)
{
int halfLength = a.length / 2;
int [] firstHalf = new int[halfLength];
int [] lastHalf = new int[a.length - halfLength];
divide(a, firstHalf, lastHalf);
sort(firstHalf);
sort(lastHalf);
merge(a, firstHalf, lastHalf);
}
//Else do nothing. a.length == 1, so a is sorted
}
/*Precondition: a.length = firstHalf.length + lasHalf.length
Postcondition: All the elements of a are divided
between the arrays of firstHalf and lastHalf.
*/
private static void divide(int[] a, int[] firstHalf, int[] lastHalf)
{
for (int i = 0; i < firstHalf.length; i++)
firstHalf[i] = a[i];
for (int i = 0; i < lastHalf.length; i++)
lastHalf[i] = a[firstHalf.length + i];
}
/*Precondition: Arrays firstHalf and lastHalf are sorted from
smallest to largest; a.length = firstHalf.length + lastHalf.length
Postcondition: Array a contains all the values from firstHalf
and lastHalf and is sorted from smallest to largest.
*/
private static void merge(int[] a, int[] firstHalf, int[] lastHalf)
{
int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
while ((firstHalfIndex < firstHalf.length) &&
(lastHalfIndex < lastHalf.length))
{
if (firstHalf[firstHalfIndex] < lastHalf[lastHalfIndex])
{
a[aIndex] = firstHalf[firstHalfIndex];
firstHalfIndex++;
}
else
{
a[aIndex] = lastHalf[lastHalfIndex];//The problem was here what you had done wasfirstHalf[firstHalfIndex]
lastHalfIndex++;
}
aIndex++;
}
/*At least one of firstHalf and lastHalf has been
completely copied to a.
*/
//Copy rest of firstHalf,if any.
while (firstHalfIndex < firstHalf.length)
{
a[aIndex] = firstHalf[firstHalfIndex];
aIndex++;
firstHalfIndex++;
}
//Copy rest of lastHalf, if any.
while (lastHalfIndex < lastHalf.length)
{
a[aIndex] = lastHalf[lastHalfIndex];
aIndex++;
lastHalfIndex++;
}
}
}
public class Student
{
public static void main(String[] args)
{
int[] anArray = {7, 5, 11, 2, 16, 4, 18, 14, 12, 30};
System.out.println("Array values before sorting;");
for (int i = 0; i < anArray.length; i++)
System.out.print(anArray[i] + " ");
System.out.println();
MergeSort.sort(anArray);
System.out.println("Array values after sorting:");
for (int i = 0; i < anArray.length; i++)
System.out.print(anArray[i] + " ");
System.out.println();
}
}
The code given above is corrected one.
What you had done was firstHalf[firstHalfIndex] in the else as well in the merge method whereas it should have been a[aIndex] = lastHalf[lastHalfIndex];
Do give a thumbs up
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.