Sorting algorithm in discrete structure with program

Sorting algorithm in discrete structure : Is the process of arranging the element of a list of file in any specific order which may be ascending or descending. For example all list of words could be sorted alphabetically or by length. All list of cities could be sorted by population by area or by zip code. In our smartphone, contact a display on alphabetical order that is they are arranged internally according to alphabets and so on .sorting is among the most basic problem in algorithm design. Here we discuss Bubble and insertion sorting algorithm in discrete structure.

what is Bubble sorting in discrete structure?

Bubble sort is very simple sorting technique. The basic idea underlying the Bubble sort is to pass or scan through the list of elements sequentially several time. Each pass consist of comparing each element in the list with its successor(x[i] with x[x+1], where x is list of element and x[i] and x[i+1] represent ith and i+1th element in the list respectively) and  interchanging the two element if they are not in proper order. All neighboring element are compare and exchange if required.

Bubble sorting algorithm

This algorithm sorts the array list with n elements:

• step1: initialization set i=1
• step2: Repeat step 3 to 7 until i<n
• step3: set j=0
• step4: Repeat step 5 to 6 until j<n-i-1
• step5: If list[j]>list[j+1] set temp=list[j], set list[j]=list[j+1], set list[j+1]= temp End if
• step6: j=j+1
• step7: i=i+1
• step8: stop.

Insertion sorting

An Insertion sort is a sorting algorithm that sorts a set of value or records by inserting records into an existing sorted file. suppose x1, x2, x3,…xn are n-element in memory, insertion sort works as follows:

• pass1: x1 by itself is trivially sorted.
• pass2: x2 is inserted either before or after x1 so that x1, x2 is sorted.
• pass3: x3 is inserted into its proper place in x1, x2 i.e. before x1, between x1, x2, x3 is sorted.
• pass n: xn is inserted into its proper place in x1, x2, x3,….xn-1 so that x1, x2, x3,..xn is sorted.

Algorithm for insertion sorting

Let a be list of n-element which we want to sort, temp be a temporary variable to interchange the two values. i be total number of passes And j be another control value.

• step1: set: i=1
• step2: For i= 1 to n-1 set: temp=ai, set: j= i-1
• step3: while temp< aj and j>0 set: aj+1= aj
• step4: End of while loop set: aj+1=temp, End of the loop.
• step5: stop.

Program perform merge sort using recursion

#include <stdio.h>

void mergeSort(int [], int, int, int);
void partition(int [],int, int);

int main()
{
    int list[50];
    int i, size;

printf("Enter total number of elements:");
scanf("%d", &size);
printf("Enter the elements:\n");
    for(i = 0; i< size; i++)
    {
scanf("%d", &list[i]);
    }
    partition(list, 0, size - 1);
printf("After merge sort:\n");
    for(i = 0;i < size; i++)
    {
printf("%d   ",list[i]);
    }

return 0;
}

void partition(int list[],int low,int high)
{
    int mid;

if(low < high)
    {
        mid = (low + high) / 2;
        partition(list, low, mid);
        partition(list, mid + 1, high);
mergeSort(list, low, mid, high);
    }
}

void mergeSort(int list[],int low,int mid,int high)
{
    int i, mi, k, lo, temp[50];

    lo = low;
i = low;
    mi = mid + 1;
    while ((lo <= mid) && (mi <= high))
    {
        if (list[lo] <= list[mi])
        {
            temp[i] = list[lo];
            lo++;
        }
        else
        {
            temp[i] = list[mi];
            mi++;
        }
i++;
    }
    if (lo > mid)
    {
        for (k = mi; k <= high; k++)
        {
            temp[i] = list[k];
i++;
        }
    }
    else
    {
        for (k = lo; k <= mid; k++)
        {
             temp[i] = list[k];
i++;
        }
    }

    for (k = low; k <= high; k++)
    {
        list[k] = temp[k];
    }
}

OUTPUT

What is searching algorithm?
Ans:Searching Algorithms in data structure: is the process of determining the ability of desired element in the given list of elements stored in any order or randomly. Searching operation….Read more