Czy napisałem bubblesorta czy insertsorta?
Ostatnio zmodyfikowano 2015-11-23 17:55
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: void is( int tab[], int n )
{
for( int i = 1; i < n; i++ )
{
if( tab[ i ] < tab[ i - 1 ] )
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: 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: 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: 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;
}
}
}
} |
|
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ć. |
|
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.
|
|
| « 1 » |