Sortowanie bąbelkowe - udoskonalenia

Question

Cześć 

Jakie udoskonalenia mogę dołożyć do tego algorytmu? Chodzi mi głownie o rozwiązania zmniejszające ilość zamian.

unsigned long long bubbleSortPerf(double *t,int N)
{
    int zamiana;
    unsigned long long licznik=0;
    double schowek;

    do
    {
        zamiana=0;

        for (int i=0; i<N-1; i++)
        {
            if (t[i]>t[i+1])
            {
                zamiana++;
                schowek=t[i];
                t[i]=t[i+1];
                t[i+1]=schowek;
                licznik++;
            }
        }
        N--;

    }
    while(zamiana!=0);

    return licznik;
}

 

Answer 1

Zaimplementowałeś sortowanie bąbelkowe. Jak zmienisz liczbę zamian to będzie to inny algorytm :P Jedyna opcja na optymalizacje liczby zamian to zmiana algorytmu :P. Ale mniemam, że nie o to Ci chodzi.

Comments

Mam za zadanie wykonać algorytm sortowania bąbelkowego z udoskonaleniami. Kilka już zaimplementowałem, ale nie wiem jak można zmniejszyć ilość zamian.

---

To może powiedz jakie juz zaimplementowałeś to zrozumiemy czym dla Ciebie są udoskonalenia, bo RafalS ma rację ;)

---

Sprawdzania czy przy przejściu pętli zaszła zmiana. Jęsli nie to znaczy że tablica jest posortowana. Oraz zmniejszanie sprawdzanego zakresu tablicy. Takie dodałem udoskonalenia. Jeśli jednak muszę zmienić algorytm to na jaki aby dalej sortował przez "zamiany".

---

Zmniejszenie sprawdzanego zakresu to nie optymalizacja :P Tak jest zdefiniowany algorytm sortowania bąbelkowego. Natomiast sprawdzenie czy nic nie zmieniliśmy czasem się uwzględnia czasem nie, więc można je uznać za optymalizacje.

Tak czy siak myślę, że nie znajdziesz więcej optymalizacji tego algorytmu z racji, że setki tysięcy programistów już nad nim myślało i nie dodali nic nowego do sortowania bąbelkowego :P

---

Czyli nie ma żadnego sposobu na zmniejszenie ilości zamian?

---

Ja myślę, że nie ma, ale ie czuję się na tyle kompetentny, żeby stwierdzić, że na pewno się nie da. Z ciekawości powiem, że dwóch matematyków spędziło połowe życia, żeby udowodnić, że nie da się wyznaczyć wzorów analitycznych na pierwiastki równania 5 i wyższych stopni :D