Insertion sort and its Implementation in ‘C’

Insertion sort is one of the simplest sorting algorithms, it works the way we sort the playing cards. It iterates up the given array, and growing a sorted array behind. At each array-position, it checks the value there against the value in the previous array-position. If larger, it leaves the element in that position and moves to the next. If smaller, it inserts the element into the correct position, shifting the larger values up to make space.

Example illustrating Insertion sort:

Input : 21 9 3 12 6
21 9 3 12 6 
9 21 3 12 6 // sorted subarray = {9,21}
3 9 21 12 6 // sorted subarray = {3,9,21}
3 9 12 21 6 // sorted subarray = {3,9,12,21}
3 6 9 12 21
output : 3 6 9 12 21
Insertion sort animation

Insertion sort animation. courtesy: wikipedia.org

Complexity

Time complexity : O( N --  N² -- N² ) [Best -- Average -- Worst] 
Memory          :  O(1) i.e. just the input array:"in place"
Stable          :  Yes i.e. doesn't change relative order of elements with same key
# N being the number of elements in the array

You can read about complexities of other sorting algorithms here.

Usage

It is much less efficient on larger arrays than the advanced sorting algorithms like quicksort, merge sort and heapsort. Easier to implement, more efficient in practice that the other O(N²) algorithms like selection sort and bubble sort.

Bottom line: Use this over selection or bubble sort.

Implementation in C

Continue reading

Selection Sort and its Implementation in ‘C’

Selection sort is one of the simplest sorting algorithms, at any instance it maintains two subarrays in a given array : one with the elements that are already sorted which is built up from left to right starting at front of the array, other with rest of elements in the array that are remaining to be sorted. The algorithm proceeds by finding the smallest element in the unsorted array and swapping it with the left most element of the unsorted array. Following example clarifies this sentence.

Input : 21 9 3 12 6
21 9 3 12 6 
3 9 21 12 6 // sorted subarray = {3}
3 6 21 12 9 // sorted subarray = {3,6}
3 6 9 12 21 // sorted subarray = {3,6,9}
3 6 9 12 21 // sorted subarray = {3,6,9,12}
output : 3 6 9 12 21

Complexity Analysis

You can read about complexities of other sorting algorithms here.

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

Usage

It is inefficient on larger lists due to its O() time complexity, and generally performs worse than the similar insertion sort. It is easier to implement than most of the other sorting algorithms, can be advantageous over other complicated algorithms, especially when the memory is limited.

Bottom line: Simplest algorithm one can implement when time complexity is not concerned.

Implementation in C

Continue reading

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 )

Continue reading

Bouncing balls in a box – JavaScript

bouncing balls

screen shot

As it is clear from the title, this post is about creating a box with balls bouncing after hitting the walls using JavaScript and HTML5 canvas. More precisely the box is initially empty, balls are added eventually by clicking the surface of box. Apparently i can’t embed JS in the wordpress post, so check this plunk to visualize it. I will go through the code briefly here.

HTML

Create a canvas element with onclick event handler, add some styles to it.

 

JavaScript

Continue reading