Question

Hello, I need the correct answer for this please , a quick sort program -java code- that have 2 arrays first one will have different values , the second one the values will be from smallest to largest number then the program have a quick sort to do it for both of them and will count the time - how long the quick sort is take for each one - which array is faster.

Thank you ❤️

Answer 1

QuickSort.java
public class QuickSort {


        private int array[];
        private int length;

        public void sort(int[] arr) {

            if (arr == null || arr.length == 0) {
                return;
            }
            this.array = arr;
            length = arr.length;
            quickSort(0, length - 1);
        }

        private void quickSort(int lowerIndex, int higherIndex) {

            int i = lowerIndex;
            int j = higherIndex;
            // calculate pivot , COnsider pivot as middle index number
            int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
            // Divide into two arrays
            while (i <= j) {
                /**
                 * For each iteration, we will identify a number from left side which
                 * is greater then the pivot , and also we will identify a number
                 * from right side which is less then the pivot value. Once the search
                 * is completed, then we exchange both numbers.
                 */
                while (array[i] < pivot) {
                    i++;
                }
                while (array[j] > pivot) {
                    j--;
                }
                if (i <= j) {
                    exchangeNumbers(i, j);
                    //move index to next position on both sides
                    i++;
                    j--;
                }
            }
            // call quickSort() method recursively
            if (lowerIndex < j)
                quickSort(lowerIndex, j);
            if (i < higherIndex)
                quickSort(i, higherIndex);
        }

        private void exchangeNumbers(int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        public static void main(String a[]){

            QuickSort quickSort = new QuickSort();
            int[] arr1 = {21,54,85,574,25,36,65,24,75,42};

            long startTime = System.nanoTime();//start time
            quickSort.sort(arr1);//sort the array 1
            long endTime =  System.nanoTime();//end time

            System.out.println("Original array 1\n");
            for(int i:arr1){//print original array 1
                System.out.print(i);
                System.out.print(" ");
            }

            System.out.println("\nTotal time required for unsorted array : "+(endTime-startTime)+" nanosecond");
            int[] arr2 = {1,2,3,4,5,6,7,8,9,10};
            startTime = System.nanoTime();//start time
            quickSort.sort(arr2);//sort the array 2
            endTime = System.nanoTime();//end time

            System.out.println("Original array 2\n");
            for(int i:arr2){//print original array 2
                System.out.print(i);
                System.out.print(" ");
            }

            System.out.println("\nTotal time required for sorted array : "+(endTime-startTime)+" nanosecond");
        }

}

Output

Original array 1

21 24 25 36 42 54 65 75 85 574
Total time required for unsorted array : 22805 nanosecond
Original array 2

1 2 3 4 5 6 7 8 9 10
Total time required for sorted array : 7177 nanosecond

From above output we came to conclusion that already sorted array required less time because swaping is not required only value comparisions are required.