ASD_4.pdf

(227 KB) Pobierz
ASD - laboratorium 4. Porównanie algorytmów sortowania prostego.
Zadanie na zaliczenie: przedstawić 2 tabelę porównujące trzy algorytmy sortowania prostego:
Przy n=30 / liczba porównań / liczba przypisań
Algorytm sortowania
Posortowany ciąg
Losowy ciąg
Odwrotnie posortowany ciąg
Zamiany (bąbelkowe)
Wybierania
Wstawiania
Przy n=1000
Algorytm sortowania
Posortowany ciąg
Losowy ciąg
Odwrotnie posortowany ciąg
Zamiany (bąbelkowe)
Wybierania
Wstawiania
Przykład liczenia operacji dla metody bąbelkowej:
void bubble_sort(int *tab, int n)
{ int zmiana, i;
int po=0, pr=0;
do {
pr++,
zmiana = 0;
for(pr++, i=1;
po++,
i<=n; i++)
if(po++, tab[i-1]>tab[i])
{
pr+=4;
int tmp=tab[i-1];
tab[i-1] = tab[i];
tab[i] = tmp;
zmiana = 1;
}
} while(po++, zmiana);
}
metoda selection_sort:
void
proste_wybieranie(int t[], int n)
{
int
i,j,k,min;
for(
i=0; i<n-1; i++)
{
k=i;
// pozycja najmniejszego elementu
min=t[i];
// najmniejszy element
for(
j=i+1;j<n;j++)
// pętla wyznaczająca najmniejszy element
if(t[j]<min)
// czy kolejny element tablicy jest mniejszy?
{
k=j;
// pamiętaj pozycję najmniejszego elementu
min=t[j];
// pamiętaj wartość najmniejszego elementu
}
t[k]=t[i];
// wymiana pierwszego z najmniejszym
t[i]=min;
}
}
metoda insertion_sort:
void
proste_wstawianie(int t[],
int
n)
{ int i,j,tmp;
for(i=1;
i<n; i++)
{
j=i;
// elementy 0...i-1 są posortowane
tmp=t[j];
// sortowany element
while((j>0)
&& (t[j-1]>tmp))
{
t[j]=t[j-1];
// przesunięcie w prawo
j--;
// następny element
}
t[j]=tmp;
// wstawienie elementu
}
}

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin