MATH 140 Quick Sort

You are asked to sort the following list using Quick sort. What are the subarrays after if the pivot is 26?

{26, 43, 14, 25, 10, 19, 30}

{10} and {25, 43, 19, 30}

{10, 19, 14, 25} and {43, 30}

{14, 19, 10} and {25, 43, 30}

{30, 25, 14, 10, 19} and {43}

{10, 19, 14, 25} and {43, 30}

Which is the worst case runtime for a quicksort algorithm?

O(N)
O(N⋅log(N))
O(N²)
O(2^N)

O(N²)

Which code does sorting in Quick Sort?(Not partitioning)

private static int sort(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable pivot = a[lo];
        while (true) { 
            while (less(a[++i], pivot)) {
                if (i == hi) break;
            }

            while (less(pivot, a[--j])) {
                if (j == lo) break;      
            }
            if (i >= j) break;
            exch(a, i, j);        
        }
         exch(a, lo, j);
        return j;
    }

public static void sort(Comparable[] a) {
        
        sort(a, 0, a.length - 1);
        
    }

    private static void sort(Comparable[] a, int lo, int hi) { 
        if (hi <= lo) 
            return;
        int j = 0;
        sort(a, lo, j-1);
        sort(a, j+1, hi);
        partition(a, lo, hi);          
    }

    private static void sort(Comparable[] a, int lo, int hi) { 
        if (hi <= lo) 
            return;
        sort(a, lo, j-1);
        sort(a, j+1, hi);
        
    }

public static void sort(Comparable[] a) {
        
        sort(a, 0, a.length - 1);
        
    }

    private static void sort(Comparable[] a, int lo, int hi) { 
        if (hi <= lo) 
            return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
        
    }

public static void sort(Comparable[] a) {
        
        sort(a, 0, a.length - 1);
        
    }

    private static void sort(Comparable[] a, int lo, int hi) { 
        if (hi <= lo) 
            return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
        
    }

Identify the error in the following following partition method for Quick Sort.

private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable pivot = a[lo];
        while (true) { 
            while (less(a[++i], pivot)) {
                if (i == hi) break;
            }

            while (less(pivot, a[++j])) {
                if (j == lo) break;      
            }
            if (i >= j) break;
            exch(a, i, j);        
        }
         exch(a, lo, j);
        return j;
    }

The statement private static int partition(Comparable[] a, int lo, int hi)  should be public static void partition(Comparable[] a, int lo, int hi) {

The statement while (less(a[++i], pivot)) should be while (less(a[--i], pivot)).

The statement while (less(pivot, a[++j])) should be while (less(pivot, a[--j])) {

The partition method is correct.

The statement while (less(pivot, a[++j])) should be while (less(pivot, a[--j])) {

Which of the following is a fast sorting algorithm?

Selection sort

Quicksort

Shell sort

Insertion sort

Quicksort

You are asked to sort the following list using Quick sort. What are the subarrays after if the pivot is 'Q'?

{'Q' ,'U' ,'I' ,'C' ,'K' ,'S' ,'O' ,'R' ,'T'}

{O} and{S, R, T}

{K, C, I, O, S, R, T} and {U}

{K, O, I, C} and {S, U, R, T}

{I} and {U, O, S, R, T, U}

{K, O, I, C} and {S, U, R, T}