NEED HELP WITH THIS PROBLEM. A class wants to decide at run-time what algorithm

Question

NEED HELP WITH THIS PROBLEM.

A class wants to decide at run-time what algorithm it should use to sort an array. Three sort algorithms are already available: BubbleSort, QuickSort, and InsertionSort. Use strategy design patter to solve this problem. For the sort() method, you don't have to really implement, just print a message showing the method is called, e.g., "Using bubble sort". Draw the class diagram of your design. The classes and interfaces are: Sorting, SortAlgorithms, BubbleSort, QuickSort, and InsertionSort. Also write a driver program to demonstrate changing algorithm at run-time

Explanation / Answer

Bubble sort

The insertion sort only passes through the array once. Therefore it is a very fast and efficient sorting algorithm with small arrays. (The efficiency is lost however with large amounts of data.)

The sort works as follows: the array is split into two (virtual) sub-arrays. (With virtual I mean that the array is not really split.) The first sub-array is considered to be the sorted array. The elements of the second sub-array will be inserted into the first sub-array at the right position.

quick sort

As a first step, Quick Sort chooses as pivot one of the items in the array to be sorted. Then array is then partitioned on either side of the pivot. Elements that are less than or equal to pivot will move toward the left and elements that are greater than or equal to pivot will move toward the right.

n a standard algorithms course we are taught that quicksort is O(nlogn) on average and O(n2) in the worst case. At the same time, other sorting algorithms are studied which are O(nlogn) in the worst case (like mergesort and heapsort), and even linear time in the best case (like bubblesort) but with some additional needs of memory.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.