[c] Sortowanie pozycyjne - przyklad

[soku11]

WITAM!
Prosilbym o napisanie jakiegos przykladu z uzyciem sortowania pozycyjnego dla np czegos takiego:

Kod: Zaznacz cały

int tab[4]={100,423,234,987};

Czy trzeba tutaj zamieniac te liczby na ciagi znakow, by porownywac kolejne pozycje?? Jak to dokladnie przestawiac by uzyskac w miare efektywny kod?? POZDRO

[MGT]

1. liczby musisz mieć tej samej długości (zawsze możesz dopisać nieznaczące zera)

2. sortujesz względem kolejnych pozycji, poczynając od końca:

Kod: Zaznacz cały

^ - kolumna analizowana

100     100      100     100
423 -> 423 -> 423 -> 234
234     234      234     423
987     987      987     987
   ^        ^       ^       ^

3. Zarys algorytmu w C:

Kod: Zaznacz cały

sortowanie_pozycyjne(*tablica, n_elementow)
   {
   int i;
   for (i = 0 ; i<n_elementow ; i++) sortowanie_stabilne_wg_i-tej_pozycji();
   }

4. gdzie sortowanie stabilne, to:

stabilne algorytmy sortowania utrzymują kolejność występowania dla elementów o tym samym kluczu (klucz - cecha charakterystyczna dla każdego elementu zbioru, względem której jest dokonywane sortowanie). Oznacza to, że dla każdych elementów R i S o tym samym kluczu, jeśli R wystąpiło przed S to po sortowaniu stabilnym R będzie przed S;

czyli na nasze, jeśli masz np: 62 i potem 68, to po stabilnym sortowaniu wg. cyfry dziesiątek, muszą zostać w tej samej kolejności, jak przed sortowaniem, czyli sortowanie wg. klucza 10^1 nie może zaburzyć sortowanie wg. 10^0, bo inaczej ten algorytm się wyłoży

5. przykłady stabilnych algorytmów sortowania:
- bąbelkowe
- przez wstawianie
- przez scalanie [to bym polecał dla przypadków ogólnych: O(nlogn)]
- przez zliczanie
- kubełkowe

6. nieco więcej tu: i tutaj:

7. mam nadzieję, że cokolwiek pomoże

[soku11]

Nom ogolna zasade znam, jednak chcialbym zobaczyc jakis przyklad, bo tak to narazie nie obczajam jak to posortowac :/ POZDRO

[Undre]

przyklad ? google.pl -> "radix sort c++"