1
J'écris un programme qui compte les opérations de mergesort et de quicksort. Je ne sais pas où je devrais mettre le compte ++; (pour compter les opérations) dans. Quelqu'un peut-il m'aider avec ceci?comment compter les opérations de mergesort et quicksort en Java?
Voici les codes pour le tri par fusion et le tri rapide.
MERGE SORT:
public void mergeSort(int [] data, int first, int n){
int n1;
int n2;
if (n>1) {
n1 = n/2;
n2 = n-n1;
mergeSort(data,first,n1);
mergeSort(data,first+n1,n2);
merge(data,first,n1,n2);
}
}//ends mergeSort method.
public void merge(int [] data, int first, int n1, int n2){
int [] temp = new int[n1+n2];
int copied = 0, copied1 = 0, copied2 = 0, i;
while((copied1<n1) && (copied2<n2)){
if(data[first+copied1] < data[first + n1 + copied2])
temp[copied++] = data[first + (copied1++)];
else
temp[copied++] = data[first + n1 + (copied2++)];
}
while (copied1<n1)
temp[copied++] = data[first + (copied1++)];
while(copied2<n2)
temp[copied++] = data[first + n1 + (copied2++)];
for (i=0;i<n1+n2;i++)
data[first+i] = temp[i];
}//ends merge method.
Et voici le code pour SORT RAPIDE:
public void quickSort(int data[], int left, int right){
int index = partition(data, left, right);
if (left < index - 1){
quickSort(data, left, index - 1);
}
if (index < right){
quickSort(data, index, right);
}
}//ends quickSort method.
int partition(int data[], int left, int right){
int i = left, j = right;
int tmp;
int pivot = data[(left + right)/2];
while (i <= j)
{
while (data[i] < pivot)
i++;
while (data[j] > pivot)
j--;
if (i <= j)
{
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
i++;
j--;
}
}
return i;
}//ends partition method.