Bubble Sort and its Implementation in ‘C’

Bubble Sort is one of the simplest sorting algorithms that works by comparing each pair of adjacent elements and swapping them if they are in wrong order. Unfortunately this is the worst algorithm due to its O(N²) time complexity on average.

You can read about other popular sorting algorithms here.

Static visualization of bubble sort

Static visualization of bubble sort (courtesy : Wikipedia.org )

Time complexity : O(N — N² — ) [Best -- Average -- Worst]
Memory          :  O(1) i.e. just the input array
Stable          :  Yes
# N being the number of elements in the list

Usage:

1. When you want to implement some sorting algorithm very quickly not bothering about anything else. This is not at all practical when N is large.

2. Only advantage it has over most other sorting algorithms, even quicksort, but not insertion sort is to efficiently detect whether the list is already sorted or not. When the list is already sorted the complexity is O(N) (best case).

Bottom line: Use this when you know that the list is almost-sorted (It can fix this just with linear complexity O(2N))

Implementation in C:

Question: Sort an array of integers in increasing order using bubble sort algorithm (format similar to most of the online programming contests )

Input:

First line of the input contains T, number of test cases

Each test case contains an integer N ≤ 200, the number of integers in that array, followed by N integers separated by N spaces.

Output: Sorted array

Sample Input

3
5 4 7 9 3 1
3 4 5 5
4 6 10 6 7

Sample Output

1 3 4 7 9
4 5 5 
6 6 7 10

Code

Brief explanation is given in the gist.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s