Strefa wyzwań

Już wiesz

Jak działa metoda sortowania przez wstawianie.
W jaki sposób działa algorytm sortowania przez wstawianie i umiesz go przeanalizować dla konkretnego przykładu.
Jak zaimplementować algorytm sortowania przez wstawianie w języku Python.

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce.

Ćwiczenie 1

R1GSZQ3P8KOXZ

Ćwiczenie 2

RCK9LPBTEO9NS

Ćwiczenie 3

R68X4CO64H1EX

Ćwiczenie 4

R1HBD4VTOPE52

Ćwiczenie 5

Zapoznaj się z poniższym pseudokodem. Wskaż, ile razy zostaną wykonane linie 5. i 7. dla tablicy [10, 7, 0, 1, 12, 8].

Specyfikacja:

Dane:

n – liczba elementów do posortowania; liczba naturalna
tab – n-elementowa tablica liczb do posortowania

Wynik:

tab – posortowana niemalejąco tablica n liczb

1:dla i = 2,3,4....n wykonuj
2:	pom = tab[i]
3:	j = i-1
4:	dopóki j >= 1 oraz tab[j] > pom wykonuj
5:		tab[j + 1] = tab[j]
6:		j = j - 1
7:	tab[j + 1] = pom

R191ZEFMEK29R

Ćwiczenie 6

Dla zainteresowanych.

Napisz wersję algorytmu sortowania przez wstawianie, która będzie korzystała z rekurencji. Wynikowa lista powinna być posortowana w kolejności niemalejącej. Funkcja ma sortować wejściową listę w miejscu. Program przetestuj dla danych:

liczby = [4, -5, 7, 1, 3, 2, -7, 5, 5, 8, 9, 15, 22, 4, -3, 5, 7]
n = 17

Specyfikacja problemu:

Dane:

liczby – lista liczb całkowitych
n – liczba elementów w liście; liczba naturalna

Wynik:

Program na standardowe wyjście wypisuje posortowaną niemalejąco listę liczb.

RdWvjBJD5UKeC

liczby = [4, -5, 7, 1, 3, 2, -7, 5, 5, 8, 9, 15, 22, 4, -3, 5, 7]
n = 17

def sortuj_rekurencyjnie(liczby, obecny_indeks):
	if obecny_indeks < 1:
		return

	sortuj_rekurencyjnie(liczby, obecny_indeks - 1)

	a = liczby[obecny_indeks]
	b = obecny_indeks - 1

	while b >= 0 and liczby[b] > a:
		liczby[b + 1] = liczby[b]
		b -= 1

	liczby[b + 1] = a

sortuj_rekurencyjnie(liczby, n - 1)
print(liczby)

Plik z programem do pobrania:

R13VHS33OS8LP

Przycisk do pobrania pliku TXT z programem.

Plik TXT o rozmiarze 418.00 B w języku polskim

Implementacja algorytmu