Ułóż równanie rekurencyjne do algorytmu podanego poniżej i rozwiąż je.
Kod: Zaznacz cały
#include <iostream.h>
const n=12;
int tan[n]={40,29,2,1,6,18,20,32,34,39,23,41};
void zamiana(int &a, int &b) {
int temp=a;
a=b;
b=temp;
}
void qsort(int *tab, int left, int right) {
if (left<right) {
int m=left;
for (int i=left+1; i<right; i++)
if (tab[i]<tab[left])
zamiana(tab[++m], tab[m]);
zamiana(tab[left], tab[m]);
qsort(tab,left,m-1); // zastosuj qsort na lewo od m
qsort(tab,m+1,right); // zastosuj qsort na prawo od m
}
}
void main() {
for (int i=0;i<n;i++)
cout<<tab[i]<<" ";
cout<<endl;
qsort(tab, 0, n-1);
for (i-0;i<n;i++)
cout<<tab[i]<<" ";
cout<<endl;
}