Porównania
Zamiany
Przebieg

  • Porównywane
  • Najmniejsza dotąd
  • Zamienione
  • Na miejscu

Więcej o sortowaniu przez wybieranie

Sortowanie przez wybieranie

Sortowanie przez wybieranie buduje posortowaną listę od początku. Każdy przebieg przegląda wartości, które nie są jeszcze posortowane, zapamiętuje najmniejszą i zamienia ją z wartością na pierwszym nieposortowanym miejscu. Odtwarzaj sortowanie w dowolnym tempie albo przechodź po jednym porównaniu i obserwuj liczniki porównań, zamian i przebiegów. Naciśnij Odtwórz, aby obejrzeć sortowanie, albo Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Kafelki liczą porównania, zamiany i przebiegi. Wybierz liczbę słupków, ich początkowy układ albo wpisz własne liczby. Gdy plansza jest zaznaczona, strzałki przechodzą o krok, spacja uruchamia i wstrzymuje, a Home i End przenoszą na początek i na koniec.

Jak to działa

  1. Wybierz liczbę słupków i ich początkowy układ: losowy, prawie posortowany, odwrócony lub z kilkoma różnymi wartościami. Możesz też wpisać własne liczby.
  2. Naciśnij Odtwórz albo używaj przycisków Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce sortowania.
  3. Obserwuj, jak w trakcie przeglądania zmienia się dotąd najmniejsza wartość i jak zamiana na końcu każdego przebiegu stawia ją na miejscu.

Jak działa sortowanie przez wybieranie

Przejrzyj wszystkie wartości na liście i zapamiętaj najmniejszą. Zamień ją z pierwszą wartością: pierwsze miejsce jest już ostateczne. Potem zrób to samo z resztą listy, zaczynając o jedno miejsce dalej. Po n − 1 przebiegach każda wartość jest na swoim miejscu, a ostatnia trafia na nie sama.

Dużo porównań, mało zamian

Przeglądanie nigdy nie kończy się wcześniej, bo dopiero po sprawdzeniu każdej pozostałej wartości wiadomo na pewno, która jest najmniejsza. Dlatego sortowanie przez wybieranie wykonuje dla n wartości dokładnie n(n − 1)/2 porównań, niezależnie od tego, czy lista jest posortowana, odwrócona czy losowa. W zamian wykonuje najwyżej n − 1 zamian, po jednej na przebieg. To rozsądny wybór, gdy przeniesienie wartości kosztuje dużo więcej niż porównanie dwóch.

Często zadawane pytania

Jak działa sortowanie przez wybieranie?

Wielokrotnie wybiera najmniejszą jeszcze nieposortowaną wartość i zamienia ją z wartością na pierwszym nieposortowanym miejscu. Po przebiegu k na pierwszych k miejscach stoi k najmniejszych wartości w kolejności.

Ile porównań i zamian wykonuje sortowanie przez wybieranie?

Zawsze n(n − 1)/2 porównań dla n wartości: 45 dla 10 wartości, 780 dla 40. Zamian jest najwyżej n − 1, po jednej na przebieg, i mniej, gdy najmniejsza wartość jest już na miejscu.

Dlaczego posortowana lista zajmuje tyle samo czasu co odwrócona?

Bo każdy przebieg musi sprawdzić każdą pozostałą wartość, aby mieć pewność, że znalazł najmniejszą. W przeciwieństwie do sortowania bąbelkowego i sortowania przez wstawianie sortowanie przez wybieranie nie potrafi poznać po porównaniach, że lista jest już posortowana.

Czy sortowanie przez wybieranie jest stabilne?

Nie w tej zwykłej postaci. Zamiana może przenieść wartość za równą jej wartość: w 2, 2, 1 pierwsza dwójka zamienia się z jedynką i ląduje za drugą dwójką. Wersja, która przesuwa wartości zamiast je zamieniać, jest stabilna, ale kosztem większej liczby przesunięć.

Czy moje liczby są gdzieś wysyłane?

Nie. Sortowanie działa w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora