Selection Sort is an algorithm that falls under the category of Brute Force because it depends on the input size and it goes over all elements (or almost all elements) in order to perform its main task. It is not really effective since it's time complexity is but it is a really simple algorithm and the analysis is straightforward. Let's start seeing the pseudo-code, followed by its analysis and finally but not least, an example using C language.
Here you can see the algorithm analysis. We notice that since we have two for loops, we start the analysis with two sums as well.
Simplifying a bit more, we can see that it turns to be a fraction with a quadratic element on its numerator. If we consider this element with limit to infinite , we'll reduce to just a regular
Finally, you can see the an example using C. You can compile it with:
gcc selection_sort.c -o selection_sort
#include <stdio.h>
void swap(int *a, int i, int min, int i_value, int min_value) {
a[i] = min_value;
a[min] = i_value;
}
int selection_sort(int *a, int n) {
int i, j, min;
for (i = 0; i < (n - 1); i++) {
min = i;
for (j = i + 1; j < n; j++) {
if (a[j] < a[min]) {
min = j;
}
}
swap(a, i, min, a[i], a[min]);
}
return 0;
}
int main() {
int n = 7;
int array[] = {89, 45, 68, 90, 29, 34, 17};
printf("Before: \n");
for (int x = 0; x < n; x++) {
printf("%d, ", array[x]);
}
printf("\n\n");
selection_sort(array, n);
printf("After: \n");
for (int x = 0; x < n; x++) {
printf("%d, ", array[x]);
}
printf("\n");
return 0;
}
Top comments (0)