Radix Sort

CODE ::

#include <iostream>
#include <cstdlib>
#include <climits>
#include <queue>
using namespace std;
struct node {
    int data;
    struct node *link;
}*head;
void radixSort(int m, node *head)
{
    queue<int>qq[10];
    int i=0,temp;
    while(m>0)
    {
        node *ptr = head->link;
        while(ptr!=NULL)
        {
            temp = ptr->data;
            for(int j=0;j<i;j++)
                temp=temp/10;
            int ind = temp%10;
            qq[ind].push(ptr->data);
            ptr=ptr->link;
        }
        i++;
        m=m/10;
        ptr = head->link;
        for(int i=0;i<10;i++)
        {
            while(!qq[i].empty())
            {
                ptr->data = qq[i].front();
                qq[i].pop();
                ptr = ptr->link;
            }
        }
    }
}
int main()
{
    head = (node*) malloc(sizeof(node));
    head->link = NULL;
    node *temp = head;
    cout<<"Enter Number of elements: "<<endl;
    int n,max=INT_MIN;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        node *newnode = (node*) malloc(sizeof(node));
        newnode->data = rand()%1000;
        newnode->link =temp->link;
        temp->link = newnode;
        temp = newnode;
        max = max > newnode->data ? max : newnode->data;
    }
    radixSort(max,head);
    temp = head->link;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->link;
    }
    return 0;

}

Selection Sort (Knock Out Algorithm)

Algorithm ::

l ← n       ( here n is number of elements )

newindex ← n

while l ≠ 0 do

       index ← 1

       for i=2 to n do

             if a_index ≤ a_i

                        index ← i

        x_newindex ← a_index      ( here x is the new array )

        newindex ← newindex – 1

        a_index ← -∞

        l ← l -1

CODE :: 

#include <iostream>

#include <climits>

using namespace std;

int main()

{

    int arr[100],newarr[100],n;

    cout<<"Enter number of elements: "<<endl;

    cin>>n;

    cout<<"Enter elements: "<<endl;

    for(int i=1;i<=n;i++)

    {

        cin>>arr[i];

    }

    int limit=n;

    int new_index=n;

    while(limit--)

    {

        int index=1;

        for(int i=2;i<=n;i++)

        {

            index = arr[index]>=arr[i] ? index : i;

        }

        newarr[new_index--]=arr[index];

        arr[index]=INT_MIN;

    }

    cout<<"Sorted Array is: "<<endl;

    for(int i=1;i<=n;i++)

        cout<<newarr[i]<<" ";

    return 0;

}

Quick Sort

Algorithm : :

Quicksort ( f, l )

if ( f<l ) then

                i ← f+1

                while x_i < x_f do

                          i ← i + 1

                j ← l

                while x_j > x_f do

                         j ← j – 1

                while i < j do

                       x_i ↔ x_j

                      repeat i ← i + 1 until x_i ≥ x_f

                      repeat j ← j – 1 until x_j ≤ x_f

                x_j ↔ x_f

                Quicksort ( f, j-1)

                Quicksort (j+1, l)

CODE : : 

#include <iostream>
#include <algorithm>
#define MAX 10000000
using namespace std;
int x[MAX];
void QuickSort(int f, int l)
{
    int i,j;
    if(f<l)
    {
        i= f+1;
        while(x[i]<x[f]) i++;
        j=l;
        while(x[j]>x[f]) j--;
        while(i<j)
        {
            swap(x[i],x[j]);
            while(x[i]<x[f]) i++;
            while(x[j]>x[f]) j--;
        }
        swap(x[j],x[f]);
        QuickSort(f,j-1);
        QuickSort(j+1,l);
    }
}
int main ()
{
    int n;
    cout<<"Enter Number of Elements: "<<endl;
        cin>>n;
    cout<<"Enter Elements: "<<endl;
    for(int i=1;i<=n;i++)
        cin>>x[i];
    QuickSort(1,n);
    cout<<"Sorted Array: "<<endl;
    for(int i=1;i<=n;i++)
        cout<<x[i]<<" ";
    return 0;
}
 

Selection Sort

Algorithm : :

for j = n to 2 by -1 do

      t ← 1

      for k = 2 to j do

            if ( x_t < x_k ) then

                  t ← k

      x_{j ↔} x_t

 


CODE : :

#include <iostream>
using namespace std;
int main ()
{
    int n;
    cout<<"Enter number of elements:"<<endl;
    cin>>n;
    int arr[n+1];
    cout<<"Enter elements:"<<endl;
    for(int i=1;i<=n;i++)
        cin>>arr[i];
    for(int j=n;j>=2;j--)
    {
        int t=1;
        for(int k=2;k<=j;k++)
        {
            if(arr[t]<arr[k])
            {
                t=k;
            }
        }
        int temp=arr[j];
        arr[j]=arr[t];
        arr[t]=temp;
    }
    for(int i=1;i<=n;i++)
        cout<<arr[i]<<" ";
    return 0;
}
 

Insertion Sort

Algorithm : :

x₀ ← -∞

for j=2 to n do

     i ← j-1

     t ← x_j

while t < x_i do

           x_i+1 ← x_i

           i ← i-1

     x_i+1 ← t


CODE : :

#include <iostream>
using namespace std;
int main ()
{
    int array[100],n;
    cout<<"Enter Number of Elements:"<<endl;
    cin>>n;
    cout<<"Enter Elements:"<<endl;
    for(int i=1;i<=n;i++)
        cin>>array[i];
    array[0]=INT_MIN;
    for(int j=2;j<=n;j++)
    {
        int i=j-1;
        int t = array[j];
        while(t<array[i])
        {
            array[i+1]=array[i];
            i--;
        }
        array[i+1]=t;
    }
    for(int i=1;i<=n;i++)
        cout<<array[i]<<" ";
    return 0;
}

Bubble Sort

Algorithm::

k ← n //number of elements of array

    while k ≠ 0

              t ← 0

              for j=1 to k-1 do

                    if x_j > x_j+1 then   //here j is the index number

                        x_j ↔ x_j+1    

                             t ← j

               k ← t

Explanation::

Suppose we have an unsorted array like 8,7,5,1,12 , we have to sort this array at ascending order . We use bubble sort for sorting this array .

The algorithm of bubble sort is, it compare two numbers and when the if condition will true it swap two number to each other. At ending of every iteration the last number always will be highest number or lowest number according your condition .

Now, we see how to work this algorithm:

Iteration :: 1

Loop will be started from index 1 and ended at k-1 so, at 1st iteration loop will be cycled 4 times.

j=1,  8     7     5     1     12 ;  t=1

             swap

j=2,  7     8     5     1     12 ;  t=2
                       swap

j=3,  7     5     8     1     12 ;  t=3

                                  swap

j=4,  7     5     1     8     12 ;  t=3
                                            no swap

k=3;

After 1st iteration the array will be 7,5,1,8,12 

and k will be 3, cause after loop we assign the value of t at k.

Iteration :: 2

At this time the loop will be cycled k-1= 3-1= 2 times.

j=1  7     5     1     8     12 ; t=1
          swap

j=2  5     7      1     8     12 ; t=2
                    swap

k=3;

After 2nd iteration the array will be 5,1,7,8,12 and k will be 2

Iteration :: 3 

At this time the loop will be cycled k-1= 2-1= 1 times.

j=1  5     1     7     8     12 ;  t=1
       swap

k=1;

Iteration :: 4
t=0;
k=0;

After 3rd iteration the array will be 1,5,7,8,12 and k will be 1. This is our final array. But the while loop will be continued cause the loop condition still now true. At 4th iteration at starting time (t assigned by 0 at every iteration) t will be assigned by 0. But the for loop will not be executed at this time. So, k will be assigned by 0 and the while loop will be false next time.


CODE ::

#include <iostream>
using namespace std;
int main ()
{
    int array[100],n;
    cout<<"Enter Number of Elements:"<<endl;
    cin>>n;
    cout<<"Enter Elements:"<<endl;
    for(int i=1;i<=n;i++)
        cin>>array[i];
    int k = n;
    while(k!=0)
    {
        int t=0;
        for(int j=1;j<=k-1;j++)
        {
            int temp;
            if(array[j]>array[j+1])
            {
                temp = array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                t=j;
            }
        }
        k=t;
    }
    for(int i=1;i<=n;i++)
        cout<<array[i]<<" ";
    return 0;

}