Implementation of 8 sorting Algorithms using Abstract Class & Templates in C++.

-


Problem:
Implementation of 8 sorting Algorithms using Abstract Class in C++ which includes : -

        o Bubble sort
        o Selection Sort
        o Insertion Sort
        o Shell Sort
        o Quick Sort
        o Merge Sort
        o Heap Sort
        o Radix Sort


        Solution :

#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;

template <class T>
class sort {
public:
    virtual void sorting(T *a, int beg, int n) = 0;
    void swap(T &a, T &b);
    void createlist(T *a, int n);
    void display(T *a, int n);
};

template <class T>
void sort<T>::createlist(T *a, int n) {
    int i;
    for (i = 0; i < n; i++) {
        cout << "Enter a[" << i << "]:";
        cin >> a[i];
    }
}

template <class T>
void sort<T>::display(T *a, int n) {
    int i;
    cout << "[ ";
    for (i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << "]\n";

}

template <class T>
void sort<T>::swap(T &a, T &b) {
    a = a + b;
    b = a - b;
    a = a - b;
}

/*=====================================================================================*/

template <class T>
class bubble : public sort<T> {
public:
    void sorting(T *a, int beg, int n);
};

template<class T>
void bubble<T>::sorting(T *a, int beg, int n) {
    int j, i;
    for (j = beg + 1; j < n; j++) {
        for (i = beg; i < n - j; i++)
            if (a[i] > a[i + 1])
                swap(a[i], a[i + 1]);

    }
}

/*=====================================================================================*/
template <class T>
class selection : public sort<T> {
public:
    void sorting(T *a, int beg, int n);
};

template<class T>
void selection<T>::sorting(T *a, int beg, int n) {
    int i, j, min, t = 0;
    for (j = beg; j < n; j++) {
        min = j;
        for (i = j + 1; i < n; i++)
            if (a[min] > a[i])
                min = i;

        swap(a[t++], a[min]);
    }
}

/*=====================================================================================*/
template <class T>
class insertion : public sort<T> {
public:
    void sorting(T *a, int beg, int n);
};

template<class T>
void insertion<T>::sorting(T *a, int beg, int n) {
    int i, j, item;
    for (j = beg + 1; j < n; j++) {
        for (i = j; i >= 1 && a[i] < a[i - 1]; i--) {
            swap(a[i], a[i - 1]);
            display(a, n);
        }
    }
}

/*=====================================================================================*/
template <class T>
class shell : public sort<T> {
public:
    void sorting(T *a, int beg, int n);
};

template<class T>
void shell<T>::sorting(T *a, int beg, int n) {
    int i, j, inc = 3, temp;
    while (inc > 0) {
        for (j = beg + 1; j < n; j++)
            for (i = j; i >= inc && a[i] < a[i - inc]; i--)
                swap(a[i], a[i - inc]);

        (inc / 2) ? inc = inc / 2 : (inc == 1) ? inc = 0 : inc = 1;
    }
}

/*=====================================================================================*/
template <class T>
class quick : public sort<T> {
public:
    void sorting(T *a, int beg, int n);
    int partition(T *a, int low, int high);
};

template<class T>
void quick<T>::sorting(T *a, int low, int high) /* Quick Sort */ {
    int p;

    if ((high - low) > 0) {
        p = partition(a, low, high);
        quick::sorting(a, low, p - 1);
        quick::sorting(a, p + 1, high);
    }

}

template<class T>
int quick<T>::partition(T *a, int low, int high) /* partition */ {
    int left, right;
    T pivot = a[low];
    left = low;
    right = high;
    while (left < right) {
        display(a, high + 1);
        while (a[left] <= pivot) left++; /* Move left while item < pivot */

        while (a[right] > pivot) right--; /* Move right while item > pivot */

        if (left < right) swap(a[left], a[right]);
    }
    a[low] = a[right];
    a[right] = pivot;

    return right;
}

/*=====================================================================================*/

template <class T>
class Merge : public sort<T> {
public:
    void sorting(T *a, int beg, int n);
    void merge(T *a, int low, int mid, int high);
};

template <class T>
void Merge<T>::sorting(T *a, int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        Merge::sorting(a, low, mid);
        Merge::sorting(a, mid + 1, high);
        merge(a, low, mid, high);
    }
}

template <class T>
void Merge<T>::merge(T *a, int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    T c[10]; /* Variable declaration alongwith assignment */

    while ((i <= mid)&&(j <= high))
        c[k++] = (a[i] < a[j]) ? a[i++] : a[j++];

    while (i <= mid) c[k++] = a[i++];

    while (j <= high) c[k++] = a[j++];

    for (i = low; i < k; i++) a[i] = c[i];

}

/*=====================================================================================*/

template <class T>
class heap : public sort<T> {
public:
    void sorting(T *a, int beg, int n);
    void heapify(T *a, int i, int n);
};

template <class T>
void heap<T>::sorting(T *a, int beg, int n) {
    int i;
    for (i = (n - 1) / 2; i >= beg; i--)
        heapify(a, i, n - 1);

    for (i = n - 1; i >= beg; i--) {
        swap(a[beg], a[i]);
        heapify(a, beg, i);
    }
}

template <class T>
void heap<T>::heapify(T *a, int i, int n) {
    int j = 2 * i + 1;
    T item = a[i];
    while (j <= n - 1) {
        if (j < n - 1) {
            if (a[j] < a[j + 1])
                j++;
        }
        if (item > a[j])
            break;
        else
            a[j / 2] = a[j];
        j = 2 * j;
    }
    a[j / 2] = item;
}

/*=====================================================================================*/
template <class T>
class Radix : public sort<T> {
protected:
    void sorting(T *a, int beg, int n);
    T large(T *a, int n);
    int no_of_digit(T n);
};

template <class T>
T Radix<T>::large(T *a, int n) {
    int i, max = 0;
    for (i = 1; i < n; i++)
        if (a[max] < a[i])
            max = i;

    return a[max];
}

template <class T>
int Radix<T>::no_of_digit(T n) {
    int count = 0;
    while (n > 0) {
        count++;
        n = n / 10;
    }
    return count;
}

template <class T>
void Radix<T>::sorting(T *a, int beg, int n) {
    T bucket[10][5], buck[10], largest = large(a, n);
    int i, j, k, l, div = 1, pass, number = no_of_digit(largest);
    for (pass = 0; pass < number; pass++) {
        for (k = 0; k < 10; k++)
            buck[k] = 0;
        for (i = beg; i < n; i++) {
            l = (a[i] / div) % 10;
            bucket[l][buck[l]++] = a[i];
        }
        i = beg;
        for (k = 0; k < 10; k++) {
            for (j = 0; j < buck[k]; j++)
                a[i++] = bucket[k][j];
        }
        div *= 10;
    }
}

/*=====================================================================================*/

int main() {
    int *a, n, choice, data_type_choice;
    float *b;
    string str[20];
    while (1) {
        check:
        cout << "-----------------------------" << endl;
        cout << "Menu Selection For Data Type" << endl;
        cout << "-----------------------------" << endl;
        cout << "1: Integer\n2: Float\n3: String\n0: Exit." << endl;
        cout << "-----------------------------" << endl;
        cout << "\nEnter Your Choice[0-3]:";
        cin >> data_type_choice;
        if (data_type_choice == 1) {
            sort <int>*ptr;
            bubble <int>bub;
            selection <int>sel;
            insertion <int>ins;
            shell <int>shl;
            quick <int>qck;
            heap <int>hep;
            Merge <int>mrg;
            Radix <int>rad;

            cout << "---------------------------" << endl;
            cout << "Menu Selection For Sorting" << endl;
            cout << "---------------------------" << endl;
            cout << "1: Bubble Sort\n2: Selection Sort" << endl;
            cout << "3: Insertion Sort\n4: Shell Sort" << endl;
            cout << "5: Heap Sort\n6: Radix Sort" << endl;
            cout << "7: Quick Sort\n8: Merge Sort" << endl;
            cout << "---------------------------" << endl;
            cout << "\nEnter Your Choice[1-8]:";
            cin >> choice;
            switch (choice) {
                case 1: ptr = &bub;
                    break;
                case 2: ptr = &sel;
                    break;
                case 3: ptr = &ins;
                    break;
                case 4: ptr = &shl;
                    break;
                case 5: ptr = &hep;
                    break;
                case 6: ptr = &rad;
                    break;
                case 7: ptr = &qck;
                    break;
                case 8: ptr = &mrg;
                    break;
                default:cout << "invalid Selection" << endl;
                    break;
            }
            if (choice >= 1 && choice <= 8) {
                cout << "--------------------------------\n";
                cout << "How Many Integers You Want To Sort:";
                cin >> n;
                a = (int*) malloc(sizeof (int)*n);
                ptr->createlist(a, n);
                cout << "Unsorted List: ";
                ptr->display(a, n);
                (choice >= 1 && choice <= 6) ? ptr->sorting(a, 0, n) : ptr->sorting(a, 0, n - 1);
                cout << "Sorted List: ";
                ptr->display(a, n);
                cout << "--------------------------------\n";
            }
        } else
            if (data_type_choice == 2) {
            sort <float>*ptr;
            bubble <float>bub;
            selection <float>sel;
            insertion <float>ins;
            shell <float>shl;
            quick <float>qck;
            heap <float>hep;
            Merge <float>mrg;
            cout << "---------------------------" << endl;
            cout << "Menu Selection For Sorting" << endl;
            cout << "---------------------------" << endl;
            cout << "1: Bubble Sort\n2: Selection Sort" << endl;
            cout << "3: Insertion Sort\n4: Shell Sort" << endl;
            cout << "5: Heap Sort" << endl;
            cout << "6: Quick Sort\n7: Merge Sort" << endl;
            cout << "---------------------------" << endl;
            cout << "\nEnter Your Choice[1-8]:";
            cin >> choice;
            switch (choice) {
                case 1: ptr = &bub;
                    break;
                case 2: ptr = &sel;
                    break;
                case 3: ptr = &ins;
                    break;
                case 4: ptr = &shl;
                    break;
                case 5: ptr = &hep;
                    break;
                case 6: ptr = &qck;
                    break;
                case 7: ptr = &mrg;
                    break;
                default:cout << "invalid Selection" << endl;
                    break;
            }
            if (choice >= 1 && choice <= 7) {
                cout << "--------------------------------\n";
                cout << "How Many Floats You Want To Sort:";
                cin >> n;
                b = (float*) malloc(sizeof (float)*n);
                ptr->createlist(b, n);
                cout << "Unsorted List: ";
                ptr->display(b, n);
                (choice >= 1 && choice <= 5) ? ptr->sorting(b, 0, n) : ptr->sorting(b, 0, n - 1);
                cout << "Sorted List: ";
                ptr->display(b, n);
                cout << "--------------------------------\n";
            }
        } else
            if (data_type_choice == 3) {
            sort <string>*ptr;
            bubble <string>bub;
            selection <string>sel;
            insertion <string>ins;
            shell <string>shl;
            quick <string>qck;
            Merge <string>mrg;
            heap <string>hep;

            cout << "---------------------------" << endl;
            cout << "Menu Selection For Sorting" << endl;
            cout << "---------------------------" << endl;
            cout << "1: Bubble Sort\n2: Selection Sort" << endl;
            cout << "3: Insertion Sort\n4: Shell Sort" << endl;
            cout << "5: Heap Sort" << endl;
            cout << "6: Quick Sort\n7: Merge Sort" << endl;
            cout << "---------------------------" << endl;
            cout << "\nEnter Your Choice[1-8]:";
            cin >> choice;
            switch (choice) {
                case 1: ptr = &bub;
                    break;
                case 2: ptr = &sel;
                    break;
                case 3: ptr = &ins;
                    break;
                case 4: ptr = &shl;
                    break;
                case 5: ptr = &hep;
                    break;
                case 6: ptr = &qck;
                    break;
                case 7: ptr = &mrg;
                    break;
                default:cout << "invalid Selection" << endl;
                    break;
            }
            if (choice >= 1 && choice <= 7) {
                cout << "--------------------------------\n";
                cout << "How Many Strings You Want To Sort:";
                cin >> n;
                ptr->createlist(str, n);
                cout << "Unsorted List: ";
                ptr->display(str, n);
                (choice >= 1 && choice <= 5) ? ptr->sorting(str, 0, n) : ptr->sorting(str, 0, n - 1);
                cout << "Sorted List: ";
                ptr->display(str, n);
                cout << "--------------------------------\n";
            }
        } else
            if (data_type_choice == 0) {
            cout << "Good Bye...!!!" << endl;
            exit(0);
        }
    }
    return 0;
}
/*********************************  The End    ***************************************/

Popular posts from this blog

8 Bit Plane Slicing of an image in Image Processing

-
Image
%================ Bit Plane Slicing Program =================% A=imread('bit_plane_img.tif'); subplot(3,3,1),imshow(A),title('INPUT IMAGE'); for i=1:8     B=bitplaneslicing(A,i);     subplot(3,3,i+1),imshow(B),title(i); end %====================================================% %================ Bit Plane Slicing Function =================% function [ B ] = bitplaneslicing( A ,n) % function for n bit plane slicing where n<=8 [M,N]=size(A); B=zeros(M,N); for i = 1:M     for j = 1:N         str=dec2bin(A(i,j),8);         if strcmp(str(9-n),'0')             B(i,j)=0;         else             B(i,j)=2^(n-1);         end     end end end %====================================================% Input Image: bit_plane_img.tif Output Image:
Read more

Code to upload multiple files simultaneously using JSP, Servlet .

-
Image
Step 1 : Create a jsp page. index.jsp <%--      Document   : index     Created on : 21 Sep, 2013, 5:58:32 PM     Author     : snlkjha --%> <%@page contentType="text/html" pageEncoding="UTF-8"%> <!DOCTYPE html> <html>     <head>         <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">         <title>JSP Page</title>     </head>     <body>         <form action="UploadServlet" method="post" enctype="multipart/form-data">             <input type="file" id="file" name="file1" accept="image/*"  multiple="muliple" required/><br>             <input type="submit"/>            <br><br> ${requestScope.message} ...
Read more

STRING PALINDROME USING STACK AND QUEUE

-
#include<stdio.h> #include<stdlib.h> #include<string.h> void push(char ); char pop(); void nq(char ); char dq(); typedef struct list {     char data;     struct list *next; }node; node *top=NULL,*front=NULL,*rear=NULL; int main() {     char word[20];     printf("Type the Word:");     scanf("%s",word);     int length=strlen(word),i=0;     while(word[i]!='\0')     {         push(word[i]);         nq(word[i]);         i++;     }     for(i=0;i<length;i++)     {         if(pop()!=dq())         break;             }     if(i==length)        ...
Read more