Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | <metadesc>Selection sort program in C using recursion</metadesc> | ||
[[Complexities_of_Basic_Sorting_Algorithms |Complexity and no. of swaps required]] | [[Complexities_of_Basic_Sorting_Algorithms |Complexity and no. of swaps required]] | ||
==Recursive solution== | ==Recursive solution== | ||
<syntaxhighlight lang="c" name="selectionsort_rec"> | <syntaxhighlight lang="c" name="selectionsort_rec"> | ||
| + | #include <stdio.h> | ||
void selection_sort(int *a, int n) | void selection_sort(int *a, int n) | ||
| Line 29: | Line 31: | ||
scanf("%d", &a[i]); | scanf("%d", &a[i]); | ||
selection_sort(a, n); | selection_sort(a, n); | ||
| − | + | printf("Printing sorted:\n"); | |
for(i = 0; i < n; i++) | for(i = 0; i < n; i++) | ||
printf("%d ", a[i]); | printf("%d ", a[i]); | ||
| Line 37: | Line 39: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| + | ==Non-Recursive solution== | ||
| + | <syntaxhighlight lang="c" name="selectionsort_rec"> | ||
| + | |||
| + | #include <stdio.h> | ||
| + | |||
| + | void selection_sort(int *a, int n) | ||
| + | { | ||
| + | int big, i, j; | ||
| + | for(i = 0; i < n; i++) | ||
| + | { | ||
| + | big = 0; | ||
| + | for(j = 1; j < n-i; j++) | ||
| + | if(a[j] > a[big]) | ||
| + | big = j; | ||
| + | |||
| + | /*swap a[n-1] and a[big]*/ | ||
| + | int temp = a[n-i-1]; | ||
| + | a[n-i-1] = a[big]; | ||
| + | a[big] = temp; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | |||
| + | int main() | ||
| + | { | ||
| + | int a[100], i, n; | ||
| + | printf("Enter n:"); | ||
| + | scanf("%d", &n); | ||
| + | printf("Enter numbers: "); | ||
| + | for(i = 0; i < n; i++) | ||
| + | scanf("%d", &a[i]); | ||
| + | selection_sort(a, n); | ||
| + | printf("Printing sorted:\n"); | ||
| + | for(i = 0; i < n; i++) | ||
| + | printf("%d ", a[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | |||
| + | </syntaxhighlight> | ||
{{Template:FBD}} | {{Template:FBD}} | ||
[[Category: Arrays]] | [[Category: Arrays]] | ||
| + | [[Category: Sorting]] | ||
Complexity and no. of swaps required
<syntaxhighlight lang="c" name="selectionsort_rec">
void selection_sort(int *a, int n) {
GATECSE if(n == 1)
return;
int big = 0, i;
for(i = 1; i < n; i++)
if(a[i] > a[big])
big = i;
/*swap a[n-1] and a[big]*/
int temp = a[n-1];
a[n-1] = a[big];
a[big] = temp;
selection_sort(a, n-1);
}
int main()
{
int a[100], i, n;
printf("Enter n:");
scanf("%d", &n);
printf("Enter numbers: ");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
selection_sort(a, n);
printf("Printing sorted:\n");
for(i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
</syntaxhighlight>
<syntaxhighlight lang="c" name="selectionsort_rec">
void selection_sort(int *a, int n) {
int big, i, j;
for(i = 0; i < n; i++)
{
big = 0;
for(j = 1; j < n-i; j++)
if(a[j] > a[big])
big = j;
/*swap a[n-1] and a[big]*/
int temp = a[n-i-1];
a[n-i-1] = a[big];
a[big] = temp;
}
}
int main()
{
int a[100], i, n;
printf("Enter n:");
scanf("%d", &n);
printf("Enter numbers: ");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
selection_sort(a, n);
printf("Printing sorted:\n");
for(i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
</syntaxhighlight>
Complexity and no. of swaps required
<syntaxhighlight lang="c" name="selectionsort_rec">
void selection_sort(int *a, int n) {
if(n == 1)
return;
int big = 0, i;
for(i = 1; i < n; i++)
if(a[i] > a[big])
big = i;
/*swap a[n-1] and a[big]*/
int temp = a[n-1];
a[n-1] = a[big];
a[big] = temp;
selection_sort(a, n-1);
}
int main()
{
int a[100], i, n;
printf("Enter n:");
scanf("%d", &n);
printf("Enter numbers: ");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
selection_sort(a, n);
prntf("Printing sorted:\n");
for(i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
</syntaxhighlight>