Sort an array using selection sort using C programming language

Sort an array using selection sort using C programming language.

Code:

#include <stdio.h>

// Function to perform selection sort
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;

// Find the index of the minimum element in the unsorted part
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}

// Swap the found minimum element with the first element of the unsorted part
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

selectionSort(arr, n);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

In this code, the selectionSort function sorts the array by repeatedly finding the minimum element from the unsorted part and swapping it with the first element of the unsorted part. The main function demonstrates how to use the selection sort function to sort an array and then prints both the original and sorted arrays.

 

Explanation:

#include <stdio.h>

This line includes the standard input-output library, which allows you to use functions like printf and scanf.

void selectionSort(int arr[], int n) {

This line defines a function named selectionSort that takes an array arr and an integer n as parameters. This function will be responsible for sorting the array using the selection sort algorithm.

for (int i = 0; i < n - 1; i++) {

This line starts a loop that iterates through the array. It goes from i = 0 to i = n - 2 because the last element in a sorted array is already in its correct position.

int minIndex = i;

Here, we initialize a variable minIndex with the current value of i. This variable will keep track of the index of the minimum element found during each iteration.

for (int j = i + 1; j < n; j++) {

This line starts another loop inside the outer loop. It searches for the minimum element in the unsorted part of the array, which begins from i + 1 and goes up to the end of the array.

if (arr[j] < arr[minIndex]) {
minIndex = j;
}

Inside the inner loop, we compare the element at index j with the element at the current minIndex. If the element at index j is smaller, we update minIndex to j, which means we've found a new minimum element.

int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;

After finding the minimum element's index in the inner loop, we swap the element at index i with the minimum element found. We use a temporary variable temp to hold the value of the element at index i temporarily while swapping.

int main() {

This is the starting point of the program. The main function is the entry point of any C program.

int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

Here, we define an integer array arr containing some values, and we calculate the number of elements in the array using the sizeof operator. This gives us the size of the array in memory divided by the size of a single array element, giving us the number of elements (n).

printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

We print the original array elements using a loop and the printf function. This loop goes through each element of the array and prints it.

selectionSort(arr, n);

This line calls the selectionSort function we defined earlier to sort the arr array.

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

After sorting, we print the sorted array elements using another loop and the printf function. This loop goes through each element of the array and prints it.

return 0;

Finally, we indicate that the program has finished successfully by returning 0 from the main function.

The code reads an array, sorts it using the selection sort algorithm, and then prints both the original and sorted arrays.

 

Algorithm:

Selection Sort Algorithm:

1. Start with the first element of the array as the "current minimum."

2. Iterate through the array from the second element to the last element. a. Compare the current element with the current minimum. b. If the current element is smaller than the current minimum, update the current minimum's index.

3. After the inner loop completes, swap the current minimum element with the element at the current position.

4. Repeat steps 1 to 3 for each element until the second-to-last element.

5. The array is now sorted.

Explanation of the Algorithm using the Above C Code:

1. The code begins by including the necessary library for input and output functions.

2. It defines a function named selectionSort that takes an array arr and its length n as parameters.

3. Within the selectionSort function, there is an outer loop that iterates through the array. a. Inside the outer loop, a variable minIndex is used to track the index of the current minimum element. b. An inner loop then searches for the minimum element in the unsorted part of the array, starting from the next index. c. If a smaller element is found, the minIndex is updated. d. After the inner loop completes, the current minimum element is swapped with the element at the current position.

4. The main function defines an array arr and calculates its length n.

5. The original array elements are printed using a loop and printf.

6. The selectionSort function is called to sort the array.

7. The sorted array elements are printed using another loop and printf.

The selection sort algorithm works by iteratively finding the minimum element from the unsorted portion of the array and swapping it with the first element of the unsorted portion. This process is repeated until the entire array is sorted. The provided C code implements this algorithm to sort an array and demonstrates the sorting process through print statements.

 

Time Complexity:

The time complexity of the selection sort algorithm, as implemented in the above C program, is O(n^2), where 'n' is the number of elements in the array.

This is because the algorithm involves two nested loops:

1. The outer loop runs 'n' times, iterating through the entire array to select the minimum element.

2. The inner loop also runs 'n' times, comparing the current element with the remaining unsorted elements to find the minimum.

Since both loops iterate 'n' times, the total number of comparisons and swaps performed is proportional to n * n, leading to a quadratic time complexity of O(n^2).

It's important to note that selection sort is not very efficient for larger arrays due to its quadratic time complexity. Other sorting algorithms like merge sort or quicksort offer better average and best-case performance.

 

Space Complexity:

The space complexity of the above C program, which implements the selection sort algorithm, is O(1), constant space complexity.

The reason for this is that the program only uses a fixed amount of extra space regardless of the size of the input array. The extra space is used for variables like i, j, minIndex, and temp, which are used to control the loops and perform swaps. These variables don't depend on the size of the input array; they remain constant regardless of how many elements are in the array.

In addition to these variables, the program uses a fixed amount of space for the arr array itself and any other local variables that might be created within the main function. However, the space used for the array and local variables is not dependent on the input size, so the space complexity remains constant, or O(1).

Thank You