Jaka jest złożoność kodu..

0

W nieposortowanej części tablicy wyszukujemy minimum i wkładamy go na
koniec posortowanej części tablicy (na samym początku na pierwsze miejsce tablicy,
potem na drugie itd.)
Oto co wykodziłem(działa prawidłowo, hyba), a na dole pytanie pod kodem

#include <stdio.h>
#include <stdbool.h>

void selection_sort(int tab[], int n)
{
    n -= 1;
    bool is_smaller = false;
    int i,j,min = tab[n];
    int amount = n, temp, index_small;
    for( i = 0; i < amount; ++i){
        for( j = 0; j < n ; ++j)
        if(tab[j] < min ){
            min = tab[j];
            index_small = j;
            is_smaller = true;
        }
        if(is_smaller == false ){
            --n;
            min = tab[n];
            continue;
        }
        temp = tab[n];
        tab[n] = min;
        tab[index_small] = temp;
        --n;
        min = tab[n];
        is_smaller = false;
    }
}

int main(int argc, char *argv[])
{
    //int n1 = 10;
//  int n2 = 10;
    //int t1[10]={1,2,3,4,4,6,8,10,11,12}, t2[10] = {13,1,33,44,44,65,82,105,122,143};
    //int t3[n1 + n2];
    int tab[10] = {2,4,3,46,8,9,10,1,8,8};

    selection_sort(tab,10);

    int i; for( i=0;i<10;++i)   printf("%d\t",tab[i]);
    return 0;
}

Jaka jest pesymistyczna złożoność sortowania przez wybieranie (rząd maksymalnej ilości
operacji niezbędnej posortowania tablicy) ? Czy ilość kroków wykonywanych przez
algorytm może się zmieniać w zależności od zawartości tablicy T tzn. od tego, czy jest ona
już posortowana, „prawie posortowana” (tzn. bardzo niewiele elementów jest ułożonych
niewłaściwie) czy też jest „mocno nieposortowana”, a w szczególności posortowana
odwrotnie – nierosnąco ? Odpowiedzi napisz na początku kodu programu.
---- chodzi o to żę nie bardzo wiem co mam napisać.....

0

Sortowanie przez wybór, generalnie ma złożoność n^2, jak będziesz miał tablicę już posortowaną malejąco, to wtedy złożonośc będzie najmniejsza, tzn. n; za to najwięcej operacji jest w przypadku, gdy tablica jest posortowana rosnąco - chyba oczywiste.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0