Question

Implement Library Sort in Java which is a version of Insertion Sort with gaps to speed up the computation. If the pseudocode in Wikipedia (https://en.wikipedia.org/wiki/Library_sort) is not enough, you can download the research paper from (https://arxiv. org/pdf/cs/0407003.pdf). Below is the algorithm and pseudo code.

Implementation

Algorithm

Let us say we have an array of n elements. We choose the gap we intend to give. Then we would have a final array of size (1 + ε)n. The algorithm works in log n rounds. In each round we insert as many elements as there are in the final array already, before re-balancing the array. For finding the position of inserting, we apply Binary Search in the final array and then swap the following elements till we hit an empty space. Once the round is over, we re-balance the final array by inserting spaces between each element.

Following are three important steps of the algorithm:

1. Binary Search: Finding the position of insertion by applying binary search within the already inserted elements. This can be done by linearly moving towards left or right side of the array if you hit an empty space in the middle element.
2. Insertion: Inserting the element in the position found and swapping the following elements by 1 position till an empty space is hit. This is done in logarithmic time, with high probability.
3. Re-Balancing: Inserting spaces between each pair of elements in the array. The cost of rebalancing is linear in the number of elements already inserted. As these lengths increase with the powers of 2 for each round, the total cost of rebalancing is also linear.

Pseudocode

procedure rebalance(A, begin, end) is
    r ← end
    w ← end ÷ 2

    while r ≥ begin do
        A[w+1] ← gap
        A[w] ← A[r]
        r ← r − 1
        w ← w − 2

procedure sort(A) is
    n ← length(A)
    S ← new array of n gaps

    for i ← 1 to floor(log2(n) + 1) do
        for j ← 2^i to 2^(i + 1) do
            ins ← binarysearch(A[j], S, 2^(i − 1))
            insert A[j] at S[ins]

Here, binarysearch(el, A, k) performs binary search in the first k elements of A, skipping over gaps, to find a place where to locate element el. Insertion should favor gaps over filled-in elements.

Answer 1

import java.util.Arrays;


public class ShellSortExample {

 public static void main(String[] args) {

  int[] array = { 50, 2, 5, 1, 49 };
  System.out.println("Input Array = " + Arrays.toString(array));
  shellsort(array);
  System.out.println("After shell sort =  " + Arrays.toString(array));

 }
 /* function to sort arr using shellSort */
 static int shellsort(int arr[]) {
  int n = arr.length;

  // Start with a big gap, then reduce the gap
  for (int gap = n / 2; gap > 0; gap /= 2) {

  // Do a gapped insertion sort for this gap size. he first gap elements
  // a[0..gap-1] are already in gapped order keep adding one more element until
  // the entire array is gap sorted

   for (int i = gap; i < n; i += 1) {
   // add a[i] to the elements that have been gap sorted save a[i] in temp and make

// a hole at position i

int temp = arr[i];

// shift earlier gap-sorted elements up until the correct location for a[i] is

// found

int j;

for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)

{ arr[j] = arr[j - gap];

} // put temp (the original a[i]) in its correct location

arr[j] = temp;

}

System.out.println("After current gap(" + gap + ") : " + Arrays.toString(arr));

}

return 0;

}

}

note: plzzz don't give dislike.....plzzz comment if you have any problem i will try to solve your problem.....plzzz give thumbs up i am in need....