: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > sortowanie >

S O R T O W A N I E   P R Z E Z   W Y B Ó R

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Sortowanie przez wybór (Selection Sort) jest algorytmem porządkowania wykorzystującym liniowe wyszukiwanie elementu najmniejszego. Wyszukujemy najmniejszy element w tablicy i zapisujemy go na miejscu pierwszym, z pozostałych ponownie wybieramy najmniejszy i zapisujemy go na miejscu drugim, itd.

  1. Dla wszystkich elementów i z zakresu od 1 do n-1:

    • znajdź najmniejszą liczbę w tablicy od miejsca i do miejsca n

    • liczbę najmniejszą zapisz na miejscu i, liczbę z miejsca i zapisz w miejscu znalezionej liczby najmniejszej

Type
  Tablica = Array[1..1000] Of Integer;

Procedure Sort(Var a : Tablica; n : Integer);
Var
  i, j, k, tmp : Integer;
Begin
  For i:=1 To n-1 Do
    Begin
      k:=i;
      For j:=i+1 To n Do
        If a[k]>a[j] Then k:=j;
      tmp:=a[i];
      a[i]:=a[k];
      a[k]:=tmp;
    End;
End;

Do operacji zamiany liczb w tablicy można wykorzystać osobną procedurę Zamien:

Type
  Tablica = Array[1..1000] Of Integer;

Procedure Zamien(Var a, b : Integer);
Var
  tmp : Integer;
Begin
  tmp:=a;
  a:=b;
  b:=tmp;
End;

Procedure Sort(Var a : Tablica; n : Integer);
Var
  i, j, k : Integer;
Begin
  For i:=1 To n-1 Do
    Begin
      k:=i;
      For j:=i+1 To n Do
        If a[k]>a[j] Then k:=j;
      Zamien(a[i], a[k]);
    End;
End;

Złożoność obliczeniowa: O(n2).