Bubble sort in C

Sorting - Sorting refers to different techniques or methods of arranging or ordering things based on a criteria.
For example - We have list of student names and their age. Sorting techniques can be applied to sort this list based on student's names in decreasing order or in increasing order of their age or vice versa.

Sorting algorithms are the fundamental algorithm problems in computer science. The sorting algorithms are also embedded into other algorithms like search and merge algorithms.

Some of the sorting algorithms are bubble sort, selection sort, insertion sort, heap sort, quick sort, merge sort etc.

Bubble Sort (also known as sinking sort) - This sorting technique probably is the oldest and easiest of all the sorting algorithms. And hence it is also the most inefficient one. It is seldom used in practical applications. Some researchers even have gone to say that this algorithm should not even be taught.

Basic Principle - In this algorithm each element in the list is compared with the next element in the list and swapping the position of two if required. With each iteration (Pass) the largest element in the list is "bubbled" to the end of the list.

C Code (Bubble Sort) -

void BubbleSort (int a[], int a_size)
{
   int i,j,temp;
   for (i < 0; j < a_size - 1; ++i)
   {
      for (j=0; j < a_size - 1 - i; ++j)
      {
         if(a[j] > a[j+1])
           {
             temp = a[j+1];
      a[j+1] = a[j];
             a[j] = temp;
     }
       }
    }
}

Bubble Sort at work -

Suppose we have following list of elements which we need to sort in increasing order.(Will give the values of diffrent variables wherever possible as per above code snippet.)
List - 5 3 7 1 4 9      // a[] = {5,3,7,1,4,9}, a_size = 6

Pass 1 (i=0)

1) 5 3 7 1 4 9 -> 3 5 7 1 4 9   // 5 > 3 hence swapped, i = 0, j = 0, a[j] = 5,  a[j+1] = 3, temp = 3
2) 3 5 7 1 4 9 -> 3 5 7 1 4 9   // 7 > 5 nothing happened, i = 0, j = 1, a[j] = 5, a[j+1] = 7
3) 3 5 7 1 4 9 -> 3 5 1 7 4 9   // 7 > 1 hence swapped,i = 0, j = 2, a[j] = 7, a[j+1] = 1, temp = 1
4) 3 5 1 7 4 9 -> 3 5 1 4 7 9   // 7 > 4 hence swapped, i = 0, j = 3, a[j] = 4, a[j+1] = 1, temp = 4
5) 3 5 1 4 7 9 -> 3 5 1 4 7 9   // 9 > 7 nothing happened, i = 0, j = 4, a[j] = 7, a[j+1] = 9. End of Pass 1. Biggest element 9 is bubbled to the last.

Pass 2 (i=1)

1) 3 5 1 4 7 9 -> 3 5 1 4 7 9   // 5 > 3 nothing happened, i = 1, j = 0, a[j] = 3, a[j+1] = 5
2) 3 5 1 4 7 9 -> 3 1 5 4 7 9   // 5 > 1 hence swapped,i = 1, j = 1, a[j] = 5,  a[j+1] = 1, temp = 1
3) 3 1 5 4 7 9 -> 3 1 4 5 7 9   // 5 > 4 hence swapped,i = 1, j = 2, a[j] = 5,  a[j+1] = 4, temp = 4
4) 3 1 4 5 7 9 -> 3 1 4 5 7 9   // 7 > 5 nothing happened,i = 1, j = 3, a[j] = 5,  a[j+1] = 7, temp = 7.End of pass 2. Second biggest element 7 is bubbled to second last postion.

Pass 3 (i=2)

1) 3 1 4 5 7 9 -> 1 3 4 5 7 9   // 3 > 1 hence swapped, i = 2, j = 0, a[j] = 3, a[j+1] = 1,temp = 1
2) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 4 > 3 nothing happened,i = 2, j = 1, a[j] = 3, a[j+1] = 4
3) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 5 > 4 nothing happened,i = 2, j = 2, a[j] = 4, a[j+1] = 5,End of pass 3. Third biggest element 5 is bubbled to third last position.


Pass 4(i=3)

1) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 3 > 1 nothing happened,i = 3, j = 0, a[j] = 1, a[j+1] = 3
2) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 4 > 3 nothing happened,i = 3, j = 1, a[j] = 3, a[j+1] = 4,End of pass 4. Fourth biggest element 4 is bubbled to third position.

Pass 5(i=4)

1) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 3 > 1 nothing happened,i = 4, j = 0, a[j] = 1, a[j+1] = 3,End of pass 5. Fivth biggest element 3 is bubbled to second position.

Issues in Bubble Sort -

As you can see in the example above we need a_size - 1 - i comparison's in every pass (i). So the number of comparisons performed by the bubble sort algorithm can be summed as (n-1)+(n-2)+…….+2+1= n(n-1)/2 = O(n2), here n = number of elements to sort. In the example above this value comes out to be 5+4+3+2+1 = 15. In any case i.e. worst case or the best case number of comparisons remain same i.e. O(n2).

worst case = elements are in decreasing order
best case = elements are in increasing order

Difference in worst and best case is the number of swapes which happen. In worst case we have 0(n2) number of swaps while in best case we do not have any swap of elements in the list.

Note - Efficiency of bubble sort can be improved. One way to do this is to check if the list of elements is already sorted during the execution of algorithm. This can be checked by inserting a flag which will check if if during a pass did any swap of elements happened or not. If not that means list is already sorted, and further execution of paases is not required.

C Code (Improved Bubble Sort) -

void BubbleSort (int a[], int a_size)
{
   int i,j,temp;
   bool sorted = false;
   for (i < 0; (j < a_size - 1) && (!sorted) ; ++i)
   {
    sorted = true;
      for (j=0; j < a_size - 1 - i; ++j)
      {
         if(a[j] > a[j+1])
           {
             temp = a[j+1];
             a[j+1] = a[j];
             a[j] = temp;
      sorted = false;
     }
       }
    }
}












 

malloc () function in C

malloc is short form of memory allocation. This function is used to allocate block of memory on heap memory. Function definition resides in stdlib.h header file.

void * malloc(size_in_bytes)

malloc function returns a void pointer which contains the address of the first byte in the allocated block of memory. Size_in_bytes is the size of block we want malloc function to allocate when it is called in the program. If we have specified the Size_in_bytes more than what is available in the heap memory then this function will return a NULL.
We need to type cast the void pointer into the data type which we need to allocate memory for.

Hence we will use this function as below in our program.

type *ptr = (type *)malloc(size_in_bytes)

Note - If we allocate memory using this function, the allocated memory block will contain garbage value. We need to initialize the pointer before using it so that we do not use the garbage value contained in. Malloc function will not initialize the memory block allocated on heap memory.

C Code Example

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

/* stdlib.h contains the definition for malloc() function. */

int main()
int *ptr;    // ptr is declared as a pointer to an integer

ptr = (int*)malloc(sizeof(int));  

/* malloc function is called with an argument which is another function sizeof().sizeof() returns the number of bytes of memory the specified data type will take. In this case sizeof(int) will return 4 which means 4 bytes which is required on my machine to store a integer variable. ptr will now have the address of first byte of the 4 bytes malloc allocated. */

if(ptr=NULL)
{
puts("malloc call failed");
}
else
{
*ptr = 7;
}
printf("Integer we stored at address ptr is = %d",*ptr);
free(ptr);

/* free() function will free the memory allocated by malloc. If we do not free the memory this block of memory will not be available for the program and may cause memory leak issue. */

getch()

}

Output of above program will be :

Integer we stored at address ptr is = 7


















 

Stack Vs Heap Memory in C

Memory is one of the various resources on computer system and this needs to be managed efficiently for smooth
executions of both user and system programs.
Memory mainly consists of two portions. Stack and Heap.
Stack frame is implemented using stack data structure and is used for storing local variables and function calls.
This memory portion is static and do not grow while the program is running.
When program execution starts OS assigns fix amount of space for stack. If local variables and function calls grow
more than this specified amount we tend to see stack overflow errors and program will crash.
One common case when this can happen is in case of bad regression.
Stack is a LIFO data structure. That means the element which is written last is read or manipulated first. In other
words the data which is pushed recently is read first and the function which is pushed recently is manipulated first.
Allocation and DE allocation in stack happens through two operations push and pop.
PUSH - Add item to stack (Top)
POP - Remove item from stack (Top)
If we need to declare a large data type like array as local variable we need to know the size of the array at
compile time.
Heap on the other hand does not have anything to do with heap data structure as we study in data structures. Heap is
also called dynamic memory. Using heap is also known as dynamic memory allocation.
Its size can vary during run time of program as far as we don't run out of memory of the system. Heap is
implemented in different ways depending on operating systems.
How to use Heap in C:
1) malloc
2) calloc
3) realloc
4) free