SORTING IN C PROGRAMING

by
  1. Explain in detail about sorting and different types of sorting techniques
    Sorting is a technique to rearrange the elements of a list in ascending or descending order, which can be numerical, lexicographical, or any user-defined order. Sorting is a process through which the data is arranged in ascending or descending order. Sorting can be classified in two types;
    Internal Sorts:- This method uses only the primary memory during sorting process. All data items are held in main memory and no secondary memory is required this sorting process. If all the data that is to be sorted can be accommodated at a time in memory is called internal sorting.
    There is a limitation for internal sorts; they can only process relatively small lists due to memory constraints. There are 3 types of internal sorts.
    (i) Selection sort
    (ii) Insertion sort
    (iii) Bubble Sort
    External Sorts:- Sorting large amount of data requires external or secondary memory. This process uses external memory such as HDD, to store the data which is not fit into the main memory. So, primary memory holds the currently being sorted data only. All external sorts are based on process of merging. Different parts of data are sorted separately and merged together.
    Ex:- Merge Sort
  2. Explain the algorithm for bubble sort and give a suitable example. (OR) Explain the algorithm for exchange sort with a suitable example.
    In bubble sort method the list is divided into two sub-lists sorted and unsorted. The smallest element is bubbled from unsorted sub-list. After moving the smallest element the imaginary wall moves one element ahead. The bubble sort was originally written to bubble up the highest element in the list. But there is no difference whether highest / lowest element is bubbled. This method is easy to understand but time consuming. In this type, two successive elements are compared and swapping is done. Thus, step-by-step entire array elements are checked. Given a list of ‘n’ elements the bubble sort requires up to n-1 passes to sort the data.

Algorithm for Bubble Sort: Bubble_Sort ( A [ ] , N )
Step 1 : Repeat For P = 1 to N – 1 Begin
Step 2 : Repeat For J = 1 to N – P Begin
Step 3 : If ( A [ J ] < A [ J – 1 ] )

Swap ( A [ J ] , A [ J – 1 ] ) End For
End For

Step 4 : Exit
Example:
Ex:- A list of unsorted elements are: 10 47 12 54 19 23

  1. Show the bubble sort results for each pass for the following initial array of elements.
    35 18 7 12 5 23 16 3 1
  1. Explain the algorithm for selection sort and give a suitable example.
    In selection sort the list is divided into two sub-lists sorted and unsorted. These two lists are divided by imaginary wall. We find a smallest element from unsorted sub-list and swap it to the beginning. And the wall moves one element ahead, as the sorted list is increases and unsorted list is decreases.
    Assume that we have a list on n elements. By applying selection sort, the first element is compared with all remaining (n-1) elements. The smallest element is placed at the first location.
    Again, the second element is compared with remaining (n-1) elements. At the time of comparison, the smaller element is swapped with larger element. Similarly, entire array is checked for smallest
    element and then swapping is done accordingly. Here we need n-1 passes or iterations to completely rearrange the data.
    Algorithm: Selection_Sort ( A [ ] , N )
    Step 1 : Repeat For K = 0 to N – 2 Begin
    Step 2 : Set POS = K
    Step 3 : Repeat for J = K + 1 to N – 1 Begin

If A[ J ] < A [ POS ]
Set POS = J
End For
Step 5 : Swap A [ K ] with A [ POS ]

End For
Step 6 : Exit

  1. Demonstrate the selection sort results for each pass for the following initial array of elements
    . 21 6 3 57 13 9 14 18 2

Write a program to sort elements of an array using selection sort

#include <stdio.h>
#include <conio.h>
void main()
{
int i,j,t,n,min,a[10];
clrscr( );
printf("\n How many elements you want to sort? ");
scanf("%d",&n);
printf("\Enter elements for an array:");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
min=i;
for(j=i+1; j<n; j++)
if(a[j] > a[min])
{
min=j;
}
t=a[i];
a[i]=a[min];
a[min]=t;
}
printf("\nAfter sorting the elements are:");
for(i=0; i<n; i++)
printf("%d ",a[i]);
getch( );
}

Output

How many elements you want to sort? :5
Enter elements for an array : 2 6 4 8 5
After Sorting the elements are : 8 6 5 4 2
  1. Explain the algorithm for insertion sort and give a suitable example.
    Both the selection and bubble sorts exchange elements. But insertion sort does not exchange elements. In insertion sort the element is inserted at an appropriate place similar to card insertion. Here the list is divided into two parts sorted and unsorted sub-lists. In each pass, the first element of unsorted sub list is picked up and moved into the sorted sub list by inserting it in suitable position. Suppose we have ‘n’ elements, we need n-1 passes to sort the elements.
    Insertion sort works this way:

It works the way you might sort a hand of playing cards:

  1. We start with an empty left hand [sorted array] and the cards face down on the table [unsorted
    array].
  2. Then remove one card [key] at a time from the table [unsorted array], and insert it into the
    correct position in the left hand [sorted array].
  3. To find the correct position for the card, we compare it with each of the cards already in the
    hand, from right to left.

INSERTION_SORT (A)

  1. FOR j ← 2 TO length[A]
  2. DO key ← A[j]
  3. {Put A[j] into the sorted sequence A[1 . . j − 1]}
  4. i ← j − 1
  5. WHILE i > 0 and A[i] > key
  6. DO A[i +1] ← A[i]
  7. i ← i − 1
  8. A[i + 1] ← key

Ex:- A list of unsorted elements are: 78 23 45 8 32 36 . The results of insertion sort for each pass is as follows:-

  1. Demonstrate the insertion sort results for each insertion for the following initial arrayof elements
    . 25 6 15 12 8 34 9 18 2

Write a program to sort elements of an array using insertion sort

#include <stdio.h>
#include <conio.h>
void main()
{
int a[10],i,j,k,n;
clrscr( );
printf("\n How many elements you want to sort? ");
scanf("%d",&n);
printf("\Enter the Elements into an array :");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
for(i=1; i<n; i++)
{
k=a[i];
for(j= i-1; j>=0 && k<a[j]; j--)
a[j+1]=a[j];
a[j+1]=k;
}
printf("\n\n Elements after sorting: \n");
for(i=0;i<n;i++)
printf("%d\n", a[i]);
getch( );
}

Output

How many elements you want to sort ? : 6
Enter elements for an array : 78 23 45 8 32 36
After Sorting the elements are : 8 23 32 36 45 78

Leave a Comment