sorting algorithm CoolSort(). Usef insertion sort for designing this sorting alg
ID: 3667609 • Letter: S
Question
sorting algorithm CoolSort(). Usef insertion sort for designing this sorting algorithm.
We will first choose a decreasing sequence of numbers that ends at 1. Let us consider the sequence of step sizes H = 5, 3, 1. You can choose any decreasing sequence. Note that the first element of the sequence is less than the number of elements in the array.
For each H, sort sub-arrays that start at arbitrary element and include every Hth element using insertion sort. For example, consider the following array
a = [ 62 83 18 53 07 17 95 86 47 69 25 28].
5, 3 and 1 is shown below
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12
Input 62 83 18 53 07 17 95 86 47 69 25 28
H = 5 17 28 18 47 07 25 83 86 53 69 62 95
H = 3 17 07 18 47 28 25 69 62 53 83 86 95
H = 1 07 17 18 25 28 47 53 62 69 83 86 95
The first pass, 5-sorting, performs insertion sort on separate subarrays (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). For instance, it changes the subarray (a1, a6, a11) from (62, 17, 25) to (17, 25, 62).
The next pass, 3-sorting, performs insertion sort on the subarrays (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12).
The last pass, 1-sorting, is an ordinary insertion sort of the entire array (a1,..., a12).
Sample Test Case 1 Input = [2, 5, 6, 4, 10, 9, 8, 1, 10, 5] and H = [5, 3,1]
Output = [1, 2, 4, 5, 5, 6, 8, 9, 10, 10]
Sample Test Case 2 Input = [2, 5, 9, 4, 10, 7, 8, 1, 11, 5] and H = [5, 2,1]
Output = [1, 2, 4, 5, 5, 7, 8, 9, 10, 11]
Explanation / Answer
I have explained a Insertion sorting Implementation using java with an example ,
In this Java program, we will sort an integer array using Insertion sort algorithm in Java. As I said, insertion sort should only be used with small arrays or linked list, we are going to use an integer array of length 7, which contains numbers in random order. We have a method called insertionSort(int[] input) which takes an unsorted array and sorts it. If you look at the logic, you will first see that we are looping over integer array, starting from second element. On inner loop we initialize the index with next element e.g. in first iteration, j=1 and it will point to second element. Inner loop is used to compare current element with already sorted element, that's why after each iteration we decrease j by 1, here j>0 condition stops when we reach at the beginning of array. Shifting and swapping of element occur only if current element is less than already sorted element. Like in our code example, 32 is first element so it is sorted, next is 23 so we compare it to 32, now 23 is less than 32 so we will swap 32 and 23 position. I have inline swapping logic but you can also create a method swap just to make algorithm more readable. Once we came out of the outer loop, our int array is sorted on ascending order.
import java.util.Arrays;
/** * Java program to implement insertion sort in Java. In this example, we will * sort an integer array using insertion sort algorithm. This logic can be used * to sort array of String, or any other object which implements Comparable or * Comparator interface in Java. * * */
public class InsertionSortDemo {
public static void main(String args[])
{ // unsorted integer array int[] unsorted = {32, 23, 45, 87, 92, 31, 19};
System.out.println("integer array before sorting : " + Arrays.toString(unsorted));
insertionSort(unsorted);
System.out.println("integer array after sorting : " + Arrays.toString(unsorted));
}
/* * Sort integer array using Insertion sort algorithm. * only good for small array. */
public static void insertionSort(int[] unsorted)
{
for (int i = 1; i < unsorted.length; i++)
{
int j = i; while (j > 0 && unsorted[j] < unsorted[j - 1])
{
//swap int temp = unsorted[j - 1];
unsorted[j - 1] = unsorted[j]; unsorted[j] = temp; j--;
} } } }
Output:
integer array before sorting : [32, 23, 45, 87, 92, 31, 19]
integer array after sorting : [19, 23, 31, 32, 45, 87, 92]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.