najgorszy przypadek porównania do sortowania w specjalnym przypadku - algorytm, sortowanie

Rozważmy Wstawianie Sortowanie z Sentinelem na nwartości, gdzie każda wartość występuje dokładnie dwa razy w danych wejściowych (więc n musi być parzysta). Najlepszym argumentem dla porównania jest to, że elementy są już posortowane, a dokładna liczba porównań w najlepszym przypadku to n-1. Sądzę, że najgorszym sposobem do porównania jest sytuacja, gdy elementy są sortowane odwrotnie. Ale jaka jest dokładna liczba porównań w tym przypadku? i dlaczego?

Odpowiedzi:

tablica z 1 elementem jest posortowana. i n-1 elementy wstawione do tablicy

for(int i=1 ; i<n ; i++){
int valueForInsert = a[i];
.
.
.
}

dla elementu w indeksie ja, mamy ja porównania w najgorszym przypadku. więc 1 + 2 + 3 + ... + (n - 1) porównania występują w odwróconej posortowanej tablicy. a wzór dla tablicy o długości n jest równy: (n * (n - 1)) / 2