Skip to main content

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 realised 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 provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sort them based on their values.
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; 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; 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)
        {
            break;
        }
    }
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;
               }
    }
}


Comments

  1. very nice..post.
    https://shayarihindishayari.com/

    ReplyDelete

Post a Comment

Popular posts from this blog

Files in C

A file is a repository of data that is stored in a permanent storage media, mainly in secondary memory. In order to use the files we should learn how to read information from a file and how to write information into a file. A very important concept in C is the stream.The stream is a common logical interface to the various devices( files).A stream is linked to a file while using an open operation. A stream is disassociated from a file while using a close operation. The current location, also referred to as the current position, is the location in a file where the next fie access will occur.There are two types of streams text and binary. The following are some difference between text and binary files ·Text file is human readable because everything is stored in terms of text. In binary file everything is written in terms of 0 and 1, therefore binary file is not human readable. ·A newline(\n) character is converted into the carriage return-linefeed combination before being written to the d…

KTU C programming question paper and evaluation scheme

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY SECOND SEMESTER B.TECH DEGREE EXAMINATION, MAY 2017 CS 100 COMPUTER PROGRAMMING (CS, IT) SCHEME OF EVALUATION
PART A 1 An identifier is a sequence of characters invented by the programmer or to identify or name a specific object. The sequence of characters may be letters, digits, and special character ‘_’known as an underscore Rules: i)Identifiers should start with alphabets. ii)Identifiers are case sensitive iii)A numeric digit should not be the first character iv)Identifier name should not be a keyword v)Identifier may be of any reasonable length 1mark






2mark 2 Associativity defines the direction, left to right or right to left in which operator act upon its operands Unary operators have associativity is from right to left. For examplein the expression &--x, pre decrement works first and then address of operator works Direction + example<

Strings in C

Strings in C Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’. Declaration of strings: Declaring a string is as simple as declaring a one dimensional array. Below is the basic syntax for declaring a string. charstr_name[size]; In the above syntax str_name is any name given to the string variable and size is used define the length of the string, i.e the number of characters strings will store. Please keep in mind that there is an extra terminating character which is the Null character (‘\0’) used to indicate termination of string which differs strings from normal character arrays. Initializing a String: A string can be initialized in different ways. We will explain this with the help of an example. Below is an example to declare a string with name as str and initialize it with “cek”. 1. charstr[] = "cek"; 2. charstr[50] = "cek"; 3. charstr[] = {'c','…