#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.
#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.
Selection Sort Algorithm:
Start with the first element of the array as the "current minimum."
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.
After the inner loop completes, swap the current minimum element with the element at the current position.
Repeat steps 1 to 3 for each element until the second-to-last element.
The array is now sorted.
Explanation of the Algorithm using the Above C Code:
The code begins by including the necessary library for input and output functions.
It defines a function named selectionSort
that takes an array arr
and its length n
as parameters.
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.
The main
function defines an array arr
and calculates its length n
.
The original array elements are printed using a loop and printf
.
The selectionSort
function is called to sort the array.
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.
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:
The outer loop runs 'n' times, iterating through the entire array to select the minimum element.
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.
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).