All geek questions in one place

A sorting algorithm sorts a height of 1.14 billion people!

This is an interview question: considering that India is 1.14 billion people, what is the most efficient / efficient sorting algorithm that can be used to sort by their heights? (Heights data is available to you).

+3
source share
4 answers

About (p):

If the height can be rounded to the nearest mm, you can calculate the height histogram and print the counts in each bucket of the histogram in order. Expected RAM requires only a few KB for 32-bit ints 2000.

+10
source

Since the range of possible heights is quite small, I recommend:

  • Express all heights in millimeters.
  • , .
  • .
  • , .

, bin. ().

+4

, , , , , Θ(n+k), n - , k - .

, Ω(n×log n) , , , .

+2

radix sort, bin.

0
source

Source: https://habr.com/ru/post/1776030/

More articles:


All Articles