comment implémenter un algorithme de sorting rapide en C ++

Votre considération est fausse. La valeur de r ne change pas, car elle est donnée comme valeur à la fonction Quicksort (pas une référence). Vous manipulez les plages avec p , q telles que p soit le premier index de la plage et q le premier index qui n’est pas dans la plage.

Ainsi, vos appels étaient faux:

 r=partition(A, p,q); quickSort(A,p,r); //range is from A[p] to A[r-1] quickSort(A,(r+1),q); //range is from A[r+1] to A[q-1] 

Voici l’exemple complet. J’ai utilisé std :: swap pour changer les éléments et ans std :: vector au lieu d’un tableau.

 #include  #include  using namespace std; void quickSort(vector&,int,int); int partition(vector&, int,int); int main() { vector A = {6,10,13,5,8,3,2,25,4,11}; int p=0; int q=10; cout<<"======Original======="<& A, int p,int q) { int r; if(p& A, int p,int q) { int x= A[p]; int i=p; int j; for(j=p+1; j 

Exemple vivant: ideone

Ceci est une solution basée sur un modèle. Cependant, cela ne fonctionne que pour les tableaux d’éléments pour l’instant. Si quelqu’un a une amélioration pour le rendre générique à la fois pour les tableaux et les conteneurs STL, veuillez le faire.

 template> void q_sort(T input[], int l_idx, int r_idx, compare comp = compare()) { if (l_idx >= r_idx) return; // The below is the partition block (can be made a sub function) int left = l_idx; int right = r_idx; { int pivot_idx = l_idx; T pivot = input[pivot_idx]; while (left < right) { while (comp(input[left], pivot)) left++; while (comp(pivot, input[right])) right--; swap(input[left], input[right]); } swap(pivot, input[left]); } q_sort(input, l_idx, left, comp); q_sort(input, left+1, r_idx, comp); } template> void quick_sort(T array[], int N, compare comp = compare()) { // This is an improvisation on the merge sort algorithm // is in-place and works on the divide-and-conquer methodology // Choose a pivot and find its appropriate place, such that // All elements less than the pivot are on its left and all elements // greater are on its right. Once found, split the porlblem into subsets // of elements less than and greater than the pivot and recursively // follow the process. q_sort(array, 0, N-1, comp); } int main() { int input[] = {11, 6, 3, 21, 9, 12}; std::cout << "Before : "; for (int i=0; i < 6; i++) std::cout << input[i] << " "; std::cout << std::endl; quick_sort(input, 6); // or //quick_sort(input, 6, std::greater()); std::cout << "After : "; for (int i=0; i < 6; i++) std::cout << input[i] << " "; std::cout << std::endl; } 

Une implémentation beaucoup plus simple et propre, vous donne également le nombre de SWAP minimum dans QuickSort:

 int quickSort(int[], int, int); int partition(int[], int, int, int&); int main() { int array[] = {4, 2, 5}; int size = sizeof(array)/sizeof(array[0]); /* first and last indices are passed idea is to move lower elements to the left of the list/pivot */ int swaps = quickSort(array, 0, size-1); std::cout << "Minimum Swaps are: " << swaps << std::endl; for(int i = 0; i < size; i++) { std::cout << array[i] << " "; } } int quickSort(int array[], int start, int end) { int swaps = 0; if(start < end) { int pIndex = partition(array, start, end, swaps); //after each call one number(the PIVOT) will be at its final position swaps += quickSort(array, start, pIndex-1); swaps += quickSort(array, pIndex+1, end); } return swaps; } int partition(int array[], int start, int end, int& swaps) { int pivot = array[end]; int pIndex = start; for(int i = start; i < end; i++) { if(array[i] <= pivot) { if(pIndex != i) { std::swap(array[i], array[pIndex]); swaps++; } pIndex++; } } if(pIndex != end) { std::swap(array[pIndex], array[end]); swaps++; } return pIndex; } 

Puisque je vois différentes réponses, vous pouvez essayer ceci:

 #include  void quickSort(int a[], int first, int last); int pivot(int a[], int first, int last); void swap(int& a, int& b); void swapNoTemp(int& a, int& b); void print(int array[], const int& N); using namespace std; int main() { int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 }; int N = sizeof(test)/sizeof(int); cout << "Size of test array :" << N << endl; cout << "Before sorting : " << endl; print(test, N); quickSort(test, 0, N-1); cout << endl << endl << "After sorting : " << endl; print(test, N); return 0; } /** * Quicksort. * @param a - The array to be sorted. * @param first - The start of the sequence to be sorted. * @param last - The end of the sequence to be sorted. */ void quickSort( int a[], int first, int last ) { int pivotElement; if(first < last) { pivotElement = pivot(a, first, last); quickSort(a, first, pivotElement-1); quickSort(a, pivotElement+1, last); } } /** * Find and return the index of pivot element. * @param a - The array. * @param first - The start of the sequence. * @param last - The end of the sequence. * @return - the pivot element */ int pivot(int a[], int first, int last) { int p = first; int pivotElement = a[first]; for(int i = first+1 ; i <= last ; i++) { /* If you want to sort the list in the other order, change "<=" to ">" */ if(a[i] <= pivotElement) { p++; swap(a[i], a[p]); } } swap(a[p], a[first]); return p; } 

Je l'ai dans Quicksort (C ++) .