## Transcribed 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

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];

}

}...