Strefa wyzwań - I_P_W14_M10 Sortowanie przez wybieranie

R13FDE7ADF7DU

Już wiesz

Na czym polega metoda sortownia przez wybieranie.
Jak wygląda algorytm sortowania tą metodą zapisany za pomocą pseudokodu.
Jak zaimplementować algorytm sortowania przez wybieranie w języku Python.

Teraz czas na sprawdzenie swojej wiedzy i umiejętności w praktyce.

ROVJ1HFAUXN4B

Ćwiczenie 1

RQF5VMXVZV8LB

Ćwiczenie 2

Ćwiczenie 3

Napisz program, który wykorzystując sortowanie przez wybieranie, poda x najmniejszych liczb z n-elementowej tablicy liczb naturalnych dane. Swój program przetestuj dla następujących danych:

n = 17
dane = [696, 587, 501, 811, 162, 980, 18, 207, 638, 49, 329, 316, 305, 406, 25, 16, 542]
x = 5

Specyfikacja problemu:

Dane:

n – liczba elementów tablicy dane; liczba naturalna
dane – n-elementowa tablica liczb naturalnych
x – liczba najmniejszych liczb z tablicy dane, które program powinien wypisać; liczba naturalna; $x \leq n$ .

Wynik:

Program wypisuje x najmniejszych liczb z n-elementowej tablicy dane. Liczby powinny być wypisane w jednej linii i oddzielone znakiem spacji.

RLACBZ83XXR1N1

Przykładowe rozwiązanie zadania:

Linia 1. def znajdz podkreślnik indeks podkreślnik minimum otwórz nawias okrągły n przecinek dane przecinek i zamknij nawias okrągły dwukropek. Linia 2. indeks podkreślnik najmniejszego podkreślnik elementu znak równości i. Linia 4. for j in range otwórz nawias okrągły i plus 1 przecinek n zamknij nawias okrągły dwukropek. Linia 5. if dane otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny dane otwórz nawias kwadratowy indeks podkreślnik najmniejszego podkreślnik elementu zamknij nawias kwadratowy dwukropek. Linia 6. indeks podkreślnik najmniejszego podkreślnik elementu znak równości j. Linia 8. return indeks podkreślnik najmniejszego podkreślnik elementu. Linia 10. def zamien otwórz nawias okrągły dane przecinek a przecinek b zamknij nawias okrągły dwukropek. Linia 11. tmp znak równości dane otwórz nawias kwadratowy a zamknij nawias kwadratowy. Linia 12. dane otwórz nawias kwadratowy a zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy b zamknij nawias kwadratowy. Linia 13. dane otwórz nawias kwadratowy b zamknij nawias kwadratowy znak równości tmp. Linia 15. def sortowanie podkreślnik wybieranie otwórz nawias okrągły x przecinek n przecinek dane zamknij nawias okrągły dwukropek. Linia 16. for i in range otwórz nawias okrągły 0 przecinek x zamknij nawias okrągły dwukropek. Linia 17. indeks znak równości znajdz podkreślnik indeks podkreślnik minimum otwórz nawias okrągły n przecinek dane przecinek i zamknij nawias okrągły. Linia 18. zamien otwórz nawias okrągły dane przecinek i przecinek indeks zamknij nawias okrągły. Linia 20. n znak równości 17. Linia 21. dane znak równości otwórz nawias kwadratowy 696 przecinek 587 przecinek 501 przecinek 811 przecinek 162 przecinek 980 przecinek 18 przecinek 207 przecinek 638 przecinek 49 przecinek 329 przecinek 316 przecinek 305 przecinek 406 przecinek 25 przecinek 16 przecinek 542 zamknij nawias kwadratowy. Linia 22. x znak równości 5. Linia 24. sortowanie podkreślnik wybieranie otwórz nawias okrągły x przecinek n przecinek dane zamknij nawias okrągły. Linia 26. for i in range otwórz nawias okrągły x zamknij nawias okrągły dwukropek. Linia 27. print otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły.

def znajdz_indeks_minimum(n, dane, i):
	indeks_najmniejszego_elementu = i

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

	return indeks_najmniejszego_elementu

def zamien(dane, a, b):
	tmp = dane[a]
	dane[a] = dane[b]
	dane[b] = tmp

def sortowanie_wybieranie(x,n, dane):
	for i in range(0, x):
		indeks = znajdz_indeks_minimum(n, dane, i)
		zamien(dane, i, indeks)

n = 17
dane = [696, 587, 501, 811, 162, 980, 18, 207, 638, 49, 329, 316, 305, 406, 25, 16, 542]
x = 5

sortowanie_wybieranie(x, n, dane)

for i in range(x):
	print(dane[i], end=" ")

Plik z programem do pobrania:

R168EDJPA8BXV

Przycisk do pobrania pliku TXT z programem.

Plik TXT o rozmiarze 647.00 B w języku polskim

Implementacja algorytmu

I_P_W14_M10 Sortowanie przez wybieranie