Z porządkowaniem spotykamy się każdego dnia. Porządkujemy rzeczy i nawet nie zastanawiamy się, jak to robimy, np. układając w szufladzie kolejne miseczki, umieszczając mniejszą w większej, a tę większą następnie w jeszcze większej itd.

Również systemy informatyczne wykorzystują często tę operację – nazywamy ją sortowaniem. Posortowana jest np. lista kontaktów w telefonie – niezależnie od tego, w jakiej kolejności dodawaliśmy kontakty, możemy wyświetlać je posortowane alfabetycznie (sortowanie zgodnie z porządkiem liter alfabetu nazywamy porządkiem leksykograficznym).

Dużo łatwiej jest nam korzystać z danych uporządkowanych. Komputery do sortowania danych używają różnych algorytmów. W tym materiale zapoznamy się z algorytmem porządkowania metodą przez wybieranie.

Porządkujemy karty

Dana jest talia 24 kart, w której hierarchia kart przedstawia się następująco: 9, 10, W, D, K, A (dziewiątka, dziesiątka, walet, dama, król, as). Przyjmijmy, że po rozdaniu mamy w ręce kilka nieuporządkowanych kart. Chcemy uporządkować je od najmłodszej (o najmniejszej wartości) do najstarszej (o największej wartości), czyli niemalejąco. Możemy przyjąć następującą strategię:

1. Szukamy najmniejszej karty i zamieniamy ją z kartą pierwszą.

2. Spośród pozostałych kart wybieramy najmniejszą i zamieniamy z kartą drugą.

3. Kroki 1 oraz 2 powtarzamy dla wszystkich kart. Po ich wykonaniu karty są posortowane.

Przeanalizujmy przykład.

Algorytm porządkowania metodą przez wybieranie

Napiszemy program, który uporządkuje w sposób niemalejący wyniki konkursu. Wykorzystamy algorytm porządkowania metodą przez wybieranie.

Dane wejściowe:

• n – liczba naturalna, liczba elementów listy

• wyniki – lista zawierająca nieuporządkowane liczby naturalne z przedziału <1; 50>.

Wynik:

• wyniki – lista zawierająca uporządkowane niemalejąco liczby naturalne

Zmienne pomocnicze:

• i, j, k – liczby naturalne, indeksy porównywanych elementów listy

Zapiszemy algorytm w postaci listy kroków.

1. Wczytaj wartość zmiennej n.

2. Do listy wyniki wczytaj n wyników.

3. Do zmiennej i przypisz 0.

4. Dopóki i jest mniejsze od n - 1, wykonuj:

   4.1. Do zmiennej k przypisz wartość zmiennej i.

   4.2. Do zmiennej j przypisz i + 1.

   4.3. Dopóki j jest mniejsze od n, wykonuj:

   4.3.1. Jeżeli liczba wyniki[j] jest mniejsza od liczby wyniki[k], do zmiennej k przypisz wartość zmiennej j.

   4.3.2. Zwiększ wartość zmiennej j o 1.

   4.4. Zamień ze sobą wartości wyniki[i] i wyniki[k].

   4.5. Zwiększ i o 1.

5. Wypisz wartość zmiennej wyniki.

W kroku 1 i 2 przygotowujemy dane wejściowe.

Właściwy algorytm porządkowania wymaga dwóch pętli.

Pętla zewnętrzna

W kroku 4 konstruujemy pętlę zewnętrzną, która wykonuje się n - 1 razy, ponieważ, jak wynika z podanych przykładów, tyle trzeba wykonać operacji wyszukiwania elementu najmniejszego (albo największego). W omawianej pętli korzystamy ze zmiennej iteracyjnejzmienna iteracyjnazmiennej iteracyjnej i, która przyjmuje wartości od 0 do n - 1.

Wyszukiwanie elementu najmniejszego

Wyszukiwanie najmniejszego elementu rozpoczynamy od zainicjowania jego indeksu, czyli zmiennej pomocniczejzmienna pomocniczazmiennej pomocniczej k. Na początku każdego powtórzenia przypisujemy do niego i, tzn. indeks pierwszego nieuporządkowanego elementu listy.

W pętli wewnętrznejpętle zagnieżdżonepętli wewnętrznej zapisanej w krokach 4.2 i 4.3, odczytujemy kolejne nieuporządkowane elementy wskazywane za pomocą indeksu j, który przyjmuje wartości od i + 1 do n - 1. Jeżeli dla któregoś z elementów warunek wyniki[j] < wyniki[k] będzie prawdziwy, aktualizujemy indeks najmniejszego elementu: k = j.

Zamiana elementów

Po zakończeniu pętli wewnętrznej indeks najmniejszego elementu zapisany jest w zmiennej k. Są dwie możliwości:

• wśród nieuporządkowanych elementów nie ma mniejszego i wartość k pozostaje równa i, co oznacza, że kolejny element jest już na właściwym miejscu,

• znaleźliśmy mniejszy element wśród nieuporządkowanych elementów i wartość zmiennej k uległa zmianie.

By uprościć budowę algorytmu, wykonujemy zamianę elementów o indeksach i oraz k, nawet jeżeli są równe. Operację tę wykonujemy w kroku 4.4.

Zapoznajmy się z przykładem, który pozwoli lepiej zrozumieć działania wykonywane w pętlach.

Zapis algorytmu za pomocą języka Python

n = 10
wyniki = [24, 14, 34, 11, 50, 39, 44, 15, 45, 15]
print(*wyniki)

Pętle

Zacznijmy od zapisania pętli zewnętrznej i zainicjowania indeksu najmniejszego elementu.

for i in range(n - 1):
	k = i  # Początkowy indeks najmniejszego elementu

Zapiszmy pętlę wewnętrzną.

    for j in range(i + 1, n):
        if wyniki[j] < wyniki[k]:
            k = j

Pozostaje zapisanie operacji zamiany wartości elementów o indeksach k oraz i, a następnie wypisanie wyniku.

	# zamiana wartości
	wyniki[i], wyniki[k] = wyniki[k], wyniki[i]

# wypisanie posortowanej listy
print(*wyniki)

Użyty sposób zamiany wartości jest przykładem możliwego w języku Python przypisania wielokrotnego. W przypadku tej konstrukcji do zmiennych z lewej strony przypisywane są wartości kolejnych zmiennych z prawej strony. Są to początkowe wartości tych zmiennych. Dzięki temu możemy zamienić wartości dwóch elementów.

# zamiana liczb
tmp = wyniki[i]  # użycie dodatkowej zmiennej tymczasowej do przechowania wartości
wyniki[i] = wyniki[k]
wyniki[k] = tmp

liczby[0] = liczby[1]

liczby[1] = liczby[0]

Przetestujmy działanie programu.

24 14 34 11 50 39 44 15 45 15
11 14 15 15 24 34 39 44 45 50

Notatnik

Animacja (samouczek)

Film przedstawia program wykorzystujący algorytm porządkowania przez wybieranie. Wypisuje znaki z pobranego napisu w porządku alfabetycznym (leksykograficznym), np. dla słowa czara powinniśmy otrzymać ciąg znaków a a c r z.

RRs30Jc8FiQa5

Film przedstawia algorytm sortowania metodą porządkowania

Film przedstawia algorytm sortowania metodą porządkowania

Film dostępny pod adresem /preview/resource/RRs30Jc8FiQa5

Film przedstawia algorytm sortowania metodą porządkowania

Pełny kod programu:

napis = input("Podaj ciąg znaków: ")
napis = napis.lower().replace(" ", "")

napis = list(napis)  # Funkcja list() zamienia napis na listę
n = len(napis)  # Funkcja len() zwraca liczbę znaków (długość łańcucha znaków)
print("Lista znaków:", napis)
print("Liczba znaków:", n)

for i in range(n - 1):
    k = i
    for j in range(i + 1, n):
        if napis[k] > napis[j]:
            k = j
    print("Powtórzenie:", i + 1)
    print(*napis)
    print("i =", i, "k =", k, "zamiana:", napis[i], "z", napis[k])
    print()
    napis[i], napis[k] = napis[k], napis[i]

print(*napis)

Podaj ciąg znaków: 675431
Lista znaków: ['6', '7', '5', '4', '3', '1']
Liczba znaków: 6
Powtórzenie: 1
['6', '7', '5', '4', '3', '1']
i = 0 k = 5 zamiana: 6 z 1

Powtórzenie: 2
['1', '7', '5', '4', '3', '6']
i = 1 k = 4 zamiana: 7 z 3

Powtórzenie: 3
['1', '3', '5', '4', '7', '6']
i = 2 k = 3 zamiana: 5 z 4

Powtórzenie: 4
['1', '3', '4', '5', '7', '6']
i = 3 k = 3 zamiana: 5 z 5

Powtórzenie: 5
['1', '3', '4', '5', '7', '6']
i = 4 k = 5 zamiana: 7 z 6

1 3 4 5 6 7

if napis[j] > napis[k]:

if napis[k] < napis[j]:

Zestaw ćwiczeń interaktywnych

zmienna_pomocnicza = zmienna_a
XXX = YYY
YYY = zmienna_pomocnicza

Słownik