Sortowanie przez wstawianie – przykładowe zadania maturalne

Zadanie 1. Słówka

Pani Kasia jest nauczycielką języka polskiego. W ramach urozmaicenia zajęć wymyśliła konkurs odgadywania słów, w których pozamieniano miejscami litery. Ze względu na dużą liczbę słów poprosiła Maćka, aby napisał program, który przygotuje wybrane przez nią słówka na konkurs.

Dany jest plik słowa.txt, który zawiera 30 słów. Każdy wyraz zapisany jest w osobnej linii i składa się wyłącznie z małych liter. Napisz program, który w każdym z wyrazów z pliku ułoży liter w kolejności odwrotnej niż porządek alfabetyczny, a następnie wypisze zmienione słowa (każde w nowej linii).

Plik słowa.txt:

Do oceny oddajesz:

• plik wyniki.txt z odpowiedzią (plik tekstowy zawierający w każdej linii odpowiadający wyraz z pliku słowa.txt o literach posortowanych w kolejności odwrotnej niż porządek alfabetyczny)

• plik(i) z komputerową realizacją zadania (kodem programu)

Rozwiązanie:

Rozwiązanie przedstawimy w postaci pseudokodu.

Wczytujemy dane z pliku. SortowaniesortowanieSortowanie dla każdego z wyrazów będzie odbywało się oddzielnie. Aby skorzystać z sortowania przez wstawianie, potrzebujemy zmiennych przechowujących aktualny znak oraz indeks, pod który dany znak wstawimy:

slowa[1..30] ← wczytaj dane z pliku "słowa.txt"

aktualnyZnak ← ""
aktualnyIndeks ← 0

dla i = 1, 2, ..., 30 wykonuj:

W każdym przypadku sortujemy nierosnąco, zatem będziemy porównywać element z jego sąsiadem o niższym indeksie. W związku z tym zaczynamy od znaku z indeksem równym 2 (wyrazy indeksowane są od 1). Korzystamy z funkcji długość() przyjmującej łańcuch znaków i zwracającej jego długość. Jest ona dostępna w każdym języku programowania dostępnym na maturze:

slowa[1..30] ← wczytaj dane z pliku "słowa.txt"

aktualnyZnak ← ""
aktualnyIndeks ← 0

dla i = 1, 2, ..., 30 wykonuj:
	slowo ← slowa[i]
	dla j = 2, 3, ..., długość (slowo) wykonuj:
		aktualnyZnak ← slowo[j]
		aktualnyIndeks ← j

Następnie porównujemy aktualnyZnak z jego wcześniejszymi sąsiadami i dopóki jest on od nich większy, przesuwamy sąsiadów w prawo. Sortujemy jednak znaki, a nie liczby. Korzystamy zatem z funkcji ascii(), która zwraca kod ASCIIkod asciikod ASCII dla znaku podanego jako argument i umożliwia porównywanie liter. Jej działanie można zaimplementować w każdym dostępnym języku i jest to zadanie ucznia:

slowa[1..30] ← wczytaj dane z pliku "słowa.txt"

aktualnyZnak ← ""
aktualnyIndeks ← 0

dla i = 1, 2, ..., 30 wykonuj:
	slowo ← slowa[i]
	dla j = 2, 3, ..., długość (slowo) wykonuj:
		aktualnyZnak ← slowo[j]
		aktualnyIndeks ← j

		dopóki aktualnyIndeks > 0 oraz ascii(aktualnyZnak) > ascii(slowa[i][aktualnyIndeks - 1]) wykonuj:
			slowo[aktualnyIndeks] ← slowo[aktualnyIndeks - 1]
			aktualnyIndeks ← aktualnyIndeks - 1

Po zakończeniu pętli zmienna aktualnyIndeks zawiera właściwą pozycję dla porównywanego znaku. Wstawiamy go zatem z powrotem do tablicy.

slowa[1..30] ← wczytaj dane z pliku "słowa.txt"

aktualnyZnak ← ""
aktualnyIndeks ← 0

dla i = 1, 2, ..., 30 wykonuj:
	slowo ← slowa[i]
	dla j = 2, 3, ..., długość (slowo) wykonuj:
		aktualnyZnak ← slowo[j]
		aktualnyIndeks ← j

		dopóki aktualnyIndeks > 0 oraz ascii(aktualnyZnak) > ascii(slowa[i][aktualnyIndeks - 1]) wykonuj:
			slowo[aktualnyIndeks] ← slowo[aktualnyIndeks - 1]
			aktualnyIndeks ← aktualnyIndeks - 1

		slowo[aktualnyIndeks] ← aktualnyZnak

Na koniec zapisujemy posortowane słowo do pliku i kontynuujemy algorytm dla kolejnych wyrazów z tablicy.

slowa[1..30] ← wczytaj dane z pliku "słowa.txt"

aktualnyZnak ← ""
aktualnyIndeks ← 0

dla i = 1, 2, ..., 30 wykonuj:
	slowo ← slowa[i]
	dla j = 2, 3, ..., długość (slowo) wykonuj:
		aktualnyZnak ← slowo[j]
		aktualnyIndeks ← j

		dopóki aktualnyIndeks > 0 oraz ascii(aktualnyZnak) > ascii(slowa[i][aktualnyIndeks - 1]) wykonuj:
			slowo[aktualnyIndeks] ← slowo[aktualnyIndeks - 1]
			aktualnyIndeks ← aktualnyIndeks - 1

		slowo[aktualnyIndeks] ← aktualnyZnak
        
	dopisz slowo do pliku "wyniki.txt"

Odpowiedź do zadania

Plik wyniki.txt:

Słownik