Anonymous user
Sorting algorithms/Quicksort: Difference between revisions
→{{header|C}}
m (Added comment to the pivot() method in the C# sample.) |
|||
Line 969:
void quicksort(int *A, int len);
int main (void) {
int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
int n = sizeof a / sizeof a[0];
int i;
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
Line 983 ⟶ 981:
quicksort(a, n);
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
Line 992 ⟶ 989:
}
void quicksort(int *A, int len) {
if (len < 2) return;
Line 999 ⟶ 995:
int i, j;
for (i = 0, j = len - 1; ; i++, j--) {
while (A[i] < pivot) i++;
while (A[j] > pivot) j--;
Line 1,027 ⟶ 1,022:
#include <stdlib.h> // REQ: rand()
void swap(int *a, int *b) {
int c = *a;
*a = *b;
Line 1,034 ⟶ 1,028:
}
int partition(int A[], int p, int q) {
swap(&A[p + (rand() % (q - p + 1))], &A[q]); // PIVOT = A[q]
int i = p - 1;
for(int j = p; j <= q; j++) {
if(A[j] <= A[q]) {▼
▲ if(A[j] <= A[q])
swap(&A[++i], &A[j]);
}
Line 1,050 ⟶ 1,041:
}
void quicksort(int A[], int p, int q) {
if(p < q) {▼
▲ if(p < q)
int pivotIndx = partition(A, p, q);
|