I am trying to understand this code and see what each line does in this program

ID: 3779663 • Letter: I

Question

I am trying to understand this code and see what each line does in this program could you explain what each line or each section of this program does in this netbeans program.

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Sort {

private static final Random random = new Random();
private static final int RANDOM_INT_RANGE = 100;

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter Number of elements in array");
        int n = scan.nextInt();
        int[] arr = newTestArray(n);
        int[] copy = Arrays.copyOf(arr, arr.length);

        System.out.println("Unsorted array: " + Arrays.toString(arr));
        if(n <= 64)
            insertionSort(arr);
        else
            quickSort(arr);
        // check the result
        Arrays.sort(copy);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    private static int[] newTestArray(int size) {
        final int[] arr = new int[size];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(RANDOM_INT_RANGE);
        }
        return arr;
    }

    private static void quickSort(int[] arr) {
        if(arr.length > 0)
            sortInPlace(arr, 0, arr.length - 1);
    }

private static void sortInPlace(int[] arr, int left, int right) {

        if(left >= right) return; // sorted
        final int range = right - left + 1;
        int pivot = random.nextInt(range) + left;
        //int pivot = (left + (right - left)) / 2;
        int newPivot = partition(arr, left, right, pivot);
        sortInPlace(arr, left, newPivot - 1);
        sortInPlace(arr, newPivot + 1, right);
    }

    private static int partition(int[] arr, int left, int right, int pivot)
    {
        // we're going to move around the values in the array.
        // > than this pivot value goes to the right,
        // < than this pivot value goes to the left
        int pivotVal = arr[pivot];
        // temporarily move the pivot value out of the way...
        swapArrayVals(arr, pivot, right);

        int storeIndex = left;
        for(int i = left; i <= (right - 1); i++) {
            if(arr[i] < pivotVal) {
                swapArrayVals(arr, i, storeIndex);
                storeIndex++;
            }
        }
        swapArrayVals(arr, storeIndex, right);
        return storeIndex;
    }

    private static void swapArrayVals(int[] arr, int from, int to) {
        int fromVal = arr[from];
        int toVal = arr[to];
        arr[from] = toVal;
        arr[to] = fromVal;
    }

    private static void insertionSort(int[] arr)
    {
        int temp;
        for (int i = 1; i < arr.length; i++)
        {
            for(int j = i ; j > 0 ; j--)
            {
                if(arr[j] < arr[j-1])
                {
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
    }

}

Explanation / Answer

Here we have a class named Sort.
member variable is one static final integer named Random_int_range with value 500 and another is object of random class.
Then inside main function its asking user to enter number of elements of array and scanning the value using object of Scanner class and have defined an array arr and a copy of that array named copy.
First it prints the unsorted array and on the basis of number of elements of arrays it calls different sorting methods like if its less than 64 then calls insertion sort else quick sort and then prints the sorted array.
Now here we have different functions defined to perform the above actions like we have newTestArray which will create a array of size entered by user using random number generation.
Then quick sort method which in tun calls another function named sortInPlace(takes arguments array, and left and right of pivot).
Now sortInPlace , it performs the sorting implementing quick sort algo with help of other functions like partition(another function defined in this class and in turn calls another function swapArrayVals this function is also support the implementation of quick sort) to divide the array
Then insertionSort function to sort array by implementing insertion osrt algo.

So in short a class to sort array of size entered by user, generates random number to insert in array and then on size basis call insertion or quick sort to sort the array.

Navigate

I am trying to understand the proof of the Karp-Lipton theorem as stated in the

I am trying to understand this program from my class. I understnad the basic for

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

I am trying to understand this code and see what each line does in this program

Question

Explanation / Answer

Related Questions

Navigate