PRI, laboratorium 5

Zakres materiału: Proste algorytmy sortowania (sortowanie bąbelkowe, sortowanie przez wstawianie). (5 pkt)

Zadanie 1. Analiza prostych algorytmów sortowania.

1. W katalogu prm5 utworzyć nowy projekt zad1 i do głównego pliku projektu skopiować zawartość pliku źródłowego lab5.c
2. Zapoznać się z działaniem obydwu algortymów sortowania (funkcje babelki i wstawianie). Polecam filmy na youtube.
3. Ile porownań musi wykonać każdy z algorytmów sortowania dla 4 elementowego ciągu odwróconego (np. 10,5,3,1) i już posortowanego (np. 1, 3, 5, 10)?
4. Jaka wartość znajdzie się na końcu tablicy tablica po pierwszej iteracji pętli while z linii 17-34? Czy ta obserwacja może pozwalić na przyspieszenie algorytmu?
5. Dlaczego w linii 50 najpierw sprawdzany jest warunek na zmienną j, a następnie dopiero jest wywoływana funkcja porownaj?
6. Jak inaczej można zapisać instrukcję z linii 73? Podać co najmniej dwa sposoby.
7. Jaka prosta modyfikacja pozwoli zmienić porządek sortowanie obydwy algorytmów z rosnącego na malejący?

Zadanie 2. Modyfikacja algorytmów.

1. W katalogu prm5 utworzyć nowy projekt zad2 i do głównego pliku projektu skopiować zawartość pliku źródłowego z pierwszego zadania.
2. Zmodyfikować program, tak aby umożliwiał sortowanie listy wyrazów w zadanej kolejności. Wskazówki:
   • liste wyrazów zdefiniować w kodzie programu jako tablicę char* nieposortowane[]={"basia", "zosia", "ala", "genowefa"};
   • do porównywania dwóch wyrazów użyć funkcji strcmp, której prototyp jest w pliku nagłówkowym string.h
   • porządek sortowania jest wybierany dodatkowym argumentem int porzadek przekazywanym do funkcji babelki i wstawianie: jeżeli porzadek>=0 to sortowanie jest w porzadku rosnącym, w przeciwnym przypadku w porządku malejącym
   • zmodyfikować odpowiednio funkcje kopiuj i wypisz, aby przyjmowały jako pierwszy argument tablicę ciągów znakowych

Zadanie 3. Zadanie samodzielne.

Grupa A

1. Napisać i uruchomić program wyznaczający liczbę wystąpień znaków (liter i cyfr) w zdaniu. Liczba wystąpień poszczególnych znaków powinna być następnie wypisana w kolejności malejącej według liczby wystąpień. Przykładowe wyniki działania programu:

   Podaj zdanie: Rabarbar bar Barbar
   Liczba wystapien znakow:
   a 6
   r 6
   b 4
   B 1
   

2. Założenia:
   • długość zdania <50
   • nie używać instrukcji switch!
3. Podpowiedzi:
   • wyrażenie 'c'-'a' ma wartość 2
   • użyć tablicy short int liczba[62] do przechowywania liczby wystapień znaków (62=26+26+10, jest 26 małych i 26 dużych liter w kodzie ASCII, i 10 cyfr)

Grupa B

1. Napisać i program określający sposób uporządkowania zadanego ciągu liczb (malejący, rosnący, nieuporządkowany). Przykładowe wyniki działania programu:

   Podaj liczbę elementów ciągu: 5
   Podaj elementy ciągu:
   1
   2
   3
   6
   9
   Ciag jest uporzadkowany rosnaco.
   Podaj liczbę elementów ciągu: 5
   Podaj elementy ciągu:
   1
   2
   3
   9
   6
   Ciag jest nieuporzadkowany.
   Podaj liczbę elementów ciągu: 3
   Podaj elementy ciągu:
   3
   2
   1
   Ciag jest uporzadkowany malejaco.
   

2. Założenia:
   • długość ciągu <20
3. Podpowiedzi:
   • zmodyfikować algorytm bubble sort