Ronzii's Blog

Just your average geek's blog

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))

Advertisements

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

Kruskal’s algorithm

Kruskals Algorithm is used to find the minimum spanning tree for a connected weighted graph and is an ideal greedy algorithm. Additionally, I’ve calculated the total weight of the Minimum Spanning Tree.

Algorithm

1. Take a Forest or a set of edges as input.

2. Create sets for each vertices. What I’ve done is merely kept track of the parent of each list i.e if the parent is same then they belong to the same list.

3. Now, Sort all the edges in non-decreasing order of their weights.

4. Extract the smallest edge (u,v). Compare whether they belong to the same set or not.  If the edge connects two different trees add it to the MST otherwise discard that edge.

The time complexity of this algorithm is O(E log V) where E is number of edges and V is number of vertices.

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#define MAX 10001
#define edge pair<int,int>
using namespace std;
vector< pair<int, edge > > Graph,MST;
int n,e,parent[MAX];
void initialize(int n)
{
    for(int i=1; i<=n; i++)
    {
        parent[i] = i;
    }
    MST.clear();
    Graph.clear();
}
int findSet(int x, int *parent)
{
    if(x!=parent[x])
    {
        parent[x] = findSet(parent[x],parent);
    }
    return parent[x];
}
void kruskal()
{
    sort(Graph.begin(),Graph.end());
    int total = 0;
    for(int i=0; i<e; i++)
    {
        int pu = findSet(Graph[i].second.first,parent);
        int pv = findSet(Graph[i].second.second,parent);
        if(pu!=pv)
        {
            total+=Graph[i].first;
            MST.push_back(Graph[i]);
            parent[pu] = parent[pv];
        }
    }
    cout<<total<<"\n";
}
int main()
{
    cin>>n>>e;
    initialize(n);
    int u,v,w;
    for(int i=0; i<e; i++)
    {
        cin>>u>>v>>w;
        Graph.push_back(pair<int, edge>(w,edge(u,v)));
    }
    kruskal();
    return 0;
}

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

Intern @ One97

Its been a month since I started as an intern at One97 Communications Limited. So far, I have had the greatest lunches, met great people and the most fun part, I have done no work at all. Apparently, there is an internal agenda that interns are not supposed to be given relevant work. Initially, it pissed me off to no end but  I soon realized it was a blessing in disguise. I was able to figure out my career options with the help of my co-workers , check out the “Hot” HR’s there 😉 and started SPOJ(Don’t judge me, I was bored)

Since the founder of the company is also a DCE passout, they treat DCEites with great respect and my general observation has been that all of the alumni I met here have high salary jobs. Simply because “DCE ki chaud hain!”.

Also, this is the company’s founders reply on reading this post

 

 


 

July 7, 2011 Posted by | Fun | , | 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

Dijkstra’s algorithm using STL

Dijkstra’s algorithm requires a priority queue so I have used STL’s inbuilt priority queue functions. The class Prioritize ensures that the queue remains sorted according to the first value of the pair<int,int> object

Algorithm
1. Assign to every node a distance value: set it to zero for our initial node and to infinity(999) for all other nodes. Mark all nodes as unvisited.
2. Set initial source as current.
3.  Consider all its unvisited neighbors and calculate their distance. For example, if current node (A) has distance of 1, and an edge connecting it with another node (B) is 2, the distance to B through A will be 1+2=3
4.When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal
5. The next current node will be the node with the lowest distance in the unvisited set that is the topmost element of the priority queue.

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define pp pair<int,int>
using namespace std;
class Prioritize
{
public:
    int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second < p2.second;
    }
};
int main()
{
    priority_queue<pp, vector<pp > , Prioritize > Q;
    int n;
    cin>>n;
    vector< pp > G[n+1];
    int e,u,v,w;
    cin>>e;
    for(int i=0;i<e;i++)
    {
        cin>>u>>v>>w;
        G[u].push_back(pp(v,w));
        G[v].push_back(pp(u,w));
    }
    int s;
    cin>>s;
    int d[n+1];
    for(int i=1;i<=n;i++)
    {
        d[i] = 999;
    }
    d[s] = 0;
    Q.push(pp(s,d[s]));
    while(!Q.empty())
    {
        u = Q.top().first;
        Q.pop();
        int size = G[u].size();
        for(int i = 0 ; i < size ; i++)
        {
            v = G[u][i].first;
            w = G[u][i].second;
            cout<<u<<" "<<v<<" "<<w<<endl;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push(pp(v,d[v]));
            }
        }
    }
    for(int i=1; i<=n; i++) printf("Node %d, min weight = %d\n", i, d[i]);
    return 0;
}

July 7, 2011 Posted by | C++ | , , , , | 2 Comments