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.
Jak wyznaczać złożoność obliczeniową algorytmu sortowania przez wstawianie.

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

Ćwiczenie 1

R134CK73VPKTH

Ćwiczenie 2

R1465Z6SQ49S7

Ćwiczenie 3

RABA38Z7X3QE1

Ćwiczenie 4

RLQP8RR3DZZ2N

Ćwiczenie 5

R1C9GAFAN9E5M

Ćwiczenie 6

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

R1JCKKFGFAEVM

Ćwiczenie 7

RC195ZOLE1M7V

Ćwiczenie 8

Używając algorytmu sortowania przez wstawianie, napisz program sortujący wyrazy znajdujące się w liście napisy w porządku odwrotnym do alfabetycznego. Swój program przetestuj dla listy:

napisy = ["sortowanie", "python", "lekcja", "matura", "wstawianie"]

Specyfikacja problemu:

Dane:

napisy – lista ciągów znaków

Wynik:

Program na standardowe wyjście wypisuje posortowaną w kolejności odwrotnej do alfabetycznej listę ciągów znaków.

RP68ULKQNFF4A

Ćwiczenie 9

Pewien przedsiębiorca postanowił udostępniać usługę sortowania przez wstawianie na zasadzie komercyjnej. Cenę za posortowanie listy niemalejąco ustalił w następujący sposób: jest to suma liczby przesunięć i opłaty stałej 2,50 zł. Napisz funkcję, która zwróci cenę posortowania podanej listy. Swój program przetestuj dla przygotowanych list testowych:

przypadek_optymistyczny = [1, 4, 8, 9, 12, 14, 15, 17, 27, 32, 35, 45, 99]
przypadek_pesymistyczny = [99, 45, 35, 32, 27, 17, 15, 14, 12, 9, 8, 4, 1]
przypadek_sredni = [14, 32, 35, 45, 12, 8, 17, 15, 99, 1, 27, 4, 9]

Specyfikacja problemu:

Dane:

dane – lista liczb naturalnych do posortowania
n – liczba naturalna; liczba elementów tablicy dane

Wynik:

cena_sortowania – wyliczona cena dla zadanej listy liczb

R1K6QF8NB42SH

Linia 1. def sortowanie podkreślnik przez podkreślnik wstawianie otwórz nawias okrągły dane zamknij nawias okrągły dwukropek. Linia 2. cena podkreślnik sortowania znak równości 2 kropka 5. Linia 3. n znak równości len otwórz nawias okrągły dane zamknij nawias okrągły. Linia 4. for i in range otwórz nawias okrągły 1 przecinek n zamknij nawias okrągły dwukropek. Linia 5. a znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 6. b znak równości i minus 1. Linia 8. while b zamknij nawias ostrokątny znak równości 0 and dane otwórz nawias kwadratowy b zamknij nawias kwadratowy zamknij nawias ostrokątny a dwukropek. Linia 9. dane otwórz nawias kwadratowy b plus 1 zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy b zamknij nawias kwadratowy. Linia 10. b minus znak równości 1. Linia 11. cena podkreślnik sortowania plus znak równości 1. Linia 12. dane otwórz nawias kwadratowy b plus 1 zamknij nawias kwadratowy znak równości a. Linia 13. return cena podkreślnik sortowania. Linia 15. przypadek podkreślnik optymistyczny znak równości otwórz nawias kwadratowy 1 przecinek 4 przecinek 8 przecinek 9 przecinek 12 przecinek 14 przecinek 15 przecinek 17 przecinek 27 przecinek 32 przecinek 35 przecinek 45 przecinek 99 zamknij nawias kwadratowy. Linia 16. przypadek podkreślnik pesymistyczny znak równości otwórz nawias kwadratowy 99 przecinek 45 przecinek 35 przecinek 32 przecinek 27 przecinek 17 przecinek 15 przecinek 14 przecinek 12 przecinek 9 przecinek 8 przecinek 4 przecinek 1 zamknij nawias kwadratowy. Linia 17. przypadek podkreślnik sredni znak równości otwórz nawias kwadratowy 14 przecinek 32 przecinek 35 przecinek 45 przecinek 12 przecinek 8 przecinek 17 przecinek 15 przecinek 99 przecinek 1 przecinek 27 przecinek 4 przecinek 9 zamknij nawias kwadratowy. Linia 19. print otwórz nawias okrągły sortowanie podkreślnik przez podkreślnik wstawianie otwórz nawias okrągły przypadek podkreślnik optymistyczny zamknij nawias okrągły zamknij nawias okrągły. Linia 20. print otwórz nawias okrągły sortowanie podkreślnik przez podkreślnik wstawianie otwórz nawias okrągły przypadek podkreślnik pesymistyczny zamknij nawias okrągły zamknij nawias okrągły. Linia 21. print otwórz nawias okrągły sortowanie podkreślnik przez podkreślnik wstawianie otwórz nawias okrągły przypadek podkreślnik sredni zamknij nawias okrągły zamknij nawias okrągły.

def sortowanie_przez_wstawianie(dane):
	cena_sortowania = 2.5
	n = len(dane)
	for i in range(1, n):
		a = dane[i]
		b = i - 1

		while b >= 0 and dane[b] > a:
			dane[b + 1] = dane[b]
			b -= 1
			cena_sortowania += 1
		dane[b + 1] = a
	return cena_sortowania

przypadek_optymistyczny = [1, 4, 8, 9, 12, 14, 15, 17, 27, 32, 35, 45, 99]
przypadek_pesymistyczny = [99, 45, 35, 32, 27, 17, 15, 14, 12, 9, 8, 4, 1]
przypadek_sredni = [14, 32, 35, 45, 12, 8, 17, 15, 99, 1, 27, 4, 9]

print(sortowanie_przez_wstawianie(przypadek_optymistyczny))
print(sortowanie_przez_wstawianie(przypadek_pesymistyczny))
print(sortowanie_przez_wstawianie(przypadek_sredni))

Ćwiczenie 10

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.

R4LA2X7MNBBNQ

Implementacja algorytmu