Write acomplete Java program to implement Quick and Merge sortingalgorithms. Input an arrayof double data type, and
Fantastic news! We've Found the answer you've been seeking!
Question:
Write acomplete Java program to implement Quick and Merge sortingalgorithms.
Input an arrayof double data type, and choice of sorting algorithm to be used,from the user.
Display thesorted array to the user.
Runthe program and display output samples [2Marks]
(Hint Refer toLab 9)
Transcribed Image Text:
LAB 09: Recursion Objectives: To implement some of the recursive algorithms and analyze their complexity. 1. Recursion We have seen so far that a function, such as main, can call another function to perform some computation. In Java, a function can also call itself. Such types of functions are called recursive functions. A function, f, is also said to be recursive if it calls another function, g, which in turn calls f. Although it may sound strange for a function to call itself, it is in fact not so strange, as many mathematical functions are defined recursively... e.g., factorial function: n! = Although less efficient than iterative functions (using loops) due to overhead in function calls, in many cases, recursive functions provide a more natural and simple solutions. Thus, recursion is a powerful tool in problem solving and programming. Problems that can be solved using recursion have the following characteristics: • One or more simple cases of the problem have a direct and easy answer - also called base cases. Example: 0! = 1. The other cases can be re-defined in terms of a similar but smaller problem - recursive cases. Example: n! =n(n-1)! By applying this re-definition process, each time the recursive cases will move closer and eventually reach the base case. Example: n! → (n-1)! → (n-2)! → ... 1!, 0!. The strategy in recursive solutions is called divide-and-conquer. The idea is to keep reducing the problem size until it reduces to the simple case with obvious solution. size n problem } Recursive version int factorial (int n) { if n = 0, n* (n-1)! if n>0 if (n == 0) return 1; size n-1 problem size 1 problem //base case Example: Recursive Factorial The following code shows the recursive and iterative versions of the factorial function: //recursive case else return n*factorial (n-1); size n-2 problem size 1 problem } Iterative version int factorial (int n) { size 2 problem size 1 problem size 1 problem int i, product=1; for (i=n; i>1; -1) product=product * i; return product; size 1 problem In recursive functions such as above: • The if branch is the base case, while the else branch is the recursive case. For the recursion to terminate, the recursive case must be moving closer to the base case. Tracing the Recursive Functions Executing recursive algorithms goes through two phases: Expansion in which the recursive step is applied until hitting the base step. factorial(4) = 4* factorial (3) = 4*(3* factorial (2)) = 4*(3* (2* factorial (1))) The following diagram from wikipedia shows the complete merge sort process for an example array (38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the size becomes 1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged. = 4*(3* (2*(1 * factorial (0)))) = 4*(3* (2 (11))) = 4*(3* (2*1)) 38 = 4*(3*2) = 4*6 = 24 CSE 202: DATA STRUCTURES Substitution in which the solution is constructed backwards starting with the base step. 2. Sorting Algorithms Call mergeSort (arr, m+1, r) 4. Merge the two halves sorted in step 2 and 3: Call merge (arr, 1, m, r) 38 27 Sorting algorithms rearrange the data in some order (ascending or descending order). Following are the two very common recursive algorithms for sorting. These numbers, indicate the order steps are prohich 27 i. Merge Sort Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, 1, m, r) is key process that assumes that arr[1..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following C implementation for details. MergeSort (arr [], 1, r) If r > 1 1. Find the middle point to divide the array into two halves: middle m = (1+r)/2 2. Call merge Sort for first half: Call mergeSort (arr, 1, m) 3. Call mergeSort for second half: 27 Expansion phase 38 27 43 2 Substitution phase 8 10 جامعة حفر الباطن University of Hafr Al Batin College of Computer Science and Engineering (CCSE 38 27 43 39 82 10 27 30 9 982 10 12 02 9 82 16 9 10 82 19 82 15 7 10 27 30 43 02 20 10 10 10 18 17 Exercise # 1: Edit, compile and run the following code in Eclipse. /* Java program for Merge Sort */ public class MergeSort { 12 13. 14. 15. 16. 17. 34. 35. 36. 57. 37 50. 38. CSE 202: DATA STRUCTURES 59. 40. 40. 41. 42. Merges two of arr[]. 47. 48. // First subarray is void merge(int arr[], int 1, int m, int r) { // Find sizes of two subarrays to be merged int n1 = m - 1 + 1; int n2 = rm; /* Create temp arrays */ int L[] = new int [n1]; int R[] = new int [n2]; /*Copy data to temp arrays*/ for (int i=0; i 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. } } /* Copy remaining elements of R[] if any */ while (j < n2) { arr[k] = R[j]; } } // Main function that sorts arr[1..r] using merge() void sort(int arr[], int 1, int r) { if (1 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. } 95. } 96. /* contributed by Rajat Mishra: https://www.geeksforgeeks.org/merge-sort/ */ System.out.println( Given Array ); printArray(arr); MergeSort ob = new MergeSort(); ob.sort (arr, 0, arr.length-1); System.out.println( Sorted array ); printArray(arr); Given Array 12 11 13 5 6 7 Sorted array 567 11 12 13 ii. Quick Sort Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. 1. Always pick first element as pivot. 2. Always pick last element as pivot (implemented below) 3. Pick a random element as pivot. 4. Pick median as pivot. The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time. Page 4 of 7 /* low --> Starting index, high --> Ending index */ quickSort (arr [], low, high) { if (low high) { to Partition Algorithm: There can be many ways do partition, following pseudo code adopts the method given in CLRS book (Introduction to Algorithms by Cormen et. al.). The logic is simple, we start from the leftmost element and keep track of index of smaller (or equal to) elements as i. While traversing, if we find a smaller element, we swap current element with arr[i]. Otherwise we ignore current element. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. } 15. 16. /* pi is partitioning index, arr [pil is now at right place */ pi partition (arr, low, high); 1. 2. public class QuickSort 3. { 4. 17. 18. 19. 20. quickSort (arr, low, pi 1); // Before pi quickSort (arr, pi + 1, high); // After pi 21. 22. 23. 24. Exercise # 2: Edit, compile and run the following code in Eclipse. Java program for implementation of QuickSort {10, 30, 40, (50) Partition around 50 {10, 30, 40} Partition around 40 (10, (30) Partition {10} around 30 { (10, 80, 30, 90, 40, 50, (70) Partition around 70 (Last element) = for (int j-low; j CSE 202: DATA STRUCTURES 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. iii. arr[high] = temp; return i+1; } /* The main function that implements QuickSort() arr[] > Array to be sorted, low --> Starting index, high > Ending index */ void sort(int arr[], int low, int high) { if (low high) { } } /* pi is partitioning index, arr[pi] is now at right place */ int pi= partition (arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort (arr, pi+1, high); /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i CSE 202: DATA STRUCTURES Method Selection sort Insertion sort Merge sort Quick sort Examples of Algorithms and their big-O complexity Best Case Worst Case O(n²) O(n) O(n log n) O(n log n) O(n²) O(n²) O(n log n) O(n²) Page 6 of 7 Average Case O(n²) O(n²) O(n log n) O(n log n) جامعة حفر الباطن University of Hofr Al Batin College of Computer Science and Engineering (CCSE Task 1: Write a complete Java program to implement above sorting algorithms. Input an array of double data type from user, and choice of sorting algorithm to be used. Display the sorted array to user. LAB 09: Recursion Objectives: To implement some of the recursive algorithms and analyze their complexity. 1. Recursion We have seen so far that a function, such as main, can call another function to perform some computation. In Java, a function can also call itself. Such types of functions are called recursive functions. A function, f, is also said to be recursive if it calls another function, g, which in turn calls f. Although it may sound strange for a function to call itself, it is in fact not so strange, as many mathematical functions are defined recursively... e.g., factorial function: n! = Although less efficient than iterative functions (using loops) due to overhead in function calls, in many cases, recursive functions provide a more natural and simple solutions. Thus, recursion is a powerful tool in problem solving and programming. Problems that can be solved using recursion have the following characteristics: • One or more simple cases of the problem have a direct and easy answer - also called base cases. Example: 0! = 1. The other cases can be re-defined in terms of a similar but smaller problem - recursive cases. Example: n! =n(n-1)! By applying this re-definition process, each time the recursive cases will move closer and eventually reach the base case. Example: n! → (n-1)! → (n-2)! → ... 1!, 0!. The strategy in recursive solutions is called divide-and-conquer. The idea is to keep reducing the problem size until it reduces to the simple case with obvious solution. size n problem } Recursive version int factorial (int n) { if n = 0, n* (n-1)! if n>0 if (n == 0) return 1; size n-1 problem size 1 problem //base case Example: Recursive Factorial The following code shows the recursive and iterative versions of the factorial function: //recursive case else return n*factorial (n-1); size n-2 problem size 1 problem } Iterative version int factorial (int n) { size 2 problem size 1 problem size 1 problem int i, product=1; for (i=n; i>1; -1) product=product * i; return product; size 1 problem In recursive functions such as above: • The if branch is the base case, while the else branch is the recursive case. For the recursion to terminate, the recursive case must be moving closer to the base case. Tracing the Recursive Functions Executing recursive algorithms goes through two phases: Expansion in which the recursive step is applied until hitting the base step. factorial(4) = 4* factorial (3) = 4*(3* factorial (2)) = 4*(3* (2* factorial (1))) The following diagram from wikipedia shows the complete merge sort process for an example array (38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the size becomes 1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged. = 4*(3* (2*(1 * factorial (0)))) = 4*(3* (2 (11))) = 4*(3* (2*1)) 38 = 4*(3*2) = 4*6 = 24 CSE 202: DATA STRUCTURES Substitution in which the solution is constructed backwards starting with the base step. 2. Sorting Algorithms Call mergeSort (arr, m+1, r) 4. Merge the two halves sorted in step 2 and 3: Call merge (arr, 1, m, r) 38 27 Sorting algorithms rearrange the data in some order (ascending or descending order). Following are the two very common recursive algorithms for sorting. These numbers, indicate the order steps are prohich 27 i. Merge Sort Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, 1, m, r) is key process that assumes that arr[1..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following C implementation for details. MergeSort (arr [], 1, r) If r > 1 1. Find the middle point to divide the array into two halves: middle m = (1+r)/2 2. Call merge Sort for first half: Call mergeSort (arr, 1, m) 3. Call mergeSort for second half: 27 Expansion phase 38 27 43 2 Substitution phase 8 10 جامعة حفر الباطن University of Hafr Al Batin College of Computer Science and Engineering (CCSE 38 27 43 39 82 10 27 30 9 982 10 12 02 9 82 16 9 10 82 19 82 15 7 10 27 30 43 02 20 10 10 10 18 17 Exercise # 1: Edit, compile and run the following code in Eclipse. /* Java program for Merge Sort */ public class MergeSort { 12 13. 14. 15. 16. 17. 34. 35. 36. 57. 37 50. 38. CSE 202: DATA STRUCTURES 59. 40. 40. 41. 42. Merges two of arr[]. 47. 48. // First subarray is void merge(int arr[], int 1, int m, int r) { // Find sizes of two subarrays to be merged int n1 = m - 1 + 1; int n2 = rm; /* Create temp arrays */ int L[] = new int [n1]; int R[] = new int [n2]; /*Copy data to temp arrays*/ for (int i=0; i 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. } } /* Copy remaining elements of R[] if any */ while (j < n2) { arr[k] = R[j]; } } // Main function that sorts arr[1..r] using merge() void sort(int arr[], int 1, int r) { if (1 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. } 95. } 96. /* contributed by Rajat Mishra: https://www.geeksforgeeks.org/merge-sort/ */ System.out.println( Given Array ); printArray(arr); MergeSort ob = new MergeSort(); ob.sort (arr, 0, arr.length-1); System.out.println( Sorted array ); printArray(arr); Given Array 12 11 13 5 6 7 Sorted array 567 11 12 13 ii. Quick Sort Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. 1. Always pick first element as pivot. 2. Always pick last element as pivot (implemented below) 3. Pick a random element as pivot. 4. Pick median as pivot. The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time. Page 4 of 7 /* low --> Starting index, high --> Ending index */ quickSort (arr [], low, high) { if (low high) { to Partition Algorithm: There can be many ways do partition, following pseudo code adopts the method given in CLRS book (Introduction to Algorithms by Cormen et. al.). The logic is simple, we start from the leftmost element and keep track of index of smaller (or equal to) elements as i. While traversing, if we find a smaller element, we swap current element with arr[i]. Otherwise we ignore current element. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. } 15. 16. /* pi is partitioning index, arr [pil is now at right place */ pi partition (arr, low, high); 1. 2. public class QuickSort 3. { 4. 17. 18. 19. 20. quickSort (arr, low, pi 1); // Before pi quickSort (arr, pi + 1, high); // After pi 21. 22. 23. 24. Exercise # 2: Edit, compile and run the following code in Eclipse. Java program for implementation of QuickSort {10, 30, 40, (50) Partition around 50 {10, 30, 40} Partition around 40 (10, (30) Partition {10} around 30 { (10, 80, 30, 90, 40, 50, (70) Partition around 70 (Last element) = for (int j-low; j CSE 202: DATA STRUCTURES 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. iii. arr[high] = temp; return i+1; } /* The main function that implements QuickSort() arr[] > Array to be sorted, low --> Starting index, high > Ending index */ void sort(int arr[], int low, int high) { if (low high) { } } /* pi is partitioning index, arr[pi] is now at right place */ int pi= partition (arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort (arr, pi+1, high); /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i CSE 202: DATA STRUCTURES Method Selection sort Insertion sort Merge sort Quick sort Examples of Algorithms and their big-O complexity Best Case Worst Case O(n²) O(n) O(n log n) O(n log n) O(n²) O(n²) O(n log n) O(n²) Page 6 of 7 Average Case O(n²) O(n²) O(n log n) O(n log n) جامعة حفر الباطن University of Hofr Al Batin College of Computer Science and Engineering (CCSE Task 1: Write a complete Java program to implement above sorting algorithms. Input an array of double data type from user, and choice of sorting algorithm to be used. Display the sorted array to user.
Expert Answer:
Answer rating: 100% (QA)
SOURCE CODE import javautil public class Main static void mergedouble arr ... View the full answer
Related Book For
Auditing and Assurance services an integrated approach
ISBN: 978-0132575959
14th Edition
Authors: Alvin a. arens, Randal j. elder, Mark s. Beasley
Posted Date:
Students also viewed these electrical engineering questions
-
Write a Java program to implement the Game of Life, as defined by John Conway: Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three...
-
Write a Metropolis algorithm to generate samples from a target distribution, (x) exp(x2/2), based on the proposal v-x) 2(0.4)
-
Write a program that asks the user to input a vector of integers of arbitrary length. The program then counts the number of elements, the number of positive elements, and the number of negative...
-
Implement two versions of the RESULT(s, a) function for the 8-puzzle: one that copies and edits the data structure for the parent node s and one that modifies the parent state directly (undoing the...
-
In mid-2009, the Obama administration announced it would cancel orders for a new fleet of presidential helicopters. About $3 billion had already been spent on developing the helicopters, which had...
-
The specific gravity of benzene is 0.876. Calculate its specific weight and its density in U.S. Customary System units.
-
Virtuoso Transportation issued \(\$ 600,000\) of \(8 \%\) bonds payable at \(9^{-}\) on October 1, 2010. These bonds are callable at 100 and mature on October 1, 2018. Virtuoso pays interest each...
-
Refer to question 10. Suppose that the consultants fee is $5,000 and the utility function for the owner of Morley Properties can be approximated by the exponential utility function: U(x) = 1 e-x/R...
-
computer facilities over a one-year period to aid in customer billing and perhaps inventory control. Project C entails the evaluation of a customer billing system proposed by Advanced Computer...
-
5 10 points Match the virtual lab procedure with the correct lung volume. 6 7 Ask the subject to inspire a normal inspiration, and breathe out a normal expiration, then exhale as forcibly as possible...
-
.A company invests in a project that delivers annual payments of $100 forever! The payments start three years (t=3) from today. Use 5% discount rate. The timeline of the projected cash flows is as...
-
The following diagram depicts the NPV profile for an investment that costs $62,000 and produces annual cash flow of $21,000 for four years. 25000 20000 15000 10000 5000 0 -5000 -10000 -15000 0% 5%...
-
1 Solve for q, AVC - MC = 0 when given the following equations AVC = 10 - 0.03q + 0.00005q^2 MC = 10 - 0.06q + 0.00015q^2 2. If given the following equations AVC = 10-0.03q+0.00005q^2 ATC =...
-
Golden State CPA firm leases tax software from Low Tax Software Company to prepare federal and state income tax returns. The lease agreement calls for a base charge of $5,000 per year plus $100 per...
-
How does the process of alternative splicing contribute to proteomic diversity, and what are some examples of diseases caused by aberrant splicing ?
-
Discuss the concept of epigenetics and its impact on gene expression regulation, considering both environmental influences and cellular mechanisms involved .
-
The Hard Rock Mining Company is trying to develop cost formula for utility cost.Two independent variables are being considered: Tons Mined and Direct Labor hours. As the managerial accountant, you...
-
Q:1 Take any product or service offered in Pakistan and apply all determinents of customer Perceived value ?
-
The auditor's audit files usually can be provided to someone else only with the permission of the client. Give three exceptions to this general rule.
-
Gale Gordon, CPA, has found ratio and trend analysis relatively useless as a tool in conducting audits. For several engagements, he computed the industry ratios included in publications by Standard...
-
The following are various asset misappropriations involving the payroll and personnel cycle. 1. The payroll clerk submitted payroll information for a fictitious employee and had the funds directly...
-
Assume the National Post completed the following transactions for one subscriber during 2020: Required 1. Using the account title Unearned Subscription Revenue, journalize the transactions above. 2....
-
The law firm Garner & Brown received from a large corporate client an annual retainer fee of \(\$ 60,000\) on January 2,2020 . The fee is based on anticipated monthly services of \(\$ 5,000\)....
-
Chez Nous Limited, a new company, made sales of 20,000 units at a cost of \(\$ 40\) per unit. The company offers a one-year warranty that replaces any defective units with a new one. The company...
Study smarter with the SolutionInn App