Sortowanie-liczba porównań

Hej, mam takie pytanko, jak należy wykonać liczbę porównań oraz kopiowań, aby posortować na przykład 4 liczby w najlepszym i najgorszym przypadku, używając algorytmu sortowania przez wstawianie?

A drugie pytanko jak przeprowadzić analizę czasową złożoności obliczeniowej algorytmu sorotowania bąbelkowego? Chciałbym również korzystając, z niezmiennika pętli udowodnić
poprawność algorytmu, natomiast też nie wiem jak do tego sie zabrać.

Dla zbyt nerwowych adminów - nie szukam gotowca, pytam o wskazówki.

Och wskazówki? Ależ proszę:

1. Weź do ręki kartę papieru i wykonaj to sortowanie licząc przy tym ile operacji wykonałeś. Dla ambitnych: zaimplementuj ten algorytm i dodaj sobie w nim liczniki które będziesz podbijał przy każdym porównaniu i przesuwaniu. Dla bardzo ambitnych: wyprowadź wzór na liczbę porównań i przypisań ;] Przypadek pesymistyczny to oczywiście ciag posortowany odwrotnie, optymistyczny to ciąg posortowany poprawnie.
2. Musisz wyprowadzić wzór na liczbę operacji elementarnych zależny od liczby elementów sortowanego ciągu.

Zalecam zaopatrzyć się we "Wprowadzenie do Algorytmów" pana Cormena.

Dzięki ;)