7

I am risking this question being closed before i get an answer, but i really do want to know the answer. So here goes.

I am currently trying to learn algorithms, and I am beginning to understand it as such but cannot relate to it.

I understand Time Complexity and Space Complexity. I also do understand some sorting algorithms based on the pseudo code

Sorting algorithms like

  1. Bubble Sort
  2. Insertion Sort
  3. Selection Sort
  4. Quicksort
  5. Mergesort
  6. Heapsort (Some what)

I am also aware of Best Case and Worst Case scenarios(Average case not so much).

Some online relevant references

  • Nice place which shows all the above graphically.
  • This gave me a good understanding as well.

BUT my question is - can some one give me REAL WORLD EXAMPLES where these sorting algorithms are implemented.

Community
  • 1
  • 1
Amey
  • 8,470
  • 9
  • 44
  • 63
  • 2
    http://stackoverflow.com/questions/1933759/when-is-each-sorting-algorithm-used – Brandon Kreisel Jun 13 '12 at 20:25
  • thanks for your reply, but can you please also provide, real examples like, video streaming data sort, search addresses of people with first name starting with K in an phone dirctory record of over 5 million people. – Amey Jun 13 '12 at 20:33

2 Answers2

8

As the number of elements increases, you will use more sophisticated sorting algorithms. The later sorting techniques have a higher initial overhead, so you need a lot of elements to sort to justify that cost. If you only have 10 elements, a bubble or insertion sort will be the much faster than a merge sort, or heapsort.

Space complexity is important to consider for smaller embedded devices like a TV remote, or a cell phone. You don't have enough space to do something like a heapsort on those devices.

Datebases use an external merge sort to sort sets of data that are too large to be loaded entirely into memory. The driving factor in this sort is the reduction in the number of disk I/Os.

Good bubble sort discussion, there are many other factors to consider that contribute to a time and space complexity.

Sorting-Algorithms.com

Community
  • 1
  • 1
JustinDanielson
  • 3,155
  • 1
  • 19
  • 26
  • thank you for your reply, so at no point will one ever have to use bubble sort or insertion sort in a real world scenario? – Amey Jun 13 '12 at 20:35
  • 1
    If you know that you do not have very many items to sort, it is better to use bubble sort or insertion sort. I programmed a TV remote that used a MIPS processor and I used bubble sort to sort the channels on the longest viewing time. There were only 100 channels. Also, if you know the elements are in near-sorted order, a bubble sort is good because it will finish in a far better speed than average case of n/2 passes. – JustinDanielson Jun 13 '12 at 20:39
  • Thanks Justin, do you want to edit it (the bubble sort part) into your result. I am marking this as the answer. – Amey Jun 13 '12 at 21:15
0

One example is C++ STL sort

as the wikipedia page says:

The GNU Standard C++ library, for example, uses a hybrid sorting algorithm: introsort is performed first, to a maximum depth given by 2×log2 n, where n is the number of elements, followed by an insertion sort on the result.1 Whatever the implementation, the complexity should be O(n log n) comparisons on the average.[2]

xvatar
  • 3,229
  • 17
  • 20