Quicksort

"The quicksort algorithm has a worst-case running time of  Θ(n^2 ) on an input array of n numbers. Despite this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is Θ(nlgn), and the constant factors hidden in the Θ(nlgn) notation are quite small. It also has the advantage of sorting in place, and it works well even in virtual-memory environments."  [Introduction to algorithms]

Maximum-subarray problem

/*
Maximum-subarray problem
Given an array, find the subarray whose sum is the largest among all of the subarrays. The program prints the left index, right index and the sum of the subarray. The maximum-subarray problem is interesting only when the array containssome negative numbers.
The program uses divide-and-conquer algorithm described on Page68, Introduction to Algorithms.
Of course, this problem can be solved by using loops directly as the second program does.
*/

A 0-1 Knapsack Problem

/*
Input two integers M and N. Find all possible ways that the sum of numbers chosen from 1, 2,3,...N equals M. Print all possible combinations.
*/

Combination of letters

// List all combinations of letters in a string. Suppose no letter is repeated.
// traverse letters from the first one to the last one.
// combination[ ] is used to save the result of each combination.
// layer indicates the number of letters in the combination, also it tells you
// the position of the newly visited letter in combination[ ]
// layer increases by one in each recursion

Target Shooting Problem

Target shooting

Decimal Integer to Binary

Sieve of Eratosthen algorithm

Sieve of Eratosthen algorithm is used to find primes.
The following codes(modified) are from Algorithms in C++ and Core Java Volume I.

Palindrome

The following program determines if a given string is a palindrome.
Another way to do this is first to copy the string to another char[] and remove the non- alphabet characters from the string. Then copy it to the third char array and  reverse the order of the string . Finally compare the two strings.

Finding maximum

/* Finding max number in an integer array
using recursive method.
*/

Josephus Problem

/*
Josephus Problem
N people have decided to elect a leader by arranging themselves in a
circle and eliminating every M th person around the circle, closing
ranks as each person drops out. The problem is to find out which person
will be the last one remaining ( a mathematically inclined potential
leader will figure out ahead of time which position in the circle to take).
From Algorithms in C++.
*/

Connectivity Problem

/*
This program reads a sequence of pairs of nonnegative integers less than N from standard input (interpreting the pair p q to mean "connect object p to object q") and prints out pairs
representing objects that are not yet connected. It maintains an array id that has an entry for each object, with the property that id[p] and id[q] are equal if and only if p and q are connected. For simplicity, we define N as a compile-time constant. Alternatively, we could take it from the input and allocate the id array
dynamically.From Algorithms in C++
*/

Spiral Numbers

Print spiral number array like this:

7 8 9 10
6 1 2 11
5 4 3 12

Given coordinates of a point, find the corresponding number residing on it.

There are many solutions to this problem. For example, find the number by looking for the relation(function) between the number and its coordinates. The code below solves the problem without using such kind of relation. Of course, the cost is the increase of running time.

Bubble Sort

The Bubble sort has a worst-case running time of Θ(n^2).

//compare the consecutive numbers, larger one sinks to the bottom
void bubbleSort(int *a)
{
// int temp;
  for(int j = 0; j < arraysize; j++) 
  { 
    for( int i = 0; i < arraysize - j - 1;i++ )
    { 
       if( a[i] > a[i+1] ) 
      {swap(a[i], a[i+1]);} 
      }
  }
}

Heapsort

“Like merge sort, but unlike insertion sort, heapsort’s running time is O(n*lg(n)). Like insertion sort, but unlike merge sort, heapsort sorts in place: only a constant number of array elements are stored outside the input array at any time. Thus, heapsort combines the better attribute of the two sorting algorithms …” [Introduction to Algorithms]

void heapSort(int *a)
{
    for(int i = arraySize; i > 1; --i)
    {
        for(int k = 0; k < i; ++k)
        {
            // compare each element with its parent
            // if the child is begger than its parent
            // then swap them
            // keep doing this until reaching the root
            while((a[k] > a[k/2]) && (k > 0))
            { 
                swap(a[k], a[k/2]); 
                k = k/2; 
            }
        }
        // After the for loop, the largest is put at a[0]
        // then put the largest to the end of the array
        // and find the largest of the rest in the same way
        swap(a[0], a[i-1]);
    }
}

Merge Sort

The merge sort has a worst case running time of Θnlg(n).

Insertion Sort

Insertion sort has a worst-case running time of Θ(n^2).

void insertionSort(int *a, int n)
{
    for (int j = 1; j < n; ++j)
    {
        int key = a[j];

        // Insert A[j] into the sorted sequence A[0, 1,...,j-1]
        int i = j-1;
        while ((i >= 0) && (key < a[i]))
        {
            a[i+1] = a[i];
            --i;
        }
        a[i+1] = key;
    }
}