Количество (n-1) сравнения, необходимого для сортировки n элементов?

Question

Если у меня есть n элементов, скажем,

a, b, c

Тогда я могу использовать 6 сравнений с (n-1) компараторами для сортировки элементов:

if (a > b && b > c) {
   a, b, c
}
else if (a < b && b < c) {
   c, b, a
}
else if (b > a && a > c) {
   b, a, c
}
else if (a > c && c > b) {
   a, c, b
}
else if (b > c && c > a) {
   b, c, a
}
else if (c > a && a > b) {
   c, a, b
}

Теперь у меня двавопросы:

1. Охватывают ли эти 6 сравнений все возможные комбинации 3 элементов?

2. Если да, верно ли сравнивать n элементов, п!нужны сравнения с (n-1) компараторами?

Answer 1

Для начала, да, вы рассмотрели все случаи.Однако то, что у вас есть, не является оптимальным числом сравнений.Если вам позволено иметь более сложную логику ветвления, тогда вы можете избежать множества сравнений.Один из способов думать об этом заключается в том, что вы можете по существу запустить алгоритм сортировки для входных данных, за исключением того, что вместо обмена элементами вы просто отслеживаете, как проходили предыдущие сравнения, и используете их, чтобы влиять на те сравнения, которые вы делаете позже.Используя такой подход, вы можете сортировать только с Θ (n lg n) сравнений (хотя ваш исходный код будет содержать Θ (n!) Сравнений; вы просто не будете использовать их все).

Answer 2

Да, потому что есть n!способы сортировки n элементов (перестановок).один из них - «правильный» путь, так что это правда - не более n!....

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

Answer 3

Можно отсортировать массив из N целых чисел, используя N log_2 N сравнений, что намного меньше, чем N !.Эти сравнения просты (сравните только два целых числа).Вот где стандартный результат сложности O (N log N) приходит для QuickSort и MergeSort.Это также доказано оптимальным, то есть нет способа сортировки массива с использованием меньшего количества сравнений, чем это.

Итак, для сортировки N целых чисел необходимо N log_2 N сравнений с 1 компаратором в каждом.