[Introduction to algorithm]Sorting and Order Statistics

[wutiejun]

Algorithm	Worst-case running time	Average-case/expected running time
Insertion Sort	O(n^2)	O(n^2)
Merge Sort	O(n*lg(n))	O(n*lg(n))
Heap Sort	O(n*lg(n))	-
Quick Sort	O(n^2)	O(n*lg(n)) (expected)
Counting sort	O(k+n)	O(k+n)
Radix sort	O(d(n+k))	O(d(n+k))
Bucket sort	O(n^2)	O(n) (average case)

[wutiejun]

Counting Sort

//
// K is the max number in the array
int * CountingSort(int *pA, int K, int Max)
{
    int * pC = malloc(sizeof(int) * K);         // Count array
    int * pB = malloc(sizeof(int) * Max);       // Temp array
    int i;

    memset(pC, 0, sizeof(int) * K);
    for (i = 0; i < Max; i ++)
    {
        pC[pA[i]] = pC[pA[i]] + 1;
    }
    //C[i] now contains the number of elements equal to i.

    for (i = 1; i < K; i ++)
    {
        pC[i] = pC[i] + pC[i - 1];
    }
    //
    for (i = 0; i < Max; i ++)
    {
        pB[pC[pA[i]] - 1] = pA[i];
        pC[pA[i]] = pC[pA[i]] - 1;
    }
    free(pC);
    return pB;
}

[wutiejun]

Merge Sort

#define MAX_INT 0x7FFFFFFF;

// divide and conquer sort
// p: start index
// q: mid index, p + 1
// r: array items count, n-1
// If only one item need to merge, the item will be in Left sub-array.
void Merger(int * pA, int p, int q, int r)
{
    int n1 = q -  p + 1;    // if only one element in the array, it's will be in the left sub-array
    int n2 = r - q;         // if only one element in the array, the right will be empty
    int * pL = (int *)malloc(sizeof(int) * (n1 + 1));
    int * pR = (int *)malloc(sizeof(int) * (n2 + 1));
    int i;
    for (i = 0; i < n1; i ++)
    {
        pL[i] = pA[p + i];
    }
    //
    for (i = 0; i < n2; i ++)
    {
        // element pA[q] is in the left sub-array, so the index need to plus 1
        pR[i] = pA[q + i + 1];
    }
    pL[n1] = MAX_INT;
    pR[n2] = MAX_INT;

    i = 0;
    int j = 0, k = 0;
    for (k = p; k <= r; k ++)
    {
        if (pL[i] <= pR[j])
        {
            pA[k] = pL[i];
            i ++;
        }
        else
        {
            pA[k] = pR[j];
            j ++;
        }
    }
    free(pL);
    free(pR);
    return;
}

void MergeSort(int *pA, int p, int r)
{
    int q = 0;
    if (p < r)
    {
        q = (p + r) / 2;
        MergeSort(pA, p, q);
        MergeSort(pA, q + 1, r);
        Merger(pA, p, q, r);
    }
    return;
}

[wutiejun]

Bubble Sort

void BubbleSort(int *pA, int n)
{
    int i, j, t;
    for (i = 0; i < n; i ++)
    {
        for (j = 0; j < n - i - 1; j ++)
        {
            if( pA[j] > pA[j+1])
            {
                t = pA[j];
                pA[j] = pA[j+1];
                pA[j+1] = t;
            }
        }
    }
}

void BubbleSortEx(int *pA, int n)
{
    int i, j, t, f;
    for (i = 0; i < n; i ++)
    {
        f = 0;
        for (j = 0; j < n - i - 1; j ++)
        {
            if( pA[j] > pA[j+1])
            {
                t = pA[j];
                pA[j] = pA[j+1];
                pA[j+1] = t;
                f = 1;
            }
        }
        if (f == 0)
        {
            // no element swapped, already sorted, break
            break;
        }
    }
}

[wutiejun]

Quick Sort

int Partition(int * pA, int p, int r)
{
    int x = pA[r];
    int i = p;
    int j;
    int t;
    for (j = p; j < r; j ++)
    {
        if (pA[j] <= x)
        {
            t = pA[i];
            pA[i] = pA[j];
            pA[j] = t;
            i ++;
        }
    }
    t = pA[i];
    pA[i] = pA[r];
    pA[r] = t;
    return i;
}

void QuickSort(int *pA, int p, int r)
{
    int q;
    if (p < r)
    {
        q = Partition(pA, p, r);
        QuickSort(pA, p, q - 1);
        QuickSort(pA, q + 1, r);
    }
    return;
}

[wutiejun]

Selection Sort

void SelectionSort(int * pA, int MaxNum)
{
    int i = 0;
    int j = 0;
    int Temp;
    for (i = 0; i < MaxNum; i ++)
    {
        for (j = i; j <= MaxNum; j ++)
        {
            if (pA[i] > pA[j])
            {
//               pA[i] >< pA[j];
               Temp = pA[i];
               pA[i] = pA[j];
               pA[j] = Temp;
            }
        }
    }
    return;
}

void selectionSort(int a[], int size)
{
  int i, j, min, temp;
  for(i=0; i < size-1; i++ )
  {
    min = i;   //setting min as i
    for(j=i+1; j < size; j++)
    {
      if(a[j] < a[min])   //if element at j is less than element at min position
      {
       min = j;    //then set min as j
      }
    }
   temp = a[i];
   a[i] = a[min];
   a[min] = temp;
  }
}

[wutiejun]

Heap Sort

// intorduction-to-algorithm
//
// heap sort
//

#include "stdio.h"
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define MAX_RANDOM 100

#define Left(i)     (2*(i) + 1)
#define Right(i)    (2*((i) + 1))
#define Parent(i)   ((i)/2)

static int RandomScore ( void )
{
    static int inted = 0;
    struct timeval tp;
    gettimeofday ( &tp, NULL );
    int val = tp.tv_usec;

    //srandom(tp.tv_usec%32);
    //val = random();
    if ( inted == 0 )
    {
        srand ( ( unsigned ) time ( NULL ) );
        inted = 1;
    }

    val = rand();
    return ( val % MAX_RANDOM );
}

int * InitArray(int Num)
{
    int * pArray = malloc(sizeof(int) * Num);
    int i;
    for (i = 0; i < Num; i ++ )
    {
        pArray[i] = RandomScore();
    }
    return pArray;
}

void PrintItemArray(int *  pA, int len, const char * pInfo)
{
    int i;
    printf("============%s===============\r\n", pInfo);
    for(i = 0; i < len; i ++)
    {
        printf("%d:%d\r\n", i, pA[i]);
    }
    return;
}

void PrintHeap(int *  pA, int i, int HeapSize)
{
    int l = Left(i);    // 2 * i;
    int r = Right(i);   // 2 * i + 1;
    if (l <= HeapSize)
    {
        printf("\"[%d]:%d\" -> \"[%d]:%d\";\r\n", i, pA[i], l, pA[l]);
        PrintHeap(pA, l, HeapSize);
    }
    if (r <= HeapSize)
    {
        printf("\"[%d]:%d\" -> \"[%d]:%d\";\r\n", i, pA[i], r, pA[r]);
        PrintHeap(pA, r, HeapSize);
    }
    return;
}

// Adjust heap to a max-heap
void MaxHeapify(int * pA, int i, int heapSize)
{
    int l = Left(i);    // 2 * i;
    int r = Right(i);   // 2 * i + 1;
    int largest = i;
    int t;
    //
    if ((l <= heapSize) && (pA[l] > pA[i]))
    {
        largest = l;
    }

    if ((r <= heapSize) && (pA[r] > pA[largest]))
    {
        largest = r;
    }

    if (largest != i)
    {
        t = pA[i];
        pA[i] = pA[largest];
        pA[largest] = t;
        MaxHeapify(pA, largest, heapSize);
    }
    return;
}

void BuildMaxHeap(int * pA, int max)
{
    int i = 0;
    for (i = max/2; i >= 0; i --)
    {
        MaxHeapify(pA, i, max);
    }
    return;
}

void HeapSort(int * pA, int max)
{
    int i = max;
    int t;
    BuildMaxHeap(pA, max);
    for (i = max; i > 0; i --)
    {
        t = pA[0];
        pA[0] = pA[i];
        pA[i] = t;
        MaxHeapify(pA, 0, i - 1);
    }
    return;
}

int main(int argc, char * argv[])
{
    if (argc < 2)
    {
        printf("Please input array count to test sort.\r\n");
        return 0;
    }

    int max = atoi(argv[1]);
    if (max <= 0)
    {
        max = 1;
    }

    int * pArray = InitArray(max);
    PrintItemArray(pArray, max, "raw info");
    //printf("================================\r\n");
    //PrintHeap(pArray, 0, max - 1);

    HeapSort(pArray, max - 1);
    //printf("================================\r\n");
    //PrintHeap(pArray, 0, max - 1);
    PrintItemArray(pArray, max, "raw info");
    return 0;
}

[wutiejun]

INSERTION-SORT(A)

/*
INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorted sequence A[1...j-1]
    i = j - 1
    while i > 0 and A[i] > key
        A[i+1] = A[i]   // Move each element to next if it's later then then key
        i = i -1
    A[i+1]=key  // find the a space to insert the key
*/
void InsertionSort(int *  pA, int len)
{
    int j = 0;
    int i = 0;
    int key = 0;
    for (j = 1; j < len; j ++)
    {
        key = pA[j];
        i = j - 1;
        while ((i >= 0) && (pA[i] > key))
        {
            pA[i + 1] = pA[i];
            i --;
        }
        pA[i+1] = key;
    }
    return;
}

void insertInOrder( int element,int *a, int first, int last)
{
    if (element >= a[last])
        a[last+1] = element;
    else if (first < last)
    {
        a[last+1] = a[last];
        insertInOrder(element, a, first, last-1);
    }
    else // first == last and element < a[last]
    {
        a[last+1] = a[last];
        a[last] = element;
    }
}
void insertion_sort_recur(int *arr, int first, int last)
{
    if(first < last)
    {
        insertion_sort_recur(arr, first, last-1); // avoids looping thru arr[0..last-1]
        insertInOrder(arr[last], arr, first, last-1); // considers arr[last] as the first element in the unsorted list
    }
}