Types of Sort

Another comparison of sorting algorithms using random, ordered and reverse ordered samples.

Quick Sort.

Find pivot from the list, arrange the elements in a such way that values less than the pivot are moved to the left and values greater than the pivot are moved to right. Apply the above logic recursively until all elements are sorted.

Merge Sort.

Divided the elements into sub lists containing a single element then repeatedly merge all the sub lists into one single sorted list.

Radix Sort.

Elements are arranged based on least-significant digit first, followed by the second-least significant digit and so forth and finally the most significant digits. This results in a single sorted list.

Heap Sort.

Construct a binary tree then remove the highest value from the tree and insert it at the end and repeat for all items to get a single sorted list.

Comparison of time taken by different sorting algorithm:

Note: Using code and algorithms found in the referenced website, the following values were generated using on an Intel Core Quad CPU Q6600 @ 2.40 Ghz with 3GB of RAM.

Randomized
Sort Algorithm
1-1000
1-5000
1-50000
1-100000
1-500000
1-1000000
Radix
0.000000
0.001000
0.023000
0.051000
Stack overflow Exception
Stack overflow Exception
Quick
0.005000
Stack overflow Exception
Stack overflow Exception
Stack overflow Exception
Stack overflow Exception
Stack overflow Exception
Heap
0.000000
0.002000
0.029000
0.064000
0.236000
0.510000
Merge
0.001000
0.009000
1.137000
4.205000
Stack overflow Exception
Stack overflow Exception
Insert
0.002000
0.035000
3.479000
14.046000
346.167000

Shell
0.005000
0.081000
8.781000
33.505000
881.254000

Bubble
0.009000
0.166000
16.912000
67.835000
1706.477000

Selection
0.004000
0.053000
5.291000
21.261000
529.334000


Ordered
Sort Algorithm
1-1000
1-5000
1-50000
1-100000
1-500000
1-1000000
Radix
0.000000
0.001000
0.016000
0.034000
Stack overflow Exception
Stack overflow Exception
Quick
0.003000
Stack overflow Exception
Stack overflow Exception
Stack overflow Exception
Stack overflow Exception
Stack overflow Exception
Heap
0.000000
0.002000
0.019000
0.039000
0.217000
0.4550000
Merge
0.001000
0.010000
1.109000
4.130000
Stack overflow Exception
Stack overflow Exception
Insert
0.000000
0.000000
0.000000
0.001000
0.004000

Shell
0.000000
0.000000
0.003000
0.008000
0.041000

Bubble
0.000000
0.000000
0.000000
0.000000
0.002000

Selection
0.004000
0.053000
5.292000
21.139000
529.687000


Reverse Ordered
Sort Algorithm
1-1000
1-5000
1-50000
1-100000
1-500000
1-1000000
Radix
0.000000
0.001000
0.016000
0.038000
Stack overflow Exception
Stack overflow Exception
Quick
0.004000
Stack overflow Exception
Stack overflow Exception
Stack overflow Exception
Stack overflow Exception
Stack overflow Exception
Heap
0.000000
0.002000
0.017000
0.037000
0.211000
0.4330000
Merge
0.001000
0.002000
1.115000
4.159000
Stack overflow Exception
Stack overflow Exception
Insert
0.005000
0.069000
7.041000
27.954000
685.792000

Shell
0.000000
0.001000
0.006000
0.013000
0.074000

Bubble
0.001000
0.168000
16.860000
67.351000
1713.482000

Selection
0.005000
0.055000
5.608000
22.252000
557.209000


References
Allain, A. (n.d.). Sorting Algorithm Comparison. Retrieved from C Programming.com:http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html
Cormen, T. H., Leiserson, E. C., Rivest, L. R., & Stein, C. (2009). Introduction to Algorithms 3rd Edition. The MIT Press.
Insertion Sort. (n.d.). Retrieved from http://en.wikipedia.org/wiki/Insertion_sort
Quick Sort. (n.d.). Retrieved from  http://en.wikipedia.org/wiki/Quicksort
Pattis, R. E. (n.d.). Analysis of Algorithms. Retrieved from http://www.cs.cmu.edu/~pattis/15-1XX/15-200/lectures/aa/
Stoimen. (n.d). Computer Algorithms. Retrieved from Stoimen’s Web Log: http://www.stoimen.com/blog/2012/03/13/computer-algorithms-quicksort/

Sorting algorithms.  (n.d.). Retrieved from http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort

Comments

Post a Comment

Popular posts from this blog

Create SAS Data Sets w/o SAS

Image
Scope:  Create output in SAS7BDAT (closed binary format for passionate SAS practitioners and experts without installing Base SAS product from SAS Programming Institute. Carolina S-JDBC Driver: Dulles Research – A Virginia based private company offer “Carolina S-JDBC” JDBC driver that replace the need for Base SAS license. License constraints: (Carolina S-JDBC Driver Download, 2016) Annual subscription is $995.00 for a single instance of application server. Quote can be requested from enterprise wide installation. Free for non-commercial use. http://www.dullesresearch.com/sjdbc-download/ Solution:   class. forName ( "com.dullesopen.jdbc.Driver" ).newInstance();               Connection connection = DriverManager. getConnection (                       "jdbc:carolina:v2:libnames= ...
Read more

ACID vs BASE

In 1970, Jim Gray defined ACID properties as a reliable means of implementing a transaction system. Atomic – A transaction should be indivisible and it must be all or nothing even when the database goes down due to system failures. Consistency – A transaction should ensure that the data remains valid at all times even in case of application errors and none of the defined rules and constraints on the data must be compromised. Isolation – A transaction must be isolated from other transactions and intermediate results of a transaction must not be seen by other transactions that are concurrently in execution. Durability - A transaction must preserve the state of completed transaction at all times even in the event of system failures. Even though ACID stood the test of time for centralized database system, and we see wide implementation of two-phase commit for distributed databases, scaling databases that are distributed and keeping them highly available has always b...
Read more

Immutable: String

The following are the some of the programmer friendly advantages of high level languages like Java, C# or Visual Basic by handling String as immutable as opposed to being mutable in languages like “C” A) Efficient use of memory: High level language make efficient use of memory by incorporating a special type of memory structure called "String Pool", each time any code creates a string literal, the Java Virtual Machine (Java) or Common language runtime checks to see if the String is already defined in the "StringPool" and if it exists, a reference is assigned as opposed to allocating space for every string. For example: If "ABCDEFGHIJKLMNOPQRSTUVWXYZ" is assigned10 times within a code, then in the StringPool, there will be a single copy of “ABCDEFGHIJKLMNOPQRSTUVWXYZ" and 10 references to it. This is a gain in the memory space allocation even though there is additional over head of maintaining “StringPool” memory structure. In ord...
Read more