void bubbleSort(int tab[], int n){
    int porownanie=0,podstawienie=0;
    for (int i=0;i<n;i++){
        podstawienie++;
        for (int j=0;j<n-1;j++){
            podstawienie++;
            if (tab[j]>tab[j+1]){
                porownanie++;
                int temp=tab[j];
                podstawienie++;
                tab[j]=tab[j+1];
                podstawienie++;
                tab[j+1]=temp;
                podstawienie++;
            }
        }
    }
} O(n^2)

void insertionSort(int tab[], int n){
    int porownanie=0, podstawienie=0;
    for (int i=0;i<n;i++){
        podstawienie++;
        int klucz=tab[i];
        podstawienie++;
        int j=i-1;
        podstawienie++;
        while ((j>=0) && (tab[j]>klucz)){
            porownanie=porownanie+2;
            tab[j+1]=tab[j];
            podstawienie++;
            j--;
            podstawienie++;
        }
        tab[j+1]=klucz;
        podstawienie++;
    }
} O(n^2)

void shellSort(int tab[], int n){
    int porownanie=0, podstawienie=0;
    for (int odstep=n/2;odstep>0;odstep/=2){
        podstawienie++;
        for (int i=odstep; i<n;i++){
            podstawienie++;
            int temp=tab[i];
            podstawienie++;
            for(int j=i;j>=odstep && tab[j-odstep]>temp;j=j-odstep){
                podstawienie++;
                porownanie=porownanie+2;
                tab[j]=tab[j-odstep];
                podstawienie++;
                tab[j]=temp;
                podstawienie++;
            }
        }
    }
} O(n^2)

int qpodstawienie=0,qporownanie=0;
int partition (int tab[],int lo,int hi){
    int pivot=tab[hi];
    qpodstawienie++;
    int i=lo-1;
    qpodstawienie++;
    int temp1,temp2;
    for (int j=lo;j<hi;j++){
        qpodstawienie++;
        if (tab[j]<=pivot){
            qporownanie++;
            i++;
            temp1=tab[j];
            tab[j]=tab[i];
            tab[i]=temp1;
            qpodstawienie=qpodstawienie+4;
        }
    }
    temp2=tab[i+1];
    tab[i+1]=tab[hi];
    tab[hi]=temp2;
    qpodstawienie=qpodstawienie+3;
    return (i+1);
}

void quickSort(int tab[],int lo, int hi){
    if (lo<hi){
        int pi=partition(tab,lo,hi);    //partition index
        qpodstawienie++;
        quickSort(tab,lo,pi-1);
        quickSort(tab,pi+1,hi);
    }
} O(nlogn)

void heapify(int tab[], int n, int i) {
    int largest=i;
    int l=2*i+1;
    int r=2*i+2;

    if (l<n&&tab[l]>tab[largest]){
        largest=l;
    }

    if (r<n&&tab[r]>tab[largest]){
        largest=r;
    }

    if (largest!=i){
        int temp=tab[i];
        tab[i]=tab[largest];
        tab[largest]=temp;
        heapify(tab, n, largest);
    }
}

void heapSort(int tab[],int n){
    for (int i=n/2-1;i>=0;i--){
        heapify(tab,n,i);
    }
    for (int i=n-1;i>=0;i--){
        int temp=tab[0];
        tab[0]=tab[i];
        tab[i]=temp;
        heapify(tab,i,0);
    }
} O(nlogn)

void countingSort(int tab[], int n, int k){
    int tabpom[k];
    for (int i=0;i<k;i++){
        tabpom[i]=0;
    }
    for (int i=0;i<n;i++){
        tabpom[tab[i]]++;
    }
    int m=0;
    for (int i=0;i<k;i++){
        for (int j=0;j<tabpom[i];j++){
            tab[m]=i;
            m++;
        }
    }
} O(n)

Tworzenie macierzy sąsiedztwa dla drzewa (globalna macierz M[n][n] jest pierwotnie wyzerowana)

void tworz(wsk T){
   if (T!=NULL){
      if (T->l!=NULL){
          M[T->x][T->l->x]=1;
          tworz(T->l);
      }
      if (T->p!=NULL){
          M[T->x][T->p->x]=1;
          tworz(T->p);
      }
}

Porównanie metod sortowania - wstawianie w tablicy i wstawianie do listy dynamicznej

W obydwu przypadkach liczba porównań jest w pesymistycznym przypadku rzędu O(n^2),
natomiast liczba podstawień - O(n^2) w tablicy oraz O(n) w liście.

Odpowiedz: 1 - drzewo zdegenerowane, 0 - w przeciwnym razie

int degen(wsk T){
   if (T==NULL){return 1;}
   if ((T->l!=NULL)&&(T->p!=NULL)) {return 0;}
   return (T->l!=NULL) ? degen(T->l) : degen(T->p);
}