Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Czy napisałem bubblesorta czy insertsorta?

Ostatnio zmodyfikowano 2015-11-23 17:55
Autor Wiadomość
maciek1o3s
Temat założony przez niniejszego użytkownika
Czy napisałem bubblesorta czy insertsorta?
» 2015-11-21 20:49:19
Opis tych algorytmów jest różny, jednak jak analizuje ich działanie to wydaje mi się że robią to samo.
Insert sort porównuje elementy i daje te najmniejsze od lewej.
Bubble sort porównuje elementy i daje największe do prawej.

Oba porównują wyrazy obok siebie i jeśli jeden jest większy to je zamieniają. W takim razie dlaczego mają inne nazwy?

Napisałem też samemu 2 insertsorty i 1 bubblesort i zastanawiam się czy aby na pewno insertsorty sa insertsortami, a nie bubblesortami. Moglibyście je przeanalizować i wydać werdykt? :)

1-wszy insertsort:
C/C++
void is( int tab[], int n )
{
    for( int i = 1; i < n; i++ )
    {
        if( tab[ i ] < tab[ i - 1 ] ) // to jest warunek na to zeby nie sprawdzac posortowanych ciagow jeszcze raz
        for( int j = i - 1; j >= 0; j-- )
        {
            if( tab[ j ] > tab[ j + 1 ] )
            {
                int x = tab[ j ];
                tab[ j ] = tab[ j + 1 ];
                tab[ j + 1 ] = x;
            }
        }
    }
}

2-gi insertsort:
C/C++
void iso( int tab[], int n )
{
    int temp;
    for( int i = 1; i < n; i++ )
    {
        int x = i;
        for( int j = x - 1; j >= 0; j-- )
        if( tab[ x ] < tab[ j ] )
        {
            int temp = tab[ j ];
            tab[ j ] = tab[ x ];
            tab[ j + 1 ] = temp;
            x--;
        }
    }
}

Książkowy insertsort:
C/C++
void ist( int tab[], int n )
{
    for( int i = 1; i < n; i++ )
    {
        int j = i;
        int temp = tab[ j ];
        while(( j > 0 ) &&( tab[ j - 1 ] > temp ) )
        {
            tab[ j ] = tab[ j - 1 ];
            j--;
        }
        tab[ j ] = temp;
    }
}

No i tutaj bubblesort:
C/C++
void bs( int tab[], int n )
{
    for( int i = 0; i < n; i++ )
    {
        for( int j = 0; j < n - i - 1; j++ )
        {
            if( tab[ j ] > tab[ j + 1 ] )
            {
                int temp = tab[ j ];
                tab[ j ] = tab[ j + 1 ];
                tab[ j + 1 ] = temp;
            }
        }
    }
}
P-140517
Rashmistrz
» 2015-11-23 17:02:26
Nie, nie panie..
Nie wskażę, które są którymi u Ciebie,
gdyż czasu nie mam, ale pokrótce wytłumaczę.

Bubblesort:
Kolejno porównywane są pary
i ewentualnie odpowiednio przestawiane.
(porównywane są 1 z 2, 2 z 3, 3 z 4 itd. (bądź tak od końca) )
Następnie przedział jest zmniejszany
(,bo na końcu znajdzie się spełniające warunek)
i powtarzany od początku.

Insertionsort:
Wstawiamy kolejne elementy do nowej tablicy,
według odpowiedniej kolejności.
Przypomina to bardzo dobieranie kart z talii
i układanie ich w ręce.

Oczywiście każdy da się na swój sposób ulepszyć.
P-140654
bombatom69
» 2015-11-23 17:55:19
Żadna z wersji nie jest ani bs ani is.
Nie chce mi się sprawdzać czy one w ogóle poprawnie sortują ale druga wersja wygląda dość obiecująco - poza tym, że to jakaś "krzyżówka" BS i IS

Kluczowa rzecz, która jest do zrozumienia w budowie prostych algorytmów sortujących to sposób wykonywania zmian.
Bubble zamienia klucze
Insertion przesuwa całe ciągi i zapisuje. Dzięki temu jest oszczędniejszy niż Bubble.
Jest ważna obserwacja, bo w praktyce jest to również jedna z dróg do przyspieszenia BubbleSorta.

P-140656
« 1 »
  Strona 1 z 1