Bubble Sort and Selection Sort in C

Sorting is nothing but arranging the data in ascending or descending order. The term sorting came into picture, as humans realized the importance of searching quickly. sorting allows everyone to arrange data in an order, hence making it easier to search.

Bubble Sort Algorithm

Bubble Sort is a simple algorithm which is used to sort a given set of n elements. Bubble Sort compares all the element one by one and sort them based on their values.

Watch the video for the demo https://www.youtube.com/watch?v=yIQuKSwPlro

If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will swap both the elements, and then move on to compare the second and the third element, and so on.
If we have total n elements, then we need to repeat this process for n-1 times. But it is noted that when the array is sorted , comparing adjacent element does not produce any swap and we can stop the process without repeating the next step.

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements "bubble" to the top of the list.

void bubblesort(int arr[], int n)

{

    int i, j, temp;

    for(i = 0; i < n-1; i++) // steps

    {

        for(j = 0; j < n-i-1; j++)

        {

            if( arr[j] > arr[j+1]) //comparing adjacent element

            {

                // swap the adjacent elements if they are out of order

                temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

            }

        }

    }

We can introduce a flag to monitor whether elements are getting swapped inside the inner for loop.
Hence, in the inner for loop, we check whether swapping of elements is taking place or not, every time.
If for a particular iteration, no swapping took place, it means the array has been sorted and we can jump out of the for loop, instead of executing all the iterations.

 

void bubbleSort(int arr[], int n)

{

    int i, j, temp,flag;

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

    {

        for(j = 0; j < n-i-1; j++)

        {

            // introducing a flag to monitor swapping

            flag = 0;

            if( arr[j] > arr[j+1])

            {

                // swap the elements

                temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

                // if swapping happens update flag to 1

                flag = 1;

            }

        }

        // if value of flag is zero after all the iterations of inner loop

        // then break out

        if(flag==0)

        {

            break;

        }

    }

 

Simple Implementation of  bubble sort without using function.

#include <stdio.h>

int main(void)

{

int arr[100],n,i,j,temp;

printf("Enter the number of elements\n");

scanf("%d",&n);

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

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

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

for(i = 0; i < n-1; i++) // steps

   {

    for(j = 0; j < n-i-1; j++)

    {

      if( arr[j] > arr[j+1]) //comparing adjacent element

         {

                // swap the adjacent elements if they are out of order

            temp = arr[j];

            arr[j] = arr[j+1];

            arr[j+1] = temp;

         }

     }

    }

printf("The sorted array is\n");

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

  printf("%d\n",arr[i]);

}

checking whether swapping is done before proceeding to the next iteration

#include <stdio.h>

int main(void)

{

int arr[100],n,i,j,temp,flag;

printf("Enter the number of elements\n");

scanf("%d",&n);

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

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

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

for(i = 0; i < n-1; i++) // steps

   {

      flag=0;

    for(j = 0; j < n-i-1; j++)

    {

      if( arr[j] > arr[j+1]) //comparing adjacent element

         {

                // swap the adjacent elements if they are out of order

            temp = arr[j];

            arr[j] = arr[j+1];

            arr[j+1] = temp;

           flag=1;

         }

     }

        if( flag==0) break;

    }

printf("The sorted array is\n");

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

  printf("%d\n",arr[i]);

}

Example:
let's trace the steps of the bubble sort algorithm for the input array [5, 3, 1, 7, 9]:

Initial array: [5, 3, 1, 7, 9]


Pass 1:Compare adjacent elements and swap if they are in the wrong order.
First pass:

Compare 5 and 3. Since 5 > 3, swap them. Array becomes [3, 5, 1, 7, 9].
Compare 5 and 1. Since 5 > 1, swap them. Array becomes [3, 1, 5, 7, 9].
Compare 5 and 7. No swap needed. Array remains [3, 1, 5, 7, 9].
Compare 7 and 9. No swap needed. Array remains [3, 1, 5, 7, 9].
Note: largest element is at bottom. smallest element is bubbled up.

Pass 2:Repeat the process for the remaining unsorted elements.
Second pass:array is [3, 1, 5, 7, 9].

Compare 3 and 1. Since 3 > 1, swap them. Array becomes [1, 3, 5, 7, 9].
Compare 3 and 5. No swap needed. Array remains [1, 3, 5, 7, 9].
Compare 5 and 7. No swap needed. Array remains [1, 3, 5, 7, 9].

Pass 3:

Third pass:array is [1, 3, 5, 7, 9].

Compare 1 and 3. No swap needed. Array remains [1, 3, 5, 7, 9].
Compare 3 and 5. No swap needed. Array remains [1, 3, 5, 7, 9].

No exchange in this pass so we can stop.

Result:The array is sorted in ascending order: [1, 3, 5, 7, 9].

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The sub array which is already sorted.
2) Remaining sub array which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted sub array is picked and moved to the sorted sub array.

 

void selectionsort(int arr[], int n)

{

    int i, j, minidx,temp;

     // One by one move boundary of unsorted subarray

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

    {

        // Find the minimum element in unsorted array

        minidx = i;

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

          if (arr[j] < arr[minidx])

            minidx = j;

         // Swap the found minimum element with the first element

      if(minidx!=i)

       {

          temp=arr[minidx];

          arr[minidx]=arr[i];

          arr[i]=temp;

               }

    }

}

Simple Implementation with out using function

#include <stdio.h>

int main(void)

{

int arr[100],n,i,j,temp,minidx;

printf("Enter the number of elements\n");

scanf("%d",&n);

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

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

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

     // One by one move boundary of unsorted subarray

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

    {

        // Find the minimum element in unsorted array

        minidx = i;

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

          if (arr[j] < arr[minidx])

            minidx = j;

         // Swap the found minimum element with the first element

      if(minidx!=i)

       {

          temp=arr[minidx];

          arr[minidx]=arr[i];

          arr[i]=temp;

               }

    }

printf("The sorted array is\n");

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

  printf("%d\n",arr[i]);

}

Write an easy to read C program to sort a set of n integers and to find the number of unique numbers and the number of repeated numbers in the given set of numbers. Use a function which takes an integer array of n elements, sorts the array using the Bubble Sorting Technique and returns the number of unique numbers and the number of repeated numbers in the given array.

 

#include <stdio.h>
void bubblesort(int arr[100],int n)
{int i,j,temp,flag,count=1,dup=0,uniq=0;
for(i = 0; i < n-1; i++)
   {
      flag=0;
    for(j = 0; j < n-i-1; j++)
    {
      if( arr[j] > arr[j+1])
         {
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
           flag=1;
         }
     }
        if( flag==0) break;
    }

  // finding count of elements

for(i=0;i<n;i=i+count)
 {
   count=1;
  for(j=i+1;j<n;j++)
     {if(arr[i]==arr[j]) count++;}
  if(count>1)
       dup++;
  else
        uniq++;
}
printf("Number of unique elements=%d duplicate elements=%d\n",uniq,dup);
}
int main(void)
{
int arr[100],n,i,j,temp,flag;
printf("Enter the number of elements\n");
scanf("%d",&n);
printf("Enter the array elements\n");
for(i=0;i<n;i++)
  scanf("%d",&arr[i]);
bubblesort(arr,n);
printf("The sorted array is\n");
for(i=0;i<n;i++)
  printf("%d\n",arr[i]);
}