Algorithm
Now that we understand the problem statement clearly, let's look at the algorithms which are used for sorting an array in C. We will discuss two popular sorting algorithms: selection sort and bubble sort.
1. Selection Sort
Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and placing it at the beginning. The algorithm maintains two subarrays: the sorted subarray at the left end and the unsorted subarray at the right end.
Let’s see how the selection sort algorithm works:
1. Find the minimum element in the unsorted array.
2. Swap the minimum element with the first element of the unsorted array.
3. Move the boundary of the sorted subarray one element to the right.
4. Repeat steps 1-3 until the entire array is sorted.
2. Bubble Sort
Bubble sort, also known as sinking sort, is another simple sorting algorithm that repeatedly steps through the array, compares adjacent elements, & swaps them if they are in the wrong order. The algorithm gets its name from the way smaller elements "bubble" to the top of the array with each iteration.
Let’s see how the bubble sort algorithm works:
1. Compare the first two elements of the array. If the first element is greater than the second element, swap them.
2. Move to the next pair of adjacent elements & repeat step 1 until the end of the array is reached.
3. After the first pass, the largest element will be at the last position.
4. Repeat steps 1-3 for the remaining unsorted elements until the entire array is sorted.
Using Selection Sort
Now, let's see how we can implement the selection sort algorithm in C:
#include <stdio.h>
void selectionSort(int arr[], int n) {
int i, j, min_idx, temp;
for (i = 0; i < n-1; i++) {
min_idx = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
}
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
You can also try this code with Online C Compiler
In this code:
1. We start by defining the `selectionSort` function that takes an array `arr` & its size `n` as parameters.
2. Inside the function, we use two nested loops to perform the selection sort algorithm.
3. The outer loop `i` iterates from 0 to `n-2` (since the last element will be automatically sorted after `n-1` iterations).
4. In each iteration of the outer loop, we initialize `min_idx` as `i`, assuming the first unsorted element is the minimum.
5. The inner loop `j` iterates from `i+1` to `n-1`, comparing each element with the current minimum.
6. If an element `arr[j]` is smaller than the current minimum `arr[min_idx]`, we update `min_idx` to `j`.
7. After the inner loop ends, we have found the index of the minimum element in the unsorted part of the array.
8. We then swap the minimum element `arr[min_idx]` with the first unsorted element `arr[i]` using a temporary variable `temp`.
9. We repeat steps 4-8 for the remaining unsorted elements until the entire array is sorted.
10. The `printArray` function is used to print the elements of the array.
11. In the `main` function, we create an example array `arr`, calculate its size `n`, & print the original array.
12. We call the `selectionSort` function to sort the array.
13. Finally, we print the sorted array.
The output of this program will be:
Original array
64 34 25 12 22 11 90
Sorted array:
11 12 22 25 34 64 90
Selection sort has a time complexity of O(n^2) in all cases, as it requires nested loops to compare & swap elements. However, it is simple to understand and implement, which makes it suitable for small arrays or educational purposes.
Using Bubble Sort
Now, let’s see the implementation of the bubble sort algorithm in C:
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n-1; i++) {
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
You can also try this code with Online C Compiler
In this code:
1. We start by defining the `bubbleSort` function that takes an array `arr` and its size `n` as parameters.
2. Inside the function, we use two nested loops to perform the bubble sort algorithm.
3. The outer loop `i` iterates from 0 to `n-2` (since the last element will be automatically sorted after `n-1` iterations).
4. The inner loop `j` iterates from 0 to `n-i-2`, comparing each pair of adjacent elements.
5. If the current element `arr[j]` is greater than the next element `arr[j+1]`, we swap them using a temporary variable `temp`.
6. We repeat steps 4-5 for the remaining unsorted elements until the entire array is sorted.
7. After each pass of the inner loop, the largest element among the unsorted elements "bubbles up" to its correct position at the end of the unsorted part of the array.
8. The `printArray` function is used to print the elements of the array.
9. In the `main` function, we create an example array `arr`, calculate its size `n`, and print the original array.
10. We call the `bubbleSort` function to sort the array.
11. Finally, we print the sorted array.
The output of this program will be:
Original array:
64 34 25 12 22 11 90
Sorted array:
11 12 22 25 34 64 90
Bubble sort has a time complexity of O(n^2) in the worst and average cases, as it requires nested loops to compare and swap adjacent elements. However, it is simple to understand and implement, making it suitable for small arrays or educational purposes.
Note: One optimization that can be made to the bubble sort algorithm is to introduce a flag that checks if any swaps were made during a pass. If no swaps were made, it means the array is already sorted, and we can terminate the algorithm early.
Frequently Asked Questions
What is the main difference between selection sort and bubble sort?
The main difference is that selection sort finds the minimum element and places it at the beginning, while bubble sort compares adjacent elements and swaps them if they are in the wrong order.
Which sorting algorithm is more efficient: selection sort or bubble sort?
Both selection sort and bubble sort have a time complexity of O(n^2), making them inefficient for large arrays. However, selection sort typically performs fewer swaps compared to bubble sort.
Can selection sort and bubble sort be used for sorting arrays in descending order?
Yes, both selection sort and bubble sort can be modified to sort arrays in descending order by changing the comparison condition in the algorithms.
Conclusion
In this article, we discussed the concept of sorting an array in C and especially focused on selection sort and bubble sort algorithms. We discussed the problem statement, provided step-by-step explanations, and provided code examples for both sorting techniques. While selection sort and bubble sort have a time complexity of O(n2), making them inefficient for large arrays, they are simple to understand and implement, which makes them suitable for educational purposes and small datasets.
You can also check out our other blogs on Code360.
7+ registered 
