Sorting Alogrithms

This is a collection of the most popular sorting algorithms. I will frequently update this page with links for the description and their implementation in C.

Sorting Algorithm

It is an algorithm which arranges items in the list in certain order. These algorithms are important for optimizing the implementation of other algorithms (like search and merge algorithms) which requires input data to be in sorted lists.

We define the sorting problem like this..

Input   : Sequence of N numbers ( i1, i2, i3, i4, …., iN)

Output: Sequence of numbers  ( j1, j2, j3, j4, …., jN) with the condition that ( j1 ≤ j2 ≤ j3 ≤ j4 …..≤ jN)

Classifications

Sorting algorithms are often classified based on the difficulties that can happen in real life while implementing them. Problems that are considered frequently..

Computational complexity

Worst, Average and Best case performance of the algorithm (usually run time) in terms of the size of list (N). For typical sorting algorithm best performance is O(N log N) and worst performance O(N²).

Memory Usage (and use of other computer resources)

Some sorting algorithms are ‘in place‘ (algorithms which overwrites its input with its output as it executes). Strictly, in place sort requires only O(1) memory. Some algorithms require O(N), O(log N) memory.

Stability

Another problem is the stability of the algorithm. A sorting algorithm is said to be stable if  two objects with same element ( key ) appears in the same order in sorted output as they appear in the unsorted input array. Example clarifies the sentence..

Question : Sort words by first letter

Input : Bag  Apple  Ball

Output : Apple Bag Ball  (stable)

Output : Apple Ball Bag  (not stable)

Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.

Further, sorting algorithms are classified based on whether or not they are comparison sort. A comparison sort examines the data only by comparing two elements with a comparison operator.

Comparison-based Sorting Algorithms

As said, comparison-based sorting algorithms find the relationship (less than or greater than or equal) between two objects by comparing them with each other. Main concern of these algorithms is to decrease the number of comparisons (lesser the comparisons, more effective is the algorithm). Let’s start with the naive ones and move on to the most sophisticated algorithms.

No. Algorithm      : O(Best — Average — Worst)  —  O(Worst case memory)

1.   Bubble sort     : O(N — N² — )   —  O(1)

2.   Selection sort  : O( — N² — )   —  O(1)

3.   Insertion sort   : O(N — N² — )   —  O(1)

4.   Merge sort      : O(N log N — N log N — N log N)   —  O(N)

5.   Heapsort         : O(N log N — N log N — N log N)   —  O(1)

6.   Quicksort        : O(N log N — N log N — )   —  O(log N or N)

7.   Timsort           : O(N  — N log N — N log N)   —  O(N)

Usage in practice

Most would say each algorithm has its trade-offs. Typically, default sort implementation for most of the languages is either Mergesort or Quicksort. As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. Python uses Timsort, another tuned hybrid of merge sort and insertion sort, that has become the standard sort algorithm in Java SE 7, on the Android platform, and in GNU Octave.

Resources

http://en.wikipedia.org/wiki/Sorting_algorithm

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