Sorting Algorithms

So class has started for a week now, but I’ve only gone to class for six days because we had MLK holiday and class got cancelled because of the snow. North Carolina can’t handle the mere thought of snow lol.

I’m writing down some of the easy Quicksort and Mergesort I’ve learned in COMPSCI 330. Maybe they’ll help me in the review process.

QuickSort:

Quicksort uses a divide-and-conquer spirit. It gets a pivot in the array and recurse on all numbers smaller or larger than the pivot. There are several ways to implement it. Here’s the method on Introduction to Algorithms:

QSORT(A, i, j)
    pivot = SPLIT(A, i, j)
    QSORT(A, i, pivot - 1)
    QSORT(A, pivot + 1, j)
SPLIT(A, m, n)
    i = m - 1
    FOR j from 0 to n - 1
        if A[j] < A[n]
            i++
            SWAP A[i], A[j]
        SWAP A[i + 1], A[n]
    return i + 1

This version is pretty hard to understand, but the key is that for each m <= k <= i, A[k] < A[n], and for each i + 1 <= k <= j, A[k] > A[n].

The running time is obviously O(n log n).

MergeSort

MergeSort also uses divide-and-conquer. Instead of dealing with a pivot, it first divide, and then merge two divisions in linear time.

MSORT(A, i, j)
    B = MSORT(A, i, (i + j) / 2)
    C = MSORT(A, (i + j) / 2 + 1, j)
    A = MERGE(B, C)
Merge(B, C)
    D = empty array
    i = j = k = 1
    while (i < |B| and j < |C|)
        if(B[i] < C[j])
            D[k] = B[i], i++
        else
            D[k]=C[j], j++
    k++
    Copy all elements of the other array into D
    return D

The running time is still O(n log n).

Leave a Reply

Your email address will not be published. Required fields are marked *