Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 15: | Line 15: | ||
{ | { | ||
int i, j, p; | int i, j, p; | ||
| − | if(start >= end | + | if(start >= end) |
{ | { | ||
return; | return; | ||
} | } | ||
| − | i = p = start, j = end | + | i = p = start, j = end; |
while(i < j) | while(i < j) | ||
{ | { | ||
| − | while(a[i] <= a[p] && i < end | + | while(a[i] <= a[p] && i < end) |
i++; | i++; | ||
while(a[j] > a[p]) | while(a[j] > a[p]) | ||
| Line 32: | Line 32: | ||
} | } | ||
swap(&a[j], &a[p]); | swap(&a[j], &a[p]); | ||
| − | qsort(a, start, j); | + | qsort(a, start, j-1); |
qsort(a, j + 1, end); | qsort(a, j + 1, end); | ||
} | } | ||
| Line 58: | Line 58: | ||
sscanf(str, "%d", &num[i++]); | sscanf(str, "%d", &num[i++]); | ||
} | } | ||
| − | qsort(num, 0, i); | + | qsort(num, 0, i-1); |
printf("The sorted numbers are: "); | printf("The sorted numbers are: "); | ||
printArray(num, i); | printArray(num, i); | ||
Complexity and no. of swaps required
<syntaxhighlight lang="c">
void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }
void qsort(int a[], int start, int end) { int i, j, p; if(start >= end) { return; } i = p = start, j = end; while(i < j) { while(a[i] <= a[p] && i < end) i++; while(a[j] > a[p]) j--; if(i < j) { swap(&a[i], &a[j]); } } swap(&a[j], &a[p]); qsort(a, start, j-1); qsort(a, j + 1, end); }
void printArray(int a[], int n) { int i; for(i = 0; i < n; i++) { printf("%d ",a[i]); } }
int main() { char str[20]; int num[100]; int i = 0; printf("Enter the numbers to sort (. to stop): "); while(1) { scanf("%s",str); if(str[0] == '.') break; sscanf(str, "%d", &num[i++]); } qsort(num, 0, i-1); printf("The sorted numbers are: "); printArray(num, i); printf("\n"); } </syntaxhighlight>
Complexity and no. of swaps required
<syntaxhighlight lang="c">
void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }
void qsort(int a[], int start, int end) { int i, j, p; if(start >= end-1) { return; } i = p = start, j = end-1; while(i < j) { while(a[i] <= a[p] && i < end-1) i++; while(a[j] > a[p]) j--; if(i < j) { swap(&a[i], &a[j]); } } swap(&a[j], &a[p]); qsort(a, start, j); qsort(a, j + 1, end); }
void printArray(int a[], int n) { int i; for(i = 0; i < n; i++) { printf("%d ",a[i]); } }
int main() { char str[20]; int num[100]; int i = 0; printf("Enter the numbers to sort (. to stop): "); while(1) { scanf("%s",str); if(str[0] == '.') break; sscanf(str, "%d", &num[i++]); } qsort(num, 0, i); printf("The sorted numbers are: "); printArray(num, i); printf("\n"); } </syntaxhighlight>
GATECSE