I have three implemented sorting algorithm:-

  1. Bubble Sort
  2. Merge Sort
  3. Quick Sort

How do I select the averagely fastest sorting algorithm based on the characteristics of the given sequence and return the sorted one.

asked 20 Jan '15, 16:35

codebazz's gravatar image

codebazz
123117


Considering the average case time complexities of the mentioned algorithms, bubble sort is the worst, O(n^2), and both quicksort and merge sort are O(n lg n). When sorting data of small sizes you may not notice any difference among these three, but for large arrays bubble sort is no good. So you can scratch it off the list.

Now, while both quicksort and merge sort have the same time complexity, their performance may be different depending on the data. Doing a a merge sort on different data of the same size would require exactly the same number of operations every time. But the number of operations can vary in quicksort. If the data is already sorted, the traditional quicksort would require O(n^2) operations. There is a variation of quicksort, which is called 'randomized quicksort', performs better in such cases. But for sorted data, bubble sort becomes O(n) (because there would be nothing to do).

So, in average case, both quicksort and merge sort have the same time complexity, but in worst case, quicksort and bubble sort can have the same complexity.

Algorithm        Best case     Average case      Worst case
Bubble sort      O(n^2)        O(n^2)             O(n^2)
Quicksort        O(n lg n)     O(n lg n)          O(n^2)
Merge sort       O(n lg n)     O(n lg n)          O(n lg n)

For a quick look on complexities of algorithms, you can see this.

permanent link

answered 21 Jan '15, 05:20

0605002's gravatar image

0605002
4907

edited 21 Jan '15, 05:21

but vaiya, I think you have missed another thing that is if the array is reversely sorted Quick sort may be not perform best and obviously bubble will be the worst for reversely sorted array. Then I think I should select the merge sort for reversely sorted large array. @Sufian Latif vaiya.

(21 Jan '15, 05:52) codebazz

You can choose the fastest one by knowing their time complexity (How many time it need to sort n numbers in worst case).The lowest time complexity in worst case is the fastest one.

The fastest algorithm among 3 is Merge sort (Time complexity: n*log(n)). Here you can find all the information about sorting algorithms-Link.

permanent link

answered 20 Jan '15, 17:15

Kaiser%20Ahmed's gravatar image

Kaiser Ahmed
3.2k522

As far as I know, If the input array list is almost sorted insertion sort performs best.

permanent link

answered 21 Jan '15, 02:39

Shadek's gravatar image

Shadek
111

but I have only three options: - bubble, merge, quick sort

(21 Jan '15, 03:54) codebazz
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×36
×13
×2
×2
×1

question asked: 20 Jan '15, 16:35

question was seen: 1,349 times

last updated: 21 Jan '15, 05:52