Podstawy Programowania - Ćwiczenia 8

Zasady, Ćw1, Ćw2, Ćw3, Ćw4, Ćw5, Ćw6, Ćw7, Ćw8, Ćw9, Ćw10, Ćw11, Ćw12, Ćw13

Prowadzący: Rafał Witkowski
Temat: Sortowania

Jest wiele różnych sposobów sortowania, o których na tych zajęciach z braku czasu nie będziemy mówić. Najpowszechniej stosowany i za najlepszy uchodzi:

QuickSort

Jest to probabilistyczny algorytm sorotwania liczb, działający w czasie oczekiwanym O(nlogn), ale w czasie pesymistycznym O(n^2).

Zadanie 1

Bardzo ważną umiejętnością każdego informatyka jest umiejętność korzystania z wyrzukiwarek, np. google. bądź książek dla programistów.
Przy takiej pomocy właśnie można rozwiązać zadanie 25.
Aby to zrobić należy znaleźć procedurę do sortowania przy pomocy algorytmu QuickSort (często znanego jako qsort), przypatrzeć się jej wejściu, a następnie zastosować do posortowania danych, co należy zrobić w zadaniu.
Jedynym haczykiem, o którym trzeba pamiętać jest to, że przeciętna procedura qsort sortuje dane od najmniejszej do największej, a w zadaniu tym dane muszą być posortowane odwrotnie - efekt taki można uzyskać przez wypisanie na wyjście tablicy w odwróconej kolejności, od największego do najmniejszego indeksu.

Do rozwiązania zadania można się wesprzeć poniższym kodem, w którym brakuje właśnie definicji procedury Qsort:

//---------------------------------------------------------------------------

#pragma hdrstop
#include <stdio.h>

//---------------------------------------------------------------------------

#pragma argsused

int t[10000];
int n,d,i,q,qq;

int main(int argc, char* argv[])
{
  scanf("%d",&d);
  while (d--)
  {
    scanf("%d",&n);
    for (i=0; i<n; i++) scanf("%d",&t[i]);
    qsort(t);
    for (i=n-1; i>=0; i--) printf("%d ",t[i]);
    printf("\n");
  }
 return 0; 
}

Sortowanie przez zliczanie (sortowanie liniowe)

Najszybszym znanym sposobem sortowania liczb (działającym zawsze dobrze) jest algorytm sortowania liniowego zwany także algorytmem sortowania przez zliczanie. Ma on tylko jedną postawową wadę - można nim sortować jedynie liczby z nie za dużego przedziału. Najlepsze efekty metoda ta daje, kiedy mamy do posortowania dużą liczbę małych liczb.

Algorytm

Mając dane N liczb z zakresu od 1 do k tworzy się tablicę wielkości k. Wpisuje się do niej same 0. Następnie dla każdej z N liczb zwiększa się o 1 wartość tablicy o indeksie równym tej liczbie. Dzięki temu po przejściu przez wszystkie liczby w tablicy mamy pod wartością odpowiedniego indeksu ilość razy występowania danej liczby w ciągu. Jeśli teraz wykonamy pętle:

for (i=0; i<k; i++) 
  for (j=0; j<t[i]; j++) printf("%d ",i);

to na wyjściu pojawi się nam posortowana tablica odpowiednich liczb.

Zadanie 2

Przy pomocy tego algorytmu należy rozwiązać zadanie 151