12

I was reading sorting method which include bubble sort, selection sort, merge sort, heap sort, bucket sort etc.. They also contain time complexity which help us to know which sorting is efficient. So I had a basic question. If we contain data than how will we be choose sorting. Time complexity is one of parameter which help us to decide sorting method. But do we have another parameter to choose sorting method?.

Just trying to figure out sorting for better understanding.

Having some query about heap sort:

  1. Where do we use heap sort?

  2. What is bigger advantage of heap sort (except time complexity O(n log n))?

  3. What is disadvantage of heap sort?

  4. What is build time for heap? (I heard O(n) but I'm not sure.)

  5. Any scenario where we have to use heap sort or heap sort is better option (except priority queue)?

  6. Before applying the heap sort on data, what are the parameter will we look into data?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • 1
    What do you mean by "if we contain data"? Are you asking how to choose a sort method for a specific data set? – Cameron Mar 21 '12 at 03:10
  • 1
    You haven't accepted any of the the answers to your previous questions. That's going to put a lot of people off from helping you. – chrisaycock Mar 21 '12 at 03:12
  • 1
    Is your question better expressed as *What is the criteria to choose a sorting algorithm?* If so please edit the Q title. – Alok Save Mar 21 '12 at 03:13
  • Your updated question looks a lot like homework, so I gave you a link that might help in my answer. If it is homework, can you add the `homework` tag please? If not, you might want to narrow your question a bit. – Timothy Jones Mar 21 '12 at 03:38
  • 1
    Good Read: [Criteria for choosing a sorting algorithm](http://my.safaribooksonline.com/book/software-engineering-and-development/algorithms/9780596516246/sorting-algorithms/criteria_for_choosing_a_sorting_algorit#X2ludGVybmFsX0ZsYXNoUmVhZGVyP3htbGlkPTk3ODA1OTY1MTYyNDYvOTk=) – Alok Save Mar 21 '12 at 03:51

2 Answers2

17

The two main theoretical features of sorting algorithms are time complexity and space complexity.

In general, time complexity lets us know how the performance of the algorithm changes as the size of the data set increases. Things to consider:

  • How much data are you expecting to sort? This will help you know whether you need to look for an algorithm with a very low time complexity.
  • How sorted will your data be already? Will it be partly sorted? Randomly sorted? This can affect the time complexity of the sorting algorithm. Most algorithms will have worst and best cases - you want to make sure you're not using an algorithm on a worst-case data set.
  • Time complexity is not the same as running time. Remember that time complexity only describes how the performance of an algorithm varies as the size of the data set increases. An algorithm that always does one pass over all the input would be O(n) - it's performance is linearly correlated with the size of the input. But, an algorithm that always does two passes over the data set is also O(n) - the correlation is still linear, even if the constant (and actual running time) is different.

Similarly, space complexity describes how much space an algorithm needs to run. For example, a simple sort such as insertion sort needs an additional fixed amount of space to store the value of the element currently being inserted. This is an auxiliary space complexity of O(1) - it doesn't change with the size of the input. However, merge sort creates extra arrays in memory while it runs, with an auxiliary space complexity of O(n). This means the amount of extra space it requires is linearly correlated with the size of the input.

Of course, algorithm design is often a trade-off between time and space - algorithms with a low space complexity may require more time, and algoithms with a low time complexity may require more space.

For more information, you may find this tutorial useful.

To answer your updated question, you may find the wikipedia page on Heap Sort useful.

Timothy Jones
  • 21,495
  • 6
  • 60
  • 90
0

If you mean criteria for what type of sort to choose, here are some other items to consider.

The amount of data you have: To you have ten, one hundred, a thousand or millions of items to be sorted.

Complexity of the algorithm: The more complex the more testing will need to be done to make sure it is correct. For small amounts, a bubble sort or quick sort is easy to code and test, verse other sorts which may be overkill for the amount of data you have to sort.

How much time will it take to sort: If you have a large set, bubble/quick sort will take a lot of time, but if you have a lot of time, that may not be an issue. However, using a more complex algorithm will cut down the time to sort, but at the cost of more effort in coding and testing, which may be worth it if sorting goes from long (hours/days) to a shorter amount of time.

The data itself: Is the data close to being the same for everything. For some sorts you may end up with a linear list, so if you know something about the composition of the data, it may help in determining which algorithm to choose for the effort.

The amount of resources available: Do you have lots of memory in which you store all items, or do you need to store items to disk. If everything cannot fit in memory, merge sort may be best, where other may be better if you work with everything in memory.

Glenn
  • 1,169
  • 1
  • 14
  • 23