Wednesday, 6 June 2012

C++ Program implementing all four types of sorting of a string

C++ Program implementing all four types of sorting of a string


#include <iostream.h>
#include <string.h>
#include <conio.h>
void MinSort(char*, int);
void BubbleSort(char*, int);
void InsertionSort(char*, int);
void ShellSort(char*, int);
int main()

    {
    clrscr();
    char cr[] = "skdmrsrjsrkpmnoprkseef";
    cout << "Data before sorting is "<<cr << endl;
    ShellSort(cr, strlen(cr));
    cout <<"Now the change is "<< cr << endl;
    getch();
    return 0;
}
// Complexity: n^2
void MinSort(char* array, int n)


    {
    int i, j, temp_index;
    char min;
    for (i=0; i < n-1; ++i)


    {
    temp_index = i;
    min = array[i];
    for (j = i+1; j < n; ++j)


        {
        if (array[j] < min)


        {
             temp_index = j;
             min = array[j];
        }
    }
    array[temp_index] = array[i];
    array[i] = min;
    }
}
// Complexity: n^2
void BubbleSort(char* array, int n)


    {
    int i, j;
    char temp;
    for (i = 0; i < n-1; ++i)
    for (j = i+1; j > 0; --j)
    if (array[j] < array[j-1])


    {
         temp = array[j];
         array[j] = array[j-1];
         array[j-1] = temp;
    }
}
// Complexity: n^2
void InsertionSort(char* array, int n)


    {
    int i, j;
    char temp;
    for (i=1; i < n; ++i)


    {
    temp = array[i];
    j = i-1;
    while ((j >= 0) && (temp < array[j]))


        {
        array[j+1] = array[j];
        j--;
    }
    array[j+1] = temp;
    }
}
// Complexity: n^1.2
void ShellSort(char* array, int n)


    {
    int i, j, k, s, gap_cnt;
    char temp;
    int gaps[5];
    gaps[0] = 9; gaps[1] = 5; gaps[2] = 3; gaps[3] = 2; gaps[4] = 1;
    for (gap_cnt = 0; gap_cnt < 5; gap_cnt++)


    {
    k = gaps[gap_cnt];
    s = -k;
    for (i = k; i < n; ++i)


        {
        temp = array[i];
        j = i-k;
        if (s == 0)


        {
             s = -k;
             s++;
             array[s] = temp;
        }
        while (temp < array[j] && j >= 0 && j <= n) // + Bound checking


        {
                     array[j+k] = array[j];
                     j = j-k;
            }
            array[j+k] = temp;
        }
    }
}

0 comments:

Post a Comment

Share

Twitter Delicious Facebook Digg Stumbleupon Favorites More