• Kurs C++ - strona główna
  • Kurs C++ - kontakt z autorem
  • Kurs C++ - mapa witryny
  • Kurs C++ - prawa autorskie
  • Kurs C++ - Kanał RSS
Informatyka krok po kroku
Użytkownik niezalogowany

Witaj nieznajomy

Reklamy
Randki

Sortowanie przez wybór (selection sort)

utworzono: 2004-09-03 zmodyfikowano: 2004-09-03 Autor: mgr inż. Marcin Nabiałek

Wprowadzenie

Sortowanie przez wybór jest w zasadzie jednym z najprostszych do zrozumienia i zaimplementowania w danym języku programowania algorytmem sortowania.

Sprecyzujmy warunki sortowania:

Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz operator porównania tych elementów, za pomocą którego możemy stwierdzić który z dwóch porównywanych elementów jest mniejszy, a który większy.

Wynik: n elementów uporządkowanych w taki sposób, że pierwszy element jest najmniejszy w sensie operatora porównania elementów, a ostatni jest elementem największym w sensie tego samego operatora.

Algorytm w postaci listy kroków

  1. Dla i od 1 do n-1 wykonaj:
    • Wśród elementów x[i], ..., x[n] znajdź takie k, że x[k] jest elementem najmniejszym w sensie pewnego operatora użytego do porównywania elementów
    • Zamień miejscami elementy x[i] i x[k]
  2. Elementy są już posortowane - zakończ algorytm

Jeśli nie wiesz jak zrealizować wyszukiwanie najmniejszego elementu w zbiorze, czyli tę część algorytmu: Wśród elementów x[i], ..., x[n] znajdź takie k, że x[k] jest elementem najmniejszym (...), przeczytaj koniecznie artykuł zatytułowany Wyszukiwanie elementu minimalnego.

Analiza algorytmu

Mimo, że algorytm jest dosyć prosty, oto wyjaśnienie. Za pierwszym razem wyszukujemy najmniejszy element wśród wszystkich danych elementów i po jego znalezieniu zamieniamy go z elementem który znajdował się na pierwszym miejscu naszych elementów.

Teraz nie zajmujemy się już pierwszym elementem, gdyż jest on ustawiony we właściwym miejscu, czyli pomniejszamy nasz zbiór elementów do przeszukiwania o jeden. Wyszukujemy najmniejszy element wśród naszego nowego zbioru i znów dokonujemy zamian.

Czynność powtarzamy do aż w naszym zbiorze elementów do przeszukiwania pozostaną tylko dwa elementy. Wtedy wykonujemy ostatnie wyszukiwanie.

Nie ma natomiast sensu już nic robić, gdy w zbiorze pozostanie jeden element, gdyż wiadomo, że jest on już dobrze ustawiony. Dlatego też zwróć uwagę, że w głównej pętli zmienna i zmienia się od 1 do n-1 a nie zmienia się ona od 1 do n.

dodajdo

1 | 2 | 3 | > | |>

Użytkowanie Serwisu oznacza zgodę na wykorzystywanie plików cookie. Szczegółowe informacje