Интервью по алгоритму сортировки

Question

Учитывая большой массив, который имеет номера в диапазоне от 1 до 100. Каков наилучший подход к его сортировке?

Интервьюер выделял на слове диапазон т.е. максимальное количество, которое присутствует в массиве 100.

Answer 1

попробовать это:

long result[100] = {0}; 

for (iterator it = vec.begin(); it != vec.end(); ++it) 
{ 
    result[*it - 1]++; 
} 

Таким образом, вы будете двигаться линейные над вектором и подсчитайте все числа, которые существуют. В результате вы получите, сколько у вас было 1, сколько у вас было 2 и т. Д., То есть оно будет таким же отсортированным.

UPD: как KillianDS написал, я имею в виду counting sort. Это быстрый.

Answer 2

Может быть, они хотели услышать о radix sort.

Answer 3

Кажется, что подсчет сортировки является наиболее подходящим алгоритмом для этой проблемы, это O (n), стабильный и простой в реализации. http://en.wikipedia.org/wiki/Counting_sort

Answer 4

Ну, так как ответ был в основном дан, пример кода. Нет необходимости копировать данные из исходного массива; он может быть получен из данных в гистограмме, называется вариант алгоритма в разделе вики counting sort variant:

std::vector <size_t> hist(101, 0);  // using index 1 to 100 inclusive 
size_t i, j, n; 
    for (i = 0; i < vec.size(); i++) 
     hist[vec[i]]++; 
    i = 0; 
    for(j = 1; j <= 100; j++) 
     for(n = hist[j]; n; n--) 
      vec[i++] = j;