What are the criteria for choosing a sorting algorithm?

Question

I read the sorting method, which included sorting bubbles, sorting sorting, merging sorting, heap sorting, bucket sorting, etc. They also contain temporary complexity that helps us find out which sorting is effective. So I had a basic question. If we will contain data, then how will we choose sorting. The complexity of time is one of the parameters that helps us solve the sorting method. But is there another option for choosing a sorting method?

Just trying to figure out the sorting for a better understanding.

Having some sort of heap sort request:

• Where do we use heap sorting?

• What is the greater advantage of heap sorting (other than O (n log n) time complexity)?

• What is the disadvantage of sorting heaps?

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

• Any scenario where we should use heap sort or heap sort is the best option (except priority queue)?

• Before applying heap sorting on data, what parameter will we look for in the data?

Answer 1

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

In general, the complexity of time allows us to find out how the performance of an algorithm changes as the size of the data set increases. What to consider:

• How much data are you going to sort? . This will help you find out if you need to look for an algorithm with very low time complexity.
• How sorted will your data be? Will it be partially sorted? Accidentally sorted? This may affect the time complexity of the sorting algorithm. Most algorithms will have the worst and best cases — you want to make sure that you are not using the algorithm for the worst case data set.
• The complexity of time is not the same as runtime. Remember that time complexity only describes how the performance of an algorithm changes as the size of the data set increases. An algorithm that always performs a single pass over all inputs will be O (n) - its performance linearly correlates with the size of the input. But the algorithm, which always performs two passes over the data set, is also O (n) - the correlation is still linear, even if the constant (and the actual run time) is different.

Similarly, the complexity of the space describes how much space the algorithm should execute. For example, simple sorting, such as insertion sort , requires an additional fixed amount of space to hold the value of the element that is currently inserted. This is an auxiliary spatial complexity O (1) - it does not change with the size of the input. However, merge sort creates additional arrays in memory at runtime, with auxiliary spatial complexity of O (n). This means that the amount of extra space that it requires is linearly correlated with the size of the input.

Of course, developing algorithms is often a compromise between time and space. Algorithms with low space complexity may require more time, and algorithms with low time complexity may require more space.

For more information you can find this tutorial .

---

To answer your updated question, you can find the useful wikipedia page for Heap Sort .

Answer 2

If you mean the criteria for choosing the type of sorting, consider some other issues.

The amount of data you have: you need to sort ten, one hundred, one thousand, or millions of items.

Algorithm complexity: the more complex, the more tests will need to be done to make sure that it is correct. For small quantities, bubble sorting, or quick sort, it’s easy to code and test verses of other varieties that may be redundant for the amount of data you need to sort.

How long does it take to sort: if you have a large set, it will take a lot of time to create bubbles / quick sort, but if you have a lot of time, this may not be a problem. However, the use of a more complex algorithm will reduce the sorting time, but at the cost of a lot of coding and testing efforts, which can be useful if sorting is from long (hours / days) to a shorter time.

The data itself: is the data close to all the same? For some species, you can get a linear list, so if you know something about the composition of the data, this can help determine which algorithm to choose for the effort.

Amount of resources available: you have a lot of memory in which all the elements are stored, or you need to store items on disk. If everything cannot fit in memory, merge sorting might be better, if the other could be better, if you work with everything in memory.