Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[Complexities_of_Basic_Sorting_Algorithms |Complexity and no. of swaps required]] | [[Complexities_of_Basic_Sorting_Algorithms |Complexity and no. of swaps required]] | ||
| − | + | <metadesc>Quick sort program in C</metadesc> | |
| − | <syntaxhighlight lang="c"> | + | <syntaxhighlight lang="c" name="quicksort"> |
#include <stdio.h> | #include <stdio.h> | ||
| Line 16: | Line 16: | ||
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)// Finds the no. of elements in the array < a[p] from the beginning and swaps with the no. of elements in the array greater than a[p] from the end | while(i < j)// Finds the no. of elements in the array < a[p] from the beginning and swaps with the no. of elements in the array greater than a[p] from the end | ||
| Line 27: | Line 26: | ||
j--; | j--; | ||
if(i < j) | if(i < j) | ||
| − | |||
swap(&a[i], &a[j]); | swap(&a[i], &a[j]); | ||
| − | |||
} | } | ||
swap(&a[j], &a[p]); | swap(&a[j], &a[p]); | ||
| Line 40: | Line 37: | ||
int i; | int i; | ||
for(i = 0; i < n; i++) | for(i = 0; i < n; i++) | ||
| − | |||
printf("%d ",a[i]); | printf("%d ",a[i]); | ||
| − | |||
} | } | ||
| Line 62: | Line 57: | ||
printArray(num, i); | printArray(num, i); | ||
printf("\n"); | printf("\n"); | ||
| + | |||
| + | return 0; | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| Line 68: | Line 65: | ||
{{Template:FBD}} | {{Template:FBD}} | ||
| − | [[Category: | + | [[Category: Arrays]] |
| + | [[Category:Sorting]] | ||
Complexity and no. of swaps required
<syntaxhighlight lang="c" name="quicksort">
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)// Finds the no. of elements in the array < a[p] from the beginning and swaps with the no. of elements in the array greater than a[p] from the end { while(a[i] <= a[p] && i < end) i++; while(a[j] > a[p]) //( > ensures j never comes equal to 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");
return 0;
} </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) { return; } i = p = start, j = end; while(i < j)// Finds the no. of elements in the array < a[p] from the beginning and swaps with the no. of elements in the array greater than a[p] from the end { while(a[i] <= a[p] && i < end) i++; while(a[j] > a[p]) //( > ensures j never comes equal to 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>
GATECSE