Quick Select

What is Quick Select Algorithm? How to implement in C++?

• The QuickSelect algorithm quickly finds the k-th smallest element of an unsorted array of n elements.
• It is an O(n), worst-case linear time, selection algorithm. A typical selection by sorting method would need atleast O(n log n) time.
• This algorithm is identical to quick sort but it does only a partial sort, since we already know which partition our desired element lies as the pivot is in final sorted position.

EXAMPLE:- Quick select implementation in C++

#include <iostream>
using namespace std;

// A simple print function
void print(int *input)
{
    for ( int i = 0; i < 5; i++ )
        cout << input[i] << " ";
    cout << endl;
}

int partition(int* input, int p, int r)
{
    int pivot = input[r];
    
    while ( p < r )
    {
        while ( input[p] < pivot )
            p++;
        
        while ( input[r] > pivot )
            r--;
        
        if ( input[p] == input[r] )
            p++;
        else if ( p < r ) {
            int tmp = input[p];
            input[p] = input[r];
            input[r] = tmp;
        }
    }
    
    return r;
}

int quick_select(int* input, int p, int r, int k)
{
    if ( p == r ) return input[p];
    int j = partition(input, p, r);
    int length = j - p + 1;
    if ( length == k ) return input[j];
    else if ( k < length ) return quick_select(input, p, j - 1, k);
    else  return quick_select(input, j + 1, r, k - length);
}

int main()
{
    int A1[] = { 100, 400, 300, 500, 200 };
    cout << "1st order element " << quick_select(A1, 0, 4, 1) << endl;
    int A2[] = { 100, 400, 300, 500, 200 };
    cout << "2nd order element " << quick_select(A2, 0, 4, 2) << endl;
    int A3[] = { 100, 400, 300, 500, 200 };
    cout << "3rd order element " << quick_select(A3, 0, 4, 3) << endl;
    int A4[] = { 100, 400, 300, 500, 200 };
    cout << "4th order element " << quick_select(A4, 0, 4, 4) << endl;
    int A5[] = { 100, 400, 300, 500, 200 };
    cout << "5th order element " << quick_select(A5, 0, 4, 5) << endl;
}

OUTPUT:-
1st order element 100
2nd order element 200
3rd order element 300
4th order element 400
5th order element 500

Read More

C++ Tries

What is a Trie? How to implement Tries in C++?

• Tries are used to index and search strings in a text.
• Some examples of tries usage include, finding the longest prefix match in a routing table, auto complete of web addresses in browser etc.
• Trie is a tree where each vertex represents a word or prefix.
• The root represents an empty string.
• Markers are used to indicate end of words.
• A typical node in a trie includes the content (a char), marker for end of word and a collection of children.
• An example of trie. (Using words Hello, Balloon, Ball)
  
  

EXAMPLE:- Demonstrate a simple implementation of search in a Trie

#include <iostream>
#include <vector>
using namespace std;

class Node {
public:
    Node() { mContent = ' '; mMarker = false; }
    ~Node() {}
    char content() { return mContent; }
    void setContent(char c) { mContent = c; }
    bool wordMarker() { return mMarker; }
    void setWordMarker() { mMarker = true; }
    Node* findChild(char c);
    void appendChild(Node* child) { mChildren.push_back(child); }
    vector<Node*> children() { return mChildren; }

private:
    char mContent;
    bool mMarker;
    vector<Node*> mChildren;
};

class Trie {
public:
    Trie();
    ~Trie();
    void addWord(string s);
    bool searchWord(string s);
    void deleteWord(string s);
private:
    Node* root;
};

Node* Node::findChild(char c)
{
    for ( int i = 0; i < mChildren.size(); i++ )
    {
        Node* tmp = mChildren.at(i);
        if ( tmp->content() == c )
        {
            return tmp;
        }
    }

    return NULL;
}

Trie::Trie()
{
    root = new Node();
}

Trie::~Trie()
{
    // Free memory
}

void Trie::addWord(string s)
{
    Node* current = root;

    if ( s.length() == 0 )
    {
        current->setWordMarker(); // an empty word
        return;
    }

    for ( int i = 0; i < s.length(); i++ )
    {        
        Node* child = current->findChild(s[i]);
        if ( child != NULL )
        {
            current = child;
        }
        else
        {
            Node* tmp = new Node();
            tmp->setContent(s[i]);
            current->appendChild(tmp);
            current = tmp;
        }
        if ( i == s.length() - 1 )
            current->setWordMarker();
    }
}


bool Trie::searchWord(string s)
{
    Node* current = root;

    while ( current != NULL )
    {
        for ( int i = 0; i < s.length(); i++ )
        {
            Node* tmp = current->findChild(s[i]);
            if ( tmp == NULL )
                return false;
            current = tmp;
        }

        if ( current->wordMarker() )
            return true;
        else
            return false;
    }

    return false;
}


// Test program
int main()
{
    Trie* trie = new Trie();
    trie->addWord("Hello");
    trie->addWord("Balloon");
    trie->addWord("Ball");

    if ( trie->searchWord("Hell") )
        cout << "Found Hell" << endl;

    if ( trie->searchWord("Hello") )
        cout << "Found Hello" << endl;

    if ( trie->searchWord("Helloo") )
        cout << "Found Helloo" << endl;

    if ( trie->searchWord("Ball") )
        cout << "Found Ball" << endl;

    if ( trie->searchWord("Balloon") )
        cout << "Found Balloon" << endl;

    delete trie;
}

OUTPUT:-
Found Hello
Found Ball
Found Balloon

Read More

Merge Sort

What is Merge Sort algorithm? How to implement Merge Sort in C++?

• Merge Sort  is a divide and conquer algorithm.
• In the best/ average/ worst case it gives a time complexity of O(n log n).

Conceptually, a merge sort works as follows:

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.

(Reference: http://en.wikipedia.org/wiki/Merge_sort)

 EXAMPLE: Demonstrate a simple merge sort implementation

#include <iostream>
#include <cmath>
using namespace std;

const int INPUT_SIZE = 10;

// A simple print function
void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

void merge(int* input, int p, int r)
{
    int mid = floor((p + r) / 2);
    int i1 = 0;
    int i2 = p;
    int i3 = mid + 1;

    // Temp array
    int temp[r-p+1];

    // Merge in sorted form the 2 arrays
    while ( i2 <= mid && i3 <= r )
        if ( input[i2] < input[i3] )
            temp[i1++] = input[i2++];
        else
            temp[i1++] = input[i3++];

    // Merge the remaining elements in left array
    while ( i2 <= mid )
        temp[i1++] = input[i2++];

    // Merge the remaining elements in right array
    while ( i3 <= r )
        temp[i1++] = input[i3++];

    // Move from temp array to master array
    for ( int i = p; i <= r; i++ )
        input[i] = temp[i-p];
}

void merge_sort(int* input, int p, int r)
{
    if ( p < r )
    {
        int mid = floor((p + r) / 2);
        merge_sort(input, p, mid);
        merge_sort(input, mid + 1, r);
        merge(input, p, r);
    }
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    merge_sort(input, 0, 9);
    cout << "Output: ";
    print(input);
    return 0;
}
OUTPUT:-
Input: 500 700 800 100 300 200 900 400 1000 600
Output: 100 200 300 400 500 600 700 800 900 1000

Read More

Facade Pattern

What is Facade Pattern?

• It is a structural design pattern.
• Makes an existing complex software library easier to use by providing a simpler interface for common tasks.
• Allows the applications/ clients using the library de-coupled from inner workings of a complex library.

EXAMPLE:- Demonstrate a simple Facade Pattern in C++

#include <iostream>
using namespace std;

// Transfer library
class Usb {
public:
    bool isAvailable()
    {
        return false;
    }

    void connect()
    {
        cout << "Connecting via USB" << endl;
    }

    void send(string file)
    {
        cout << file << " sent." << endl;
    }
};

class Bluetooth {
public:
    bool isAvailable()
    {
        return true;
    }

    void connect()
    {
        cout << "Connecting via BT" << endl;
    }

    void authenticate()
    {
        cout << "Authenticating BT" << endl;
    }

    void send(string file)
    {
        cout << file << " sent." << endl;
    }
};

// The Facade
class FileTransfer {
public:
    void sendFile(string fileName)
    {
        Usb* u = new Usb();
        Bluetooth* b = new Bluetooth();
        if ( u->isAvailable() )
        {
            u->connect();
            u->send(fileName);
        }
        else if ( b->isAvailable() )
        {
            b->connect();
            b->authenticate();
            b->send(fileName);
        }
        else
        {
            cout << "Not sent" << endl;
        }
        delete b;
        delete u;
    }
};

// Test Program
int main()
{
    FileTransfer* ft = new FileTransfer();
    ft->sendFile("mypicture");
    delete ft;
}

OUTPUT:-
Connecting via BT
Authenticating BT
mypicture sent.

Read More

Visitor Pattern

What is a visitor pattern?

• The visitor pattern is a behavioral design pattern. 


• This pattern allows to seperate the data structures and the algorithms to be applied on the data.


• Both data structure objects and algorithm objects can evolve seperately. Makes development and changes easier.


• Data structure (element) objects have an "accept" method which take in a visitor (algorithmic) object.


• Algorithmic objects have a "visit" method which take in a data structure object.

EXAMPLE:- Demonstrate a simple visitor pattern using C++

#include <iostream>

#include <list>

using namespace std;



// Forwards

class VisitorIntf;



// Abstract interface for Element objects

class ElementIntf

{

public:

    virtual string name() = 0;

    virtual void accept(VisitorIntf* object) = 0;

};



// Abstract interface for Visitor objects

class VisitorIntf

{

public:

    virtual void visit(ElementIntf* object) = 0;

};



// Concrete element object

class ConcreteElement1 : public ElementIntf

{

public:

    string name()

    {

        return "ConcreteElement1";

    }



    void accept(VisitorIntf *object)

    {

        object->visit(this);

    }

};





// Concrete element object

class ConcreteElement2 : public ElementIntf

{

public:

    string name()

    {

        return "ConcreteElement2";

    }



    void accept(VisitorIntf *object)

    {

        object->visit(this);

    }

};



// Visitor logic 1

class ConcreteVisitor1 : public VisitorIntf

{

public:

    void visit(ElementIntf *object)

    {

        cout << "Visited " << object->name() <<

                " using ConcreteVisitor1." << endl;

    }

};



// Visitor logic 2

class ConcreteVisitor2 : public VisitorIntf

{

public:

    void visit(ElementIntf *object)

    {

        cout << "Visited " << object->name() <<

             " using ConcreteVisitor2." << endl;

    }

};



//  Test main program

int main()

{

    list<ElementIntf*> elementList1;

    elementList1.push_back(new ConcreteElement1());

    elementList1.push_back(new ConcreteElement2());



    VisitorIntf* visitor1 = new ConcreteVisitor1();

    while ( ! elementList1.empty() )

    {

        ElementIntf* element = elementList1.front();

        element->accept(visitor1);

        elementList1.pop_front();

    }



    list<ElementIntf*> elementList2;

    elementList2.push_back(new ConcreteElement1());

    elementList2.push_back(new ConcreteElement2());

    VisitorIntf* visitor2 = new ConcreteVisitor2();

    while ( ! elementList2.empty() )

    {

        ElementIntf* element = elementList2.front();

        element->accept(visitor2);

        elementList2.pop_front();

    }



    delete visitor1;

    delete visitor2;

}



OUTPUT:-

Visited ConcreteElement1 using ConcreteVisitor1.

Visited ConcreteElement2 using ConcreteVisitor1.

Visited ConcreteElement1 using ConcreteVisitor2.

Visited ConcreteElement2 using ConcreteVisitor2.

Read More