QuestionQuestion

Transcribed TextTranscribed Text

Sorting without comparisons There are many algorithms which can sort groups of data values. Most of these algorithms rely on comparisons between elements. These types of algorithms can be shown to be . That is, the runtime of comparison-based sorting cannot be improved beyond linearithmic. An alternative strategy would be to sort elements without comparisons. This usually requires limiting data types to simpler types, such as integers or floating-point numbers. In this assignment we will be implementing a sorting algorithm that only partially relies upon comparisons. If implemented correctly, the algorithm should minimize the number of comparisons and possibly have a faster runtime than the linearithmic lower bound. Objectives Here is what we'd like you take out of this assignment. Course Analyze the runtime performance of an algorithm using big-O notation. Identify and describe common algorithm strategies... Module To implement a sorting algorithm. To write a simple data visualization to help verify the correctness of your algorithm. The algorithm We begin by trying to simplify the sorting problem. One way in which we can do this is to only accept numeric inputs. More specifically, our routine will accept an int[] array and then sort the array. The method will not return a new sorted array, but will instead rearrange elements in the input array. This routine will work equally well with other numeric types, such as floating-point values. This algorithm will focus on a grouping strategy. All input elements will be placed within several predefined groups, each of which will have a lower and upper bound. For example: Once all elements have been grouped together, each group will then be sorted. Please note that the algorithm does not compare elements against one another when grouping them together. To sort each individual group we will use a basic comparison-based sort (insertion sort). Our goal is to reduce the amount of comparisons by keeping each group as small as possible. After sorting each group, the groups will then be merged together into a single sorted sequence. This requires you to iterate over each group and then each element in each group. All elements should be copied back to the input array, making this algorithm an in-place sort. Forming groups When invoking your sort() method a user should be able to provide the number of groups to form. You should then calculate the boundaries of each group based on the elements in the input array and the number of groups. For example, the following array was generated from random numbers in the range [1,30]: [22, 18, 22, 11, 16, 12, 9, 29, 5, 28, 8, 28, 22, 24, 26] You should first identify the lowest and highest input value: low = 5, high = 29 Using these values you should be able to determine the number of values that could lie within the input range [low,high] and then to create the requested number of groups. For example, given an array of size 15 and a range of values [5, 29] with a total of 25 possible values in the range, I was able to determine the size of each group (5 elements) and the following upper-bounds for each group: [10, 15, 20, 25, 29] You should be able to (carefully) loop over these upper bounds to figure out which group an element belongs to. Given the upper bounds above, we have the following groups: [5 (low),10] [11, 15] [16, 20] [21, 25] [26, 29 (high)] Grouping Elements To group elements together you can define an array where each index is assigned to a group of elements (mirroring the array of upper bounds seen above). Any elements in a group can then be stored within a linked list at that position in the array. For example: When a new element is inserted into a linked list, it should maintain the order of elements in that linked list. This is similar to how insertion sort works and is costly if the linked list grows too large. After adding all elements from the array seen above you would have an array of linked lists like the following: Finishing the sort By looping over each linked list from top-to-bottom, left-to-right, you should be able to iterate over the elements in sorted order. You should do this and place all elements back into the original array. This completes the steps of the algorithm. After you have written the method, you should test the basic functionality of the sort by generating a random array and testing the routine. Your output should include: The original unsorted array The resulting sorted array A boolean value that reports whether any inversions are detected in the sorted array. This should be done programmatically so that larger arrays can be verified. For example: Generating an array of size 15 with elements in the range [1,30] Original: [22, 18, 22, 11, 16, 12, 9, 29, 5, 28, 8, 28, 22, 24, 26] Sorting with 5 groups Sorted: [5, 8, 9, 11, 12, 16, 18, 22, 22, 22, 24, 26, 28, 28, 29] Detected inversions? false Visualizing your work To help verify the correctness of your algorithm, add the following output to your algorithm: Print the min & max values when the method is called. Print the (estimated) size of each group. Print the upper bound of each group. Print the array of linked lists that are used with the algorithm. Here are a few example runs of the algorithm in action. You should be running several tests as well with different types of input arrays and numbers of groups. Generating an array of size 15 with elements in the range [1,30] Original: [22, 18, 22, 11, 16, 12, 9, 29, 5, 28, 8, 28, 22, 24, 26] Sorting with 5 groups Min/max: [5, 29] Group size: 5.0 Group thresholds: [10, 15, 20, 25, 29] 0[5-10]: 5 -> 8 -> 9 1[11-15]: 11 -> 12 2[16-20]: 16 -> 18 3[21-25]: 22 -> 22 -> 22 -> 24 4[26-29]: 26 -> 28 -> 28 -> 29 Sorted: [5, 8, 9, 11, 12, 16, 18, 22, 22, 22, 24, 26, 28, 28, 29] Detected inversions? false Generating an array of size 20 with elements in the range [1,100] Original: [19, 21, 46, 49, 20, 39, 77, 13, 29, 56, 67, 75, 28, 81, 68, 39, 67, 31, 44, 93] Sorting with 15 groups Min/max: [13, 93] Group size: 5.4 Group thresholds: [18, 23, 29, 34, 40, 45, 50, 56, 61, 67, 72, 77, 83, 88, 93] 0[13-18]: 13 1[19-23]: 19 -> 20 -> 21 2[24-29]: 28 -> 29 3[30-34]: 31 4[35-40]: 39 -> 39 5[41-45]: 44 6[46-50]: 46 -> 49 7[51-56]: 56 8[57-61]: null 9[62-67]: 67 -> 67 10[68-72]: 68 11[73-77]: 75 -> 77 12[78-83]: 81 13[84-88]: null 14[89-93]: 93 Sorted: [13, 19, 20, 21, 28, 29, 31, 39, 39, 44, 46, 49, 56, 67, 67, 68, 75, 77, 81, 93] Detected inversions? false

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.ArrayList;
import java.util.Scanner;


public class SortingWithoutComparisons {
   
    public static int min , max , groupNumbers , arraySize,minArrRang , maxArrRang;
    public static float groupSize;
    public static Scanner input ;
    public static int groupThresholds[];
    public static boolean inversions;
    public static ArrayList <ArrayList<Integer>> linkedList;
   
    public static void getUserInputs(){
       // get data from user
       input = new Scanner(System.in);
       System.out.println("please enter size of the array");
       arraySize = input.nextInt();
       System.out.println("please enter min rang of the array");
       minArrRang = input.nextInt();
       System.out.println("please enter max rang of the array");
       maxArrRang = input.nextInt();
       System.out.println("please enter number of groups");
       groupNumbers = input.nextInt();
      
    }
   
    public static void computeMaxAndMin( int array[]){
       // get min value and max value in the array
       min = max = array[0];
       for(int i = 1 ; i < arraySize ; i++){
            if( array[i] < min)
                min = array[i];
            else if( array[i] > max )
                max = array[i];
       }
    }...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

50% discount

Hours
Minutes
Seconds
$13.00 $6.50
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats