Java sorts Sort the data into ascending order (from smallest to largest). For ea

Question

Java sorts

Sort the data into ascending order (from smallest to largest).

For each sort, show the array each time it is altered. For sorts with a nested loop, show just the result of changes made by the outer loop.

Indicate in some way (with color or a comment, for example), which elements are being swapped.

Dataset:

26, 19, 21, 12, 4, 24, 9, 11

Part 1.) Trace selection sort of dataset above

Part 2.) Trace insertion sort of dataset above

Part 3.) Trace Shell sort of dataset above

Part 4.) Trace radix sort of dataset above. Show the contents of buckets and the array after each pass.

Part 5.) Trace merge sort of dataset above. Show how the arrays are split and how the arrays are merged.

Explanation / Answer

1)

public class SelectionSort {
    public static void selectionSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++)
        {
            int index = i;
            for (int j = i + 1; j < arr.length; j++){
                if (arr[j] < arr[index]){
                    index = j;//searching for lowest index
                }
            }
            int lowestNumber = arr[index];
            arr[index] = arr[i];
            arr[i] = lowestNumber;

            System.out.println("Swap Change");
            for(int i:arr){
                System.out.print(i+" ");
            }
        }
    }
     
    public static void main(String a[]){
        int[] arr1 = {26, 19, 21, 12, 4, 24, 9, 11};
        System.out.println("Before Selection Sort");
        for(int i:arr1){
            System.out.print(i+" ");
        }
        System.out.println();
        
        selectionSort(arr1);//sorting array using selection sort
       
        System.out.println("After Selection Sort");
        for(int i:arr1){
            System.out.print(i+" ");
        }
    }
}

2)

public class InsertionSort {
    public static void insertionSort(int array[]) {
        int n = array.length;
        for (int j = 1; j < n; j++) {
            int key = array[j];
            int i = j-1;
            while ( (i > -1) && ( array [i] > key ) ) {
                array [i+1] = array [i];
                i--;
            }
            array[i+1] = key;
            System.out.println("Swap Change");  
            for(int i:arr){  
                System.out.print(i+" ");  
            }
        }
    }
     
    public static void main(String a[]){  
        int[] arr1 = {26, 19, 21, 12, 4, 24, 9, 11};  
        System.out.println("Before Insertion Sort");  
        for(int i:arr1){  
            System.out.print(i+" ");  
        }  
        System.out.println();  
          
        insertionSort(arr1);//sorting array using insertion sort  
         
        System.out.println("After Insertion Sort");  
        for(int i:arr1){  
            System.out.print(i+" ");  
        }  
    }  
}

3)

public class ShellSort {
    int sort(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.
            // 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;
                System.out.println("Swap Change");  
                for(int i:arr){  
                    System.out.print(i+" ");  
                }
            }
        }
        return 0;
    }

    public static void main(String args[])
    {
        int arr[] = {26, 19, 21, 12, 4, 24, 9, 11};
        System.out.println("Array before sorting");
        for(int i:arr){  
            System.out.print(i+" ");  
        }

        ShellSort ob = new ShellSort();
        ob.sort(arr);

        System.out.println("Array after sorting");
        for(int i:arr){  
            System.out.print(i+" ");  
        }
    }
}

4)

public class Radix {
    static int getMax(int arr[], int n)
    {
        int mx = arr[0];
        for (int i = 1; i < n; i++)
            if (arr[i] > mx)
                mx = arr[i];
        return mx;
    }

    // A function to do counting sort of arr[] according to
    // the digit represented by exp.
    static void countSort(int arr[], int n, int exp)
    {
        int output[] = new int[n]; // output array
        int i;
        int count[] = new int[10];
        Arrays.fill(count,0);

        // Store count of occurrences in count[]
        for (i = 0; i < n; i++)
            count[ (arr[i]/exp)%10 ]++;

        // Change count[i] so that count[i] now contains
        // actual position of this digit in output[]
        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];

        // Build the output array
        for (i = n - 1; i >= 0; i--)
        {
            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
            count[ (arr[i]/exp)%10 ]--;
        }

        // Copy the output array to arr[], so that arr[] now
        // contains sorted numbers according to curent digit
        for (i = 0; i < n; i++)
            arr[i] = output[i];
    }

    // The main function to that sorts arr[] of size n using
    // Radix Sort
    static void radixsort(int arr[], int n)
    {
        // Find the maximum number to know number of digits
        int m = getMax(arr, n);

        // Do counting sort for every digit. Note that instead
        // of passing digit number, exp is passed. exp is 10^i
        // where i is current digit number
        for (int exp = 1; m/exp > 0; exp *= 10)
            countSort(arr, n, exp);
    }

    public static void main (String[] args)
    {
        int arr[] = {26, 19, 21, 12, 4, 24, 9, 11};
        int n = arr.length;
        radixsort(arr, n);
        for(int i:arr){  
            System.out.print(i+" ");  
        }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.