Informatyka MIMUW

Na sortowanie bąbelkowe można spojrzeć jeszcze inaczej. W każdej fazie przepychamy na pierwsze miejsce w nieuporządkowanej części tablicy element najmniejszy. Symetrycznie moglibyśmy sortować poczynając od elementów nawiększych. W sortowaniu przez wybór nie przepychamy elementu największego (najmniejszego) na jego miejsce w ciągu uporządkowanym, tylko znajdujemy jego pozycję, a następnie znaleziony element - największy w części nieuporządkowanej - zamieniamy z elementem, który znajduje się na docelowej pozycji elementu największego. Niech \( Max(i) \) będzie funkcją, której wartością jest pozycja największego elementu w podtablicy \( a[1..i] \). Oto schemat algorytmu sortowania przez wybór:

Algorytm Schemat algorytmu sortowania przez wybór

schemat SelectionSort 
  for i := n downto 2 do 
  begin
    j := Max(i);  
    Exchange(i,j)  
  end;

Dlaczego użyliśmy słowa schemat? Zauważmy, że do pełnego zdefinowania algorytmu, a także dla jego analizy, niezbędne jest zdefiniowanie funkcji \( Max \). W klasycznym sortowaniu przez wybór pozycję elementu największego w podtablicy \( a[1..i] \) wyznaczamy przeszukując podtablicę od lewej do prawej, pamiętając w zmiennej pomocniczej pozycję dotychczas największego elementu i modyfikując wartość tej zmiennej każdorazowo po napotkaniu elementu większego od dotychczas największego. Oto pełny zapis algorytmu sortowania przez wybór - algorytmu SelectionSort.

Algorytm Sortowanie przez wybór

SelectionSort 
  for i := n downto 2 do 
    begin 
      j := 1;
      for  k := 2 to i do 
        if  a[k] > a[j] then  j := k; 
      Exchange(i,j)  
  end;

Nietrudno zauważyć, że algorytm SelectionSort wykonuje taką samą liczbę porównań, co algorytm bąbelkowy. Jednak w tym przypadku maksymalna liczba zamian wynosi tylko \( n-1 \).

Należy podkreślić, że w implementacji schematu sortowania przez wybór mamy swobodę w realizacji funkcji \( Max \). Wykorzystamy to w algorytmie sortowania z użyciem struktury danych zwanej kopcem.