Geek Answers Handbook

Efficiency of sorting algorithms

Tomorrow I am studying a pretty important interview, and there is one thing that I have big problems with: sorting algorithms and BigO efficiency.

Which number is important to know? Best, worst, or average performance?

+4
source share
7 answers

worst followed by average. be aware of the real impact of the so-called "hidden constants", for example, the classic quick sort algorithm is O (n ^ 2) in the worst case and O (n log n) on average, while mergesort is O (n log n) in worst case, but quicksort in practice outperforms merging.

+4
source

Take a look here ...

All necessary data

http://en.wikipedia.org/wiki/Sorting_algorithm

+3
source

All of them are important to know, of course. You should understand that the advantages of one sorting algorithm in the average case can become a terrible shortage in the worst case, or the worst case is not so bad, but the best case is not so good, and it only works on well unsorted data, etc.

+2
source

In short.

The effectiveness of the sorting algorithm depends on the input data and the task.

  • sorting the maximum speed that can be archived is n * log (n)
  • If the data contains sorted auxiliary data, the maximum speed may be better than n * log (n)
  • if the data consists of duplicates, sorting can be done in almost linear time
  • most sorting algorithms have their own applications

Most quick sort options have their middle case also n * log (n), but yours are usually faster than other rather than highly optimized algorithms. This is faster when it is unstable, but stable options are only a few less. The main problem is the worst case. The best random fix is ​​Introsort.

Most merge sort options have their best, medium, and worst case, tied to n * log (n). It is stable and relatively easy to scale. BUT this requires a binary tree (or its emulation) relative to the size of the common elements. The main problem is memory. The best random fix is ​​timsort.

Sorting algorithms also change according to the size of the input. I can make a request for beginners that there are no matches for merge sort options for entering 10T data.

+2
source

I recommend that you do not just remember these factoids. Find out why they are who they are. If I were interviewing you, I would not ask questions that show that you understand how to analyze the algorithm, and not just discard what you saw on the web page or in the book. Also, the day before the interview is not the time for this study.

Wish you luck! Please let us know how it was in the comments!

+1
source

I ended up with one set of interviews at my college right now ...

Each algorithm has its advantages, otherwise it will not exist. So, it’s better to understand what's good with the algorithm you are learning. Where is that good? How can this be improved?

I think you will automatically need to read various signs of effectiveness when you do this. Remember the worst case and pay attention to the average case, the best cases are rare.

All the best for your interview.

+1
source

You can also see other types of sorting that can be used when certain conditions exist. For example, consider Radix collation. http://en.wikipedia.org/wiki/Radix_sort

0
source

More articles:


All Articles