Sorts

Question 1

Write the Merge Sort + WC

Answer 1

WC=O(nlogn)

MergeSort(A) {
//control statement
if(A<=1)
     return

midpoint

Question 2

Write the Heap Sort + WC

Answer 2

x /**this is another way that only to sort a predefined array recursively */
public void sort(int arr[]) {
int n = arr.length;

        //build initial heap from the array
        for(int i = n/2 -1; i >= 0; i--) { //find parent node andwork downwards
            heapify(arr, n, i);
        }

        //for each element in the heap
        for(int i = n - 1; i > 0; i--) {
            //move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            //call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

private void heapify(int arr[], int n, int i) {
    int largest = i; //initialise largest as the root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }

Question 3

Write the Quick Sort + WC

Answer 3

QuickSort(A,start,end) {
//control condition
if(start

Question 4

Write the Insertion Sort + WC

Answer 4

WC=O(n^2)

InsertionSort(A,n) {
for(i0 && A[hole-1]>value>) {
          //shift elements at hole-1 to hole
          A[hole]

Question 5

Selection Sort + WC

Answer 5

WC=O(n^2)

SelectionSort(A) {
for(i=0 tolength(A)) {
smallestIndex

Question 6

Counting Sort + WC

Answer 6

WC=O(n)

CountingSort(A) {
n=0) {
     output[count[A[i]]-1]==A[i]
     --count[A[i]]
}

//copy output to A so A contains sorted array
for(i=0 ton)
     A[i] = output[i]
}