Question

In order to practice divide and conquer algorithms, we will apply the idea to sorting and other tasks. Your goal is to rst create a method that uses the merge concept to integrate two queue ADTs. Second, you will re-implement mergesort from scratch to get a better understanding of its divide and conquer (D&C) nature. Lastly, you will create an O(nlogn) algorithm for shuing an input array. Divide and Conquer algorithms are conceptually similar to the recursive programming technique we saw earlier in the course. The idea is to break apart a problem into multiple (large) pieces. For example, the rst half of an array, and then the second half of an array. In terms of recursion, we might say that the sub-problem is size n=2. This contrasts with the standard n ???? 1 size of many recursive algorithms, where only a single piece of work is accomplished during each call. In general, D&C algorithms require multiple recursive calls while simple recursion, like taking a sum or displaying a list, requires only a single call. D&C algorithms are often more complicated to write than

Answer 1

Check the explanation

Step-by-step explanation:

// File: BaseMerging.java

// BaseMerging class implementation

import java.util.Random;

public class BaseMerging

{

/**

* Entry point for sample output.

*

* param args the command line arguments

*/

public static void main(String[] args)

{

Queue q1 = new ListQueue();

q1.enqueue("T");

q1.enqueue("R");

q1.enqueue("O");

q1.enqueue("L");

q1.enqueue("E");

// print the elements of q1

System.out.println("q1: " + q1);

Queue q2 = new ListQueue();

q2.enqueue("X");

q2.enqueue("S");

q2.enqueue("P");

q2.enqueue("M");

q2.enqueue("E");

q2.enqueue("A");

// print the elements of q2

System.out.println("q2: " + q2);

// Q1

// call the mergeQueues method on q1 and q2

Queue merged = mergeQueues(q1, q2);

// print the elements of mergeQueues(q1, q2)

System.out.println("mergeQueues(q1, q2): " + merged.toString());

// Q2

Comparable[] a = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};

// print the elements of a[]

System.out.print(" a: ");

show(a);

// call the sort method on a[]

sort(a);

// print the elements of sort(a)

System.out.print("sort(a): ");

show(a);

// Q3

String[] b = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};

// print the elements of b[]

System.out.print(" b: ");

show(b);

// call the shuffle method on b[]

shuffle(b);

// print the elements of shuffle(b)

System.out.print("shuffle(b): ");

show(b);

// call the shuffle method on b[] again

shuffle(b);

// print the elements of shuffle(b)

System.out.print("shuffle(b): ");

show(b);

} // end of main method

// Answer for Q1

// mergeQueues method implementation

public static Queue mergeQueues(Queue q1, Queue q2)

{

Queue result = new ListQueue();

while(!q1.isEmpty() && !q2.isEmpty())

{

if(less((Comparable) q1.front(), (Comparable) q2.front()))

{

} // end of mergeQueues method

// Answer for Q2

// sort method implementation

public static void sort(Comparable[] a)

{

Comparable[] b = mergesort(a);

for(int i = 0; i < b.length; i++)

{

a[i] = b[i];

}

} // end of sort method

// mergesort method implementation

public static Comparable[] mergesort(Comparable[] a)

{

if(a.length < 2)

return a;

int midPos = a.length / 2;

Comparable[] firstHalf = new Comparable[midPos];

Comparable[] secondHalf = new Comparable[a.length - midPos];

for(int i = 0; i < midPos; i++)

{

firstHalf[i] = a[i];

}

for(int i = midPos, j = 0; i < a.length; i++, j++)

{

secondHalf[j] = a[i];

}

firstHalf = mergesort(firstHalf);

secondHalf = mergesort(secondHalf);

a = merge(firstHalf, secondHalf);

return a;

} // end of mergesort method

// merge method implementation

public static Comparable[] merge(Comparable[] a, Comparable[] b)

{

Comparable[] result = new Comparable[a.length + b.length];

int i = 0; // for a[]

int j = 0; // for b[]

int k = 0; // for result[]

while(i < a.length || j < b.length)

{

if(i < a.length && j < b.length)

{

if(((Comparable) a[i]).compareTo(b[j]) < 0)

{

result[k] = a[i];

k++;

i++;

}

else if(((Comparable) a[i]).compareTo(b[j]) > 0)

{

result[k] = b[j];

k++;

j++;

}

else

{

result[k] = a[i];

k++;

i++;

result[k] = b[j];

k++;

j++;

}

}

else if(i < a.length && j >= b.length)

{

result[k] = a[i];

k++;

i++;

}

else if(j < b.length && i >= a.length)

{

result[k] = b[j];

k++;

j++;

}

}

return result;

} // end of merge method

// Answer for Q3

// shuffle method implementation

public static void shuffle(Object[] a)

{

shuffle(a, 0, a.length - 1);

} // end of shuffle method

// recursive shuffle method implementation

private static void shuffle(Object[] a, int first, int last)

{

if(first > last)

return;

int middle = (first + last) / 2;

int randIndex = (new Random()).nextInt(a.length);

Object middleElement = a[middle];

a[middle] = a[randIndex];

a[randIndex] = middleElement;

// recursive calls

shuffle(a, first, middle - 1);

shuffle(a, middle + 1, last);

} // end of recursive shuffle method

// sorting helper from text

private static boolean less(Comparable v, Comparable w)

{

return v.compareTo(w) < 0;

}

// sorting helper from text

private static void show(Comparable[] a)

{

for(Comparable a1 : a)

System.out.print(a1 + " ");

System.out.println();

}

// sorting helper from text

public static boolean isSorted(Comparable[] a)

{

for(int i = 1; i < a.length; i++)

if(less(a[i], a[i - 1]))

return false;

return true;

}

} // end of BaseMerging class