Sortowanie przez wybieranie

Jaka jest średnia złożoność obliczeniowa sortowania przez wybieranie?
Przyda się też jakiś dowodzik :)

Złożoność wynosi dokładnie O(n^2) (gdzie O to duże theta), gdyż algorytm wykonuje zawsze te same kroki (zakładając, że operacja max(a, b) jest jednostkowa).

Mamy n - 1 przebiegów pętli, w i-tym przebiegu porównujemy n - i elementów z elementem i-tym i zamieniamy je miejscami. Wobec tego samych operacji max jest n - 1 + n - 2 + ... + 1 = (n - 1) * n / 2.

A czy w przypadku, gdy nie będziemy używać porównań, aby otrzymać następny element? Można na przykład zastosować funkcję partition celem znalezienia kolejnego najmniejszego elementu:

procedureSELECT(A,n,k)
  (*Wtablicy A(1),...,A(n)poszukujemy k-tego najmniejszego elementu tablicy i wstawiamy go napo-
  zycji k.
  integer n,k,m,r,j
  m=1;r=n+1;A(n+1)=+inf
  loop //za każdym razem gdy wchodzimy do pętli 1<=m<=k<=r<=n+1
    j=r  //ustawiaj jako najwyższy index tablicy+1
    call PARTITION(m,j) //zwraca j takie, że A(j) jest j-tą najmniejszą wartością
    case
      :k=j:return
      :k<j:r=j //j jest nowym górnym limitem
      :else:m=j+1 //j+1 jest nowym niskim limitem
    endcase
  repeat
endSELECT

Średnia złożoność obliczeniowa tego algorytmu jest O(n) (co najwyżej rzędu). Czy w tym przypadku średnia złożoność obliczeniowa dalej jest n^2

Algorytm Select(1) w optymistycznym przypadku (kiedy naszym pierwszym elementem dzielącym jest minimum) wykonuje tyle samo porównań co Minimum. W pesymistycznym wykonuje O(n^2) porównań (jeżeli zawsze naszym elementem dzielącym jest maksimum).

Średnia złożoność obliczeniowa Select(1) to O(n). Tak więc n wywołań Select(1) ma średnią złożoność obliczeniową O(n^{2). Pesymistycznie sortowanie przez wybieranie z użyciem algorytmu Select ma złożoność O(n}3).

Nie rozumiem po co zastępować liczenie minimum algorytmem Select. Nie dość że pesymistyczna złożoność obliczeniowa jest drastycznie gorsza, optymistyczna i średnia gorsza o stały współczynnik (i to pewnie dość duży, strzelam że to jest 5 - 10) to jeszcze jest dużo więcej kodu do napisania. Chyba, że dla rozrywki.