Ronzii's Blog

Just your average geek's blog

Counting Sort

It is an algorithm that is used to sorting a group of integers/ characters on that basis of keys. The complexity of this function is O(n) but it uses extra space for storing the integers and this should only be used when the maximum value in the array since we need to know the size of auxiliary array to be used.

Algorithm

1. Count the occurrences of the integer in an auxiliary array.

2.  Precompute the positions of the integers by adding the last index to the current index i.e C[i]+=C[i-1]

3. Find position of the integer based on the pre-computed index array

void countingSort(int A[], int length,int max)
{
    int C[max];
    for(int i=0; i<max; i++)
    {
        C[i]=0;
    }
    for(int i=0; i<length; i++)
    {
        C[A[i]]+=1;
    }
    for(int i=1; i<max; i++)
    {
        C[i]+=C[i-1];
    }
    int B[length];
    for(int j=length-1; j>=0; j--)
    {
        B[C[A[j]]-1]=A[j];
        C[A[j]]-=1;
    }
}

July 10, 2011 Posted by | C++, Sorting | , , | 1 Comment

Merge Sort

Merge sort is a divide and conquer algorithm that recursively compares halves of arrays. The time complexity of this algorithm is O(n* log(n)). However, heap sort is definitely better since it requires less auxiliary space. But merge sort is often used for sorting linked lists since it requires O(1) space in linked lists. I will be uploading a program for Sorting Linked Lists soon
Algorithm

  1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
  2. Divide the unsorted list into two sublists of about half the size.
  3. Sort each sublist recursively by re-applying the merge sort.
  4. Merge the two sublists back into one sorted list
void mergeSort(int a[],int left, int right)
{
    if(left<right)
    {
        int middle = (left+right)/2;
        mergeSort(a,left,middle);
        mergeSort(a,middle+1,right);
        merge(a,left,middle,right);
    }
}

The merge function is used to combine to two sorted sublists  

void merge(int a[], int p, int q, int r)
{
    int n1=q-p+1,n2=r-q;
    int i,j,k;
    int L[n1],R[n2];
    for(i=0; i<n1; i++)
    {
        L[i]=a[p+i];
    }
    for(j=0; j<n2; j++)
    {
        // Tricky
        R[j]=a[q+j+1];
    }
    i=0,j=0,k=p;
    while(i<n1 && j<n2)
    {
        if(L[i]<=R[j])
        {
            a[k++]=L[i++];
        }
        else
        {
            a[k++]=R[j++];
        }
    }
    while(i<n1)
    {
        a[k++]=L[i++];
    }
    while(i<n2)
    {
        a[k++]=R[j++];
    }

}

July 8, 2011 Posted by | C++, Sorting | , , | Leave a comment

Heap Sort

Heap Sort is a comparison based sorting algorithm. The logical structure of a heap is such that a parent(i) should be larger than its children at 2*i and 2*i+1.  The following example illustrates the structure of a heap. Eg. 100 is parent, 19 and 36 are its children. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap Here are some auxiliary functions that would be required to implement heap sort

int leftChild(int n)
{
    return 2*n;
}
int rightChild(int n)
{
    return (2*n+1);
}

Heap-sort begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the partially sorted array. Each and every node in the array must follow the above structure.

void heapify(int a[],int length,int i)
{
    int left = leftChild(i);
    int right = rightChild(i);
    int largest = i;
    if(left<length && a[left] > a[i])
    {
        largest = left;
    }
    if(right<length && a[right]>a[largest])
    {
        largest  = right;
    }
    if(largest!=i)
    {
        swap(a[i],a[largest]);
        heapify(a,length,largest);
    }
}

This function is used to compare a root node with its 2 children and replace the root node with the largest of all three. As we can see this function is recursive, if the position of the element has been changed then heapify must be called again to ensure the rest of structure obeys the properties of a heap. The complexity of this function is O(log(n))
Now, to build a max heap we just need a for loop 🙂

void buildMaxHeap(int a[], int length)
{
    for(int i = (length-1)/2; i>=0; i--)
    {
        heapify(a,length,i);
    }
}

This function has a average running time of O(n* log(n)) as is apparent from the complexity of the for loop and heapify function.
Now, our array has been transformed into a heap. We can perform heap sort.
The main concept heap-sort follows is that the largest element is always at the top of the list. We swap this element to the end of the list, decreased the length of the list and then heapify the first node of the list.

void heapSort(int a[],int length)
{
    buildMaxHeap(a,length);
    for(int i= length-1 ; i>0; i--)
    {
        swap(a[0],a[i]);
        length--;
        heapify(a,length,0);
    }
}

The complexity of this function is O(n* log(n)) and requires pre-computation of O(n* log(n))

July 7, 2011 Posted by | C++, Sorting | , , , | Leave a comment

Insertion Sort

Insertion sort is effective in sorting small lists and is often used to improve merge sort. Now,Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.

Array prior to the insertion of x

becomes

Array after the insertion of x
The time complexity is O(n*log(n)) but it in general in writes to array O(n^2) times whereas selection sort writes only O(n) times.

void insertionSort(int a[], int n)
{
    int temp;
    for(int i=1; i<n; i++)
    {
        temp = a[i];
        int j=i-1;
        while(temp<a[j] && j>=0)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

July 7, 2011 Posted by | C++, Sorting | , , | Leave a comment

Selection Sort

Selection sort should be used when the number of comparisons are to be minimized. So this algorithm should be used when auxiliary memory is limited. The algorithms works to find the smallest element in the array and puts it at the first index, then it finds the second most smallest element in the list and places it at the second index. The time complexity of this algorithm is O(n*log(n))

void selectionSort(int a[],int n)
{
    int smallest;
    for(int i = 0 ; i<n; i++)
    {
        smallest = i;
        for(int j = i+1; j<n; j++)
        {
            if(a[j]<a[smallest])
            {
                swap(a[j],a[smallest]);
            }
        }
    }
}

July 7, 2011 Posted by | C++, Sorting | , , | Leave a comment

Bubble Sort

Bubble sort is the simplest of all sorting algorithms. The following is an illustration of how it operates. As we can see it compares 2 adjacent elements and swaps if A[j]>A[j+1]. The time complexity of this algorithm is O(n^2)

void bubbleSort(int a[],int n)
{
    for(int i = 0; i < n ; i++)
    {
        for(int j = 0 ; j<n-1 ; j++)
        {
            if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
            }
        }
    }
}

July 7, 2011 Posted by | C++, Sorting | , , | Leave a comment