Kursova2_SELECTION SORTandSHELLSORT

import java.util.Arrays;

public class SelectionVsShellSort {
    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++)
        {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            // Swap the found minimum element with the first
            // element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }

        return arr;
    }
}