Question

Assume the following list of keys for problems

17, 58, 80, 22, 45, 48, 95, 5, 100, 38, 36, 11, 27

Problem 4:	(2 points) The above list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the middle element of the list. What is the pivot? Give the resulting list after one call to the partition function
Problem 5:	(2.5 points) Assume the following list of keys: 78, 40, 16, 82, 64, 67, 57, 40, 37, 47, 72, 14, 17, 27, 55 This list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the median of the first, last, and middle elements of the list. What is the pivot? Give the resulting list after one call to the partition function.

JAVA

Answer 1

As the ques we want to sort is in JAVA so we have to save the name of the file same as the class name which contains the main class, so we put our function in the QuickSort class

The pivot or pivot element is the element of a matrix, or an array, which is selected first by an algorithm, to do certain calculations. In the case of matrix algorithms, a pivot entry is usually required to be at least distinct from zero, and often distant from it; in this case finding this element is called pivoting.

1)  First Example

public class QuickSort {
        public static void main(String[] args) {
                int[] x = { 17, 58, 80, 22, 45, 48, 95, 5, 100, 38, 36, 11, 27 };
                System.out.println(Arrays.toString(x));

                int low = 0;
                int high = x.length - 1;
 
                quickSort(x, low, high);
                System.out.println(Arrays.toString(x));
        }
 
        public static void quickSort(int[] arr, int low, int high) {
                if (arr == null || arr.length == 0)
                        return;
 
                if (low >= high)
                        return;
 
                // pick the pivot
        // In this we took the middle element as the middle element
                int middle = low + (high - low) / 2;
                int pivot = arr[middle];
 
                // make left < pivot and right > pivot
                int i = low, j = high;
                while (i <= j) {
                        while (arr[i] < pivot) {
                                i++;
                        }
 
                        while (arr[j] > pivot) {
                                j--;
                        }
 
                        if (i <= j) {
                                int temp = arr[i];
                                arr[i] = arr[j];
                                arr[j] = temp;
                                i++;
                                j--;
                        }
                }
 
                // recursively sort two sub parts
                if (low < j)
                        quickSort(arr, low, j);
 
                if (high > i)
                        quickSort(arr, i, high);
        }
}

2) Second example

public class QuickSort {
        public static void main(String[] args) {
                int[] x = { 78, 40, 16, 82, 64, 67, 57, 40, 37, 47, 72, 14, 17, 27, 55 };
                System.out.println(Arrays.toString(x));
 
                int low = 0;
                int high = x.length - 1;
 
                quickSort(x, low, high);
                System.out.println(Arrays.toString(x));
        }
 
        public static void quickSort(int[] arr, int low, int high) {
                if (arr == null || arr.length == 0)
                        return;
 
                if (low >= high)
                        return;
 
                // pick the pivot
        // In this we took the middle element as the middle element 
                int middle = low + (high - low) / 2;
                int pivot = arr[middle];
 
                // make left < pivot and right > pivot
                int i = low, j = high;
                while (i <= j) {
                        while (arr[i] < pivot) {
                                i++;
                        }
                        while (arr[j] > pivot) {
                                j--;
                        }
                        if (i <= j) {
                                int temp = arr[i];
                                arr[i] = arr[j];
                                arr[j] = temp;
                                i++;
                                j--;
                        }
                }
                // recursively sort two sub parts
                if (low < j)
                        quickSort(arr, low, j);
                if (high > i)
                        quickSort(arr, i, high);
        }
}

This is the example of quick sort. By this we can sort the two list very easily.