Selection Sort - Recursive approach

Selecting Sort - Recurcive

Just like Bubble sort, selection sort has also a time complexity of O(n²) . Selection sort scans through the list iteratively, selects one item and places that item at its correct position in the list.

The efficiency of the algorithm is compared in terms of number of comparisons.
In selection sort algorithm there is (n-1) comparisons in first loop, (n-2) comparisons in second loop and so on.
So, there is total of (n-1) + (n-2) + ..... + 2 + 1 comparisons. Thus, the total no. of comparisons are
n*(n-1)/2. Thus, leading to the time complexity of O(n²).

The code for the selection sort with recursive algorithm is as follows:

// SELECTION SORT using Recursion  
#include<stdio.h>
#define MAX 5
void selectionsort(int *,int *);
void display(int *,int *);
int main()
{
    int a[MAX],n,i;
    printf("Enter the no. of elements in the array,where MAX=%d: ",MAX);
    scanf("%d",&n);
    for(;n>MAX;scanf("%d",&n))
    printf("The value entered is greater than MAX.Please re-enter the value: ");
    printf("Enter the elements of the array: \n");
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    printf("The unsorted array: ");
    display(a,a+n);
    printf("\n");
    selectionsort(a,a+n);
    printf("The sorted array: ");
    display(a,a+n);
    return 0;
}

void selectionsort(int *p,int *q)
{
    if(p!=q)
    {
    int i,temp,min_index=0;
    for(i=1;p+i<q;i++)
    if(*(p+i)<*(p+min_index))
    min_index=i;
    temp=*(p+min_index);
    *(p+min_index)=*p;
    *p=temp;
    selectionsort(p+1,q);
    }
}

void display(int *p,int *q)
{
    for(;p<q;p++)
    printf("%d ",*p);
}

Selection Sort - Sorting Techniques

Selecting Sort

Just like Bubble sort, selection sort has also a time complexity of O(n²) . Selection sort scans through the list iteratively, selects one item and places that item at its correct position in the list.

The efficiency of the algorithm is compared in terms of number of comparisons.
In selection sort algorithm there is (n-1) comparisons in first loop, (n-2) comparisons in second loop and so on.
So, there is total of (n-1) + (n-2) + ..... + 2 + 1 comparisons. Thus, the total no. of comparisons are
n*(n-1)/2. Thus, leading to the time complexity of O(n²).

The code for the selection sort is as follows:

//SELCETIONSORT
#include<stdio.h>
#define MAX 5
void selectionsort(int *,int *);
void display(int *,int *);
int main()
{
    int a[MAX],n,i;
    printf("Enter the no. of elements in the array,where MAX=%d: ",MAX);
    scanf("%d",&n);
    for(;n>MAX;scanf("%d",&n))
    printf("The value entered is greater than MAX.Please re-enter the value: ");
    printf("Enter the elements of the array: \n");
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    printf("The unsorted array: ");
    display(a,a+n);
    printf("\n");
    selectionsort(a,a+n);
    printf("The sorted array: ");
    display(a,a+n);
    return 0;
}

void selectionsort(int *p,int *q)
{
    if(p!=q)
    {
    int i,j,temp,min_index;
    for(j=0;p+j<q-1;j++)
    {
        min_index=j;
        for(i=j+1;p+i<q;i++)
        if(*(p+i)<*(p+min_index))
        min_index=i;
        temp=*(p+min_index);
        *(p+min_index)=*(p+j);
        *(p+j)=temp;
    }
    }
}

void display(int *p,int *q)
{
    for(;p<q;p++)
    printf("%d ",*p);
}

Insertion Sort

Insertion Sort

The Code provided below is the C-code for bubble sorting technique of an array.

//Insertionsort

#include<stdio.h>

#define MAX 5

void insertionsort(int *,int *);

void display(int *,int *);

int main()

{

    int a[MAX],n,i;

    printf("Enter the no. of elements in the array,where MAX=%d: ",MAX);

    scanf("%d",&n);

    for(;n>MAX;scanf("%d",&n))

    printf("The value entered is greater than MAX.Please re-enter the value: ");

    printf("Enter the elements of the array: \n");

    for(i=0;i<n;i++)

    scanf("%d",&a[i]);

    printf("The unsorted array: ");

    display(a,a+n);

    printf("\n");

    insertionsort(a,a+n);

    printf("The sorted array: ");

    display(a,a+n);

    return 0;

}



void insertionsort(int *p,int *q)

{

    if(p!=q)

    {

        int i,j,temp;

        for(i=1;p+i<q;i++)

        {

            j=i-1;

            temp=*(p+i);

            for(;j>=0 && *(p+j)>temp;j--)

            *(p+j+1)=*(p+j);

            *(p+j+1)=temp;

        }

    }

}



void display(int *p,int *q)

{

    for(;p<q;p++)

    printf("%d ",*p);

}

Bubble Sort - Recurrsion

Provided below is the Bubble Sorting C-Code based on a recursive algorithm instead of a iteration algorithm. It is the most basic and novice sorting algorithm.
The time complexity is O(n²).

The worst case time complexity is O(n2).

The average case time complexity is also O(n2).

The Bubble sort algo provided below has two functions other than main function namely, bubble sort - for sorting of the array and display - for the printing of the sorted array.

The code provided below uses recursive algorithm for the sorting purpose instead of itterative algorithm. 

//Bubblesort with recurrsion

#include<stdio.h>

#define MAX 10

void bubblesort(int *,int *);

void display(int *,int *);

int main()

{

    int a[MAX],n,i;

    printf("Enter the no. of elements in the array,where MAX=%d: ",MAX);

    scanf("%d",&n);

    for(;n>MAX;scanf("%d",&n))

    printf("The value entered is greater than MAX.Please re-enter the value: ");

    printf("Enter the elements of the array: \n");

    for(i=0;i<n;i++)

    scanf("%d",&a[i]);

    printf("The unsorted array: ");

    display(a,a+n);

    printf("\n");

    bubblesort(a,a+n);

    printf("The sorted array: ");

    display(a,a+n);

    return 0;

}



void bubblesort(int *p,int *q)

{

    if(p!=q)

    {

        int temp,i;

        for(i=0;p+i<q-1;i++)

        if(*(p+i)>*(p+i+1))

        {

            temp=*(p+i+1);

            *(p+1+i)=*(p+i);

            *(p+i)=temp;

        }

        bubblesort(p,q-1);

    }

}



void display(int *p,int *q)

{

    for(;p<q;p++)

    printf("%d ",*p);

}