eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingsortowanieRe: sortowanie
  • Data: 2012-10-14 00:18:59
    Temat: Re: sortowanie
    Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
    [ pokaż wszystkie nagłówki ]

    W dniu 2012-10-13 20:06, Edek Pienkowski pisze:
    > Dnia Sat, 13 Oct 2012 10:50:01 -0700, kenobi napisal:
    >
    >>>
    >>> No to już brzmi fajnie. A co to było to C, która wartość to ma być?
    >>>
    >>> Poza tym, czy swapów nie miało być jak najmniej?
    >>>
    >>>
    >> C to dowolna wartosc z tablicy najlepiej gdyby to byla taka ktora podzieli
    >> tablice na dwa zblizone wielkoscia kawalki, mozna wylosowac dowolna np ze
    >> srodka przedzialu, wazne tylko by nie miec wielkiego pecha w wielce
    >> dlugiej serii - bo wtedy stos sie wywali - ale taki pech jest malo
    >> prawdopodobny
    >
    > Dowolna, czy się ją jakoś wybiera? Nie można robiąc te swapy na lewo
    > i prawo policzyć sobie średniej przy okazji?


    Oj, to wyższa filozofia;)

    Można wybierać z prawej, z lewej, ze środka,
    losowy element, medianę z końców i środka...
    Jak ktoś chce, może zawsze brać element 7
    (o ile tablica odpowiednio duża).


    BTW, algorytm dzielenia proponowany przez fira nie jest najlepszy.
    Raczej się robi to w ten sposób, że jedzie od początku w górę
    jednym indeksem, aż napotka się element za duży. Potem od końca
    w dół drugim indeksem, aż napotka się element za mały
    (mniejszy od elementu dzielącego). następnie zamienia się
    te elementy i wszytko powtarza, póki się indeksy nie spotkają.

    Do testów (i by sprawdzić, ile pamiętam, zajmuję się zupelnie
    innymi rzeczami) machnąłęm coś takiego:

    void qsort(int * tabl,int first, int last)
    {
    if (last-first>1)
    {
    int piv = tabl[first];//element dzielący
    int i=first; //elementow first i last+1
    int j=last+1; //nigdy nie dotkniemy
    do
    {
    do i++; while ((i<=last)&&(tabl[i]<piv));
    do j--; while (tabl[j]>piv); // fajne*)
    if (i<j) {std::swap(tabl[i],tabl[j])}
    }while (i<j);

    tabl[first]=tabl[j];
    tabl[j]=piv;

    qsort_insert(tabl, first, j-1);
    qsort_insert(tabl, j+1, last);
    }
    }

    Dzieki temu odpada jakaś polowa zapisów. W jednym ruchu swapa
    _dwa_ elementy lądują po odpowiednich stronach podziału.

    *) nie musimy sprawdzać zakresu, bo tab[first] go trzyma.
    podobnie, jeśli nasza tablica jest podtablicą taką, że
    tab[first-1] jest mniejsze, a tab[last+1] wieksze od kazdego
    elementu naszej tablicy, nie musimy tego sprawdzać.
    Zerknąłem do stla. Tam z tego korzystają i mają osobne
    procedury dla prawego kranca, lewego, i podtablicy wewnetrz.

    pzdr
    bartekltg



Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: