[WikiDyd] [TitleIndex] [WordIndex

Na zajęciach wymagana jest znajomość czterech algorytmów sortujących. W trakcie ćwiczenia będzie należało napisać program testujący oraz przedstawić wyniki testów zebrane w tabeli.

1. Sortowanie przez wstawianie (kod był podawany na zajęciach 3.)

2. Sortowanie stogowe (przez kopcowanie). (Ciekawa animacja ilustrujaca działanie algorytmu: tutaj)

3. Sortowanie szybkie qsort.

4. Sortowanie bąbelkowe.

Zaprezentowane przykłady używają typów generycznych, tzn. , że algorytmy sortujące dostosowują się do odpowiedniego typu danych w momencie ich wykorzystania. Oznacza to, że algorytmy sortujące są napisane na tyle uniwersalnie, że mogą sortować dowolne typy danych pod warunkiem dostarczenia specjalnej funkcji porównującej.

Przykładowe zadania

Ze względu na większą złożoność zadań na zajęciach do wykonania będą co najwyżej 3 wybrane przez prowadzącego zadania. Jeżeli któreś zadanie jest dla państwa niejasno sfomułowane bardzo proszę nie krępować się i zadać pytanie na konsultacjach lub e-mailem (robert [a z ogonkiem] iem.pw.edu.pl).

1. Proszę napisać program, który będzie umożliwiał posortowanie listy studentów malejąco względem oceny którą otrzymali. Proszę założyć, że lista zbudowana jest za pomocą tablicy przechowującej klasy Student zdefiniowane w poniższym fragmencie kodu. Do sortowania wykorzystać wskazany przez prowadzącego algorytm.

class Student {
   public String imie;
   public String nazwisko;
   public int grupa;
   public double ocena;
}

3. Proszę znaleźć i poprawić błąd (zrobiony specjalnie) w udostępnionym przez prowadzącego kodzie algorytmu sortowania (bąbelkowe, qsort, insort lub heapsort).

4. Proszę zbudować program badający czas sortowania przypadkowych danych przez algorytmy: bąbelkowy, stogowy oraz qsort. Testy proszę wykonać dla rozmiaru danych rosnącego wykładniczo. (10, 100, 1000, 10000, itd.).

5. Proszę napisać program który posortuje alfabetycznie wszystkie linie znajdujące się we wskazanym pliku. Wynik sortowania powinien być zapisany do innego pliku. Proszę wykorzystać przykład kopiujący pliki z zajęć 3.

6. Napisz program scalający dwie tablice liczb o podwójnej precyzji a następnie je sortujący i wyświetlajacy wynik na ekranie.

7. Napisz program wyświetlający na ekranie posortowaną alfabetycznie listę studentów, którzy zaliczyli egzamin. Przyjmij, że minimalna oceną zaliczenia jest ocena 3. Do sortowania wykorzystaj wskazany przez prowadzącego algorytm sortujący.

8. Zakładając, że posiadamy tablicę krawędzi wierzchołków, gdzie, każda krawędź przechowuje indeksy wierzchołków reprezentowane za pomocą liczb całkowitych, posortuj tę tablicę względem indeksów wierzchołków. Załóż, że krawędź jest reprezentowana przez klasę:

class Edge {
  public int edgeId;
  public int w1;
  public int w2;
}

Przyjmij, że wierzchołek e1 jest większy od wierzchołka e2 wtedy gdy: (e1.w1 > e2.w1) lub (e1.w1 == e2.w1 i e1.w2 > e2.w2).

9. Zakładając tablicę krawędzi opisaną w punkcie 9. proszę posortować krawędzie rosnąco pod względem różnicy między indeksami wierzchołków danej krawędzi: roznica = (e1.w2 - e1.w1).


2015-09-23 06:32