Sortowanie Przez Wybieranie
- Sortowanie przez wybieranie
- jedna z prostszych metod sortowania o złożoności O(n2). Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.
Algorytm przedstawia się następująco:
- wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy.
- zamień wartość minimalną, z elementem na pozycji i
Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu.
Algorytm w zaprezentowanej postaci nie jest stabilny, jednakże niewielkim kosztem można uczynić go algorytmem sortującym stabilnie. Aby tego dokonać należy jako warunek wyszukiwania minimum/maksimum zastosować nierówność nieostrą zamiast ostrej.
Kod w Pascalu
const
n=100;
var
i:integer;
j:integer;
temp,indextemp:integer;
tab:array[1..n]of integer;
BEGIN
randomize;
for i:=1 to n do tab[i]:=random(n);
for i:=1 to n-1 do begin
indextemp = i;
temp:=tab[i];
for j:=i to n do begin
if tab[j]<=temp then begin
temp := tab[j];
indextemp := j;
end;
end;
tab[indextemp]:= tab[i];
tab[i] := temp;
end;
END.
Podobne strony
Podobne Strony • Szyfr Cezara • Sortowanie Przez Kopcowanie • Sortowanie Babelkowe • Rok Przestepny • Wieża hanoi • wyswietlanie liczby calkowitej metodą odejmowania poteg • Parzysta Nieparzysta • Ruchoma Gwiazdka • Sortowanie Przez Wstawianie • QuickSort • Nww • Metoda Babelkowa • Silnia • Miejsca Zerowe Funkcji Kwadratowej • Fibonacci
wersja strony: 4, ostatnia edycja: 26 Apr 2009 17:35