записывать несортированный массив последовательных строк, отсортированный в файл эффективно

Question

У меня есть массив строк, содержащих неупорядоченные последовательные числа (от 0 до n), например. [7a, 1b, 2c, 0d, 6e, 5f, 3g, 4h], и я хочу записать числа в порядке в файл.

После того, как, например:

0d 
1b 
2c 
3g 
4h 
5f 
6e 
7a 

Строка не все имеют одинаковую длину.

Я пытался найти способ сделать это как быстро, так и не занимая слишком много места. Я нашел способ, которым я могу это сделать в O (n) пространственной сложности и O (n) производительности: я создаю массив с n ячейками и вставляю каждую строку в свой номер ячейки.

for (i = 0; i < n; i++) 
    sortedArray[originalArray[i]] = originalArray[i] 

... что-то вроде этого (создание нового массива размером исходного и заполнить его в один проход), а затем с другой цикл записать содержимое отсортированного массива в файл.

Но я ищу лучший способ сделать это.

Answer 1

Предположим, что ведущие числа в ваших строках действительно последовательны и не повторяются, вы не достигнете более высокой временной сложности, чем если бы вы использовали подход, который вы описываете в вопросе, или что-то в этом роде. Это требует рабочего пространства, пропорционального количеству строк.

В сравнении

• стандартная сортировка слиянием требует также рабочее пространство, пропорциональное количеству строк (но вы можете уйти с вдвое меньше по мере приближения в этом вопросе, если вы внимательны) , и имеет сложность времени O(n log n). Альтернативно,
• быстрая сортировка на месте и имеет O(n log n) временная сложность в среднем; если вы тщательно его реализуете, то в худшем случае требуется только рабочее пространство O(log n) - постоянная сумма на стек стека в рекурсивной версии или стек, вмещающий это множество элементов в нерекурсивном.
• Для сортировки на месте на месте требуется O(log n) рабочее пространство (и не требует такой же помощи, как и быстрая сортировка), и имеет среднюю сложность времени в среднем. Он имеет тенденцию бить большинство других O(n^2) подходов довольно удобно, большую часть времени.
• вставка сортировка видов на месте и требует O(1) рабочее место, но имеет O(n^2) временная сложность. Это хорошо понято, легко реализуется и очень быстро на практике для небольших размеров ввода.

Есть много других альтернатив, но я думаю, что они разумно представляют ваши варианты. Какой из них лучше всего соответствует вашим потребностям, зависит от границ вашего размера проблемы и от того, как вы взвешиваете пространство против скорости. Если размер вашей проблемы может быть очень большим, и вы не можете позволить себе O(n) накладные расходы на место, тогда дайте быстрое тщательное рассмотрение. Если размер проблемы определен невелик, но сохранение пространства имеет решающее значение, то рассмотрите сортировку вставки. Если высокая скорость важна, и вы можете позволить себе накладные расходы, то ваш оригинальный подход ужасно привлекателен.