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

Check the explanation

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

b.. i believe would be the right one sorry if im wrong.

a  social news website  is an  internet  website  that features  user-posted stories. such stories are ranked based on popularity, as voted on by other users of the site or by website administrators. users typically comment online on the news posts and these comments may also be ranked in popularity. since their emergence with the birth of  web 2.0, social news sites have been used to link many types of information, including news, humor, support, and discussion. all such websites allow the users to submit content and each site differs in how the content is moderated. on the  slashdot  and  fark  websites,  administrators  decide which articles are selected for the front page. on  reddit  and  digg, the articles that get the most votes from the community of users will make it to the front page. many social news websites also feature an online comment system, where users discuss the issues raised in an article. some of these sites have also applied their voting system to the comments, so that the most popular comments are displayed first. some social news websites also have a  social networking  function, in that users can set up a user profile and follow other users' online activity on the website.