3.5

package KursovaRabotaSrok2;
import java.util.Arrays;
public class SelectionVsShellSort2 {

    public static void main(String[] args) {
        int[] arr = new int[]{233, 1, 5, 99, 17, 4};
        System.out.println(Arrays.toString(shellSort(arr, arr.length)));
        System.out.println(Arrays.toString(sort(arr)));
        /*
       Shell heapSort has better time complexity O(n log(n))
       and they have same space complexity O(1)
         */
    }
________________________________________________
static int[] shellSort(int arr[], int n) {
        // Start with a big gap, then reduce the gap
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // Do a gapped insertion heapSort for this gap size.
            // The 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;
            }
        }
        return arr;
    }
    static int[] sort(int arr[]) {
        int n = arr.length;
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n - 1; i++) {