Metody sortowania prostego - 2h
Cele ogólne
Uczeń:
planuje kolejne kroki rozwiązywania problemu, z uwzględnieniem podstawowych etapów myślenia komputacyjnego (określenie problemu, definicja modeli i pojęć, znalezienie rozwiązania, zaprogramowanie i testowanie rozwiązania) (I.1),
stosuje przy rozwiązywaniu problemów z różnych dziedzin algorytmy poznane w szkole podstawowej (I.2),
stosuje przy rozwiązywaniu problemów z różnych dziedzin algorytmy porządkowania ciągu liczb: przez wstawianie i metodą bąbelkową (I.2c), sprawdza poprawność działania algorytmów dla przykładowych danych (I.5),
projektuje i programuje rozwiązania problemów z różnych dziedzin, stosuje przy tym: instrukcje wejścia/wyjścia, wyrażenia arytmetyczne i logiczne, instrukcje warunkowe, instrukcje iteracyjne, funkcje z parametrami i bez parametrów, testuje poprawność programów dla różnych danych; w szczególności programuje algorytm z punktu I.2 (II.1),
w zależności od problemu rozwiązuje go, stosując metodę wstępującą lub zstępującą (RI.1),
objaśnia dobrany algorytm, uzasadnia poprawność rozwiązania na wybranych przykładach danych i ocenia jego efektywność (RI.3),
ilustruje i wyjaśnia rolę pojęć, obiektów i operacji matematycznych w projektowaniu rozwiązań problemów informatycznych i z innych dziedzin, posługuje się pojęciem logarytmu (RI.4),
dyskutuje na temat roli myślenia komputacyjnego i jego metod, takich jak: abstrakcja, reprezentacja danych, dekompozycja problemu, redukcja, myślenie rekurencyjne, podejście heurystyczne w rozwiązywaniu problemów z różnych dziedzin (RI.8),
stosuje zasady programowania strukturalnego i obiektowego w rozwiązywaniu problemów (RII.2),
sprawnie posługuje się zintegrowanym środowiskiem programistycznym przy pisaniu, uruchamianiu i testowaniu programów (RII.3),
zapisuje za pomocą listy kroków, schematu blokowego lub pseudokodu i implementuje w wybranym języku programowania algorytmy poznane na wcześniejszych etapach (RI+II.1),
objaśnia, a także porównuje podstawowe metody i techniki algorytmiczne oraz struktury danych, wykorzystując przy tym przykłady problemów i algorytmów, w szczególności: wyszukiwanie elementów liniowe i przez połowienie (do znajdowania elementów w zbiorze, sortowania przez wstawianie, przybliżonego rozwiązywania równań, sprawdzania przynależności punktu do wielokąta wypukłego) (RI+II.3a).
definiuje pojęcia: sortowanie, operacja dominująca.
wyjaśnia, czym jest sortowanie bąbelkowe, sortowanie przez wstawianie, sortowanie przez wybieranie.
stosuje algorytmy sortowania prostego.
szacuje czasową złożoność obliczeniową algorytmów sortowania prostego.
rozróżnia algorytmy sortowania prostego.
tworzy i wywołuje funkcje w języku C++ implementujące algorytmy sortowania prostego.
Przydatne narzędzia/oprogramowanie
Problem sortowania
Algorytm sortowania bąbelkowego
Zapis algorytmu porządkującego elementy tablicy niemalejąco metodą sortowania bąbelkowego
dla i <--1, 2, ..., n-1 wykonuj dla j <-- 0, 1, 2, ..., n-i-1 wykonuj jeśli A[j] > A[j+1] to pom <-- A[j] A[j] <-- A[j+1] A[j+1] <-- pom
Sortowanie przez wybieranie
dla i <- 0, 1, 2, ... , n-2 wykonuj m <- i dla j <- i+1, i+2, .. , n-1 wykonuj jeśli A[j] > A[m] to m <- j pom <- A[i] A[i] <- A[m] A[m] <- pom
Załóżmy że chcemy posortować liczby: 6, 4, 9, 1, 5
Sortowanie przez wstawianie
Porównanie metod sortowania
Ćwiczenie 1 - napisz program sortujący niemalejąco tablicę liczb całkowitych algorytmem sortowania bąbelkowegp
Ćwiczenie 2 - sortowanie przez wybieranie
Napisz program sortujący niemalejąco tablicę liczb całkowitych algorytmem sortowania przez wybieranie
Ćwiczenie 3 - napisz program sortujący niemalejąco tablicę liczb całkowitych algorytmem sortowania przez wstawianie
Programy w C++ - zadania
1. Napisz program, który uporządkuje liczby w tablicy tak, aby pierwszym elementem tablicy była liczba z najmniejszą cyfrą jedności, a ostatnim - liczba z największą cyfrą jedności. Jeśli dwie Iiczby mają taką samą cyfrę jedności, uznajemy je za równe.
2. Napisz program, który posortuje niemalejąco tablicę liczb całkowitych. ]ako pierwszy powinien zostać wyznaczony ostatni element tablicy, następnie przedostatni itd. Podczas rozwiązywania zadania skorzystaj z algorytmu sortowania przez wybieranie.
3. Zmodyfikuj omówiony w temacie program realizujący algorytm sortowania bąbelkowego tak, aby sprawdzał, czy w danej iteracji wewnętrznej pętli dowolne z elementów zostały zamienione miejscami. Algorytm powinien kończyć działanie, jeżeli w danej iteracji nie było ani jednej zamiany elementów.
4. Napisz program sortujący liczby całkowite nieujemne według sumy ich cyfr: na pierwszym miejscu powinna się znaleźć liczba, której suma cyfr jest najmniejsza.
5. Napisz program sortujący liczby całkowite nieujemne według liczby jedynek w ich zapisie binarnym: na pierwszym miejscu powinna się znaleźć się liczba z największą liczbą jedynek w zapisie binarnym.
6. Napisz program porządkujący liczby w tablicy tak, aby na pierwszym miejscu znalazły się w niej liczby nieparzyste, a potem iczby parzyste.
7. Napisz program, który uporządkuje niemalejąco tablicę liczb, wykorzystując algorytm sortowania przez wstawianie. Miejsce do wstawienia elementu program powinien znajdować metodą przeszukiwania binarnego (jakie to przeszukiwanie?).
Uwaga: Przesunięcie elementów nadal będzie liniowe.
8. Napisz program, który uporządkuje liczby całkowite w tablicy tak, aby pierwszym elementem tablicy byłą liczba z najmniejszą cyfrą jedności, a ostatnim - liczba z największą cyfrą jedności. Jeśli dwie liczby mają taką samą cyfrę jedności, uznaj jewz za róne. Rozwiąż zadanie tak, aby złożonośc czasowa algorytmu była nie większa niż 10n.
9. Napisz program losujący tablicę liczb całkowitych z zakresu od 2 do 1000 oraz sortujący je według najmniejszego czynnika pierwszego. Najpierw w tablicy powinny znaleźć się liczby podzielne przez 2, potem podzielne przez 3 (a niepodzielne przez 2), następnie podzielne przez 5 (a niepodzielne przez 2 i 3) itd. )
Test wiedzy
|
Pytanie 1.
Podsumowanie
Sortowanle bąbelkowe (przez prostą zamianę) polega na porównywaniu sąsiednich elementów ciągu i ewentualnej ich zamianie tak, aby spełniały relację porządkującą.
W sortowaniu przez wybieranie w kolejnych krokach znajduje się najmniejszy element sortowanego ciągu i przenosi ten element na odpowiednią pozycję ciągu wynikowego (przez zamianę elementów miejscami).
Sortowanie przez wstawianie polega na wstawianiu kolejnych elementów porządkowanego ciągu w już uporządkowany fragment ciągu.
Dla algorytmów sortowania prostego operacją dominującą jest porównywanie elementów.
Dla algorytmów sortowania prostego czasowa zlożoność obliczeniowa (zarówno oczekiwana, jak i pesymistyczna) jest kwadratowa O(n2).
Przykładowe rozwiązania oraz komentarze do wybranych ćwiczeń i zadań