Верно ли, что чем сильнее «разрознен» массив чисел, тем больше времени займет его сортировка (допустим, пузырьком)?

Question

[VZVZ]

Скажем, если я отсортирую 2 отдельных массива, затем объединю их в один, добавив элементы одного между элементов другого (как косичку заплетают), а потом полученный массив еще раз отсортирую, то эта последняя сортировка займет меньше времени, чем если бы я изначально имел 1 массив?

Если неохота ответить на второй вопрос - ответьте на первый.

Answer 1

[uvelichitel]

Для сортировки пузырьком

1. имеет значение не средневзвешенное, а только максимальное отклонение позиции элемента от верной.То есть, другими словами, если вы в отсортированном массиве только поменяете местами крайние элементы, то его сортировка пузырьком займет максимально возможное время.
   
2. определенно да.
   

Для приведенного подхода(отдельно сортировать части потом слить) применяют сортировку слиянием merge-sort.

Answer 2

[MiiNiPaa]

1. В общем случае, нет.
2. Возможно, да, возможно, нет. Сильно зависит от используемого алгоритма и элементов массивов.

Comments

[VZVZ]

Алгоритм пузырек

[MiiNiPaa]

VZVZ: Зависит от массивов. В лучшем случае за 1 проход (линейная сложность) против N проходов, в худшем — N/2 прохода, если я правильно посчитал (квадратичная) против одного.

[VZVZ]

MiiNiPaa: не понял смысла фразы. Что "за 1 проход против N проходов"?

[MiiNiPaa]

VZVZ: В лучшем случае (при слиянии массивов элементы сразу станут на место) сортировка пузырьком на вашем подготовленном массиве сделает один проход по массиву и закончит работу, просто массив потребует макмимальное количество проходов по массиву равное количеству элементов.

[VZVZ]

MiiNiPaa: вы хотите сказать, что при Слиянии отсортированных массивов получается сразу отсортированный массив?
Что вы понимаете под Слиянием? Я тупо вставляю элементы одного массива (по одному) после элементов второго, не глядя (без всяких условных операций).

[MiiNiPaa]

VZVZ: Почему нет? Пример: {1, 3, 5, 7, 9} и {2, 4, 6, 8}

[VZVZ]

MiiNiPaa: А если {1, 2, 4, 6, 6} и {1, 3, 5, 7, 9}?

[MiiNiPaa]

VZVZ: Тогда это не будет лучшим случаем. Я перефразирую предыдущий ответ: "Относительная скорость зависит от содержания массивов. В лучшем случае подготовленный будет быстрее, в худшем — медленее."

Answer 3

[abcd0x00]

Очень похоже на сортировку слиянием и пирамидальную сортировку. Чтобы не изобретать эти сортировки (которые, естественно, быстрее пузырьковой), лучше найди их описание и реализуй каждую по отдельности.