Sorting in C
Subject: Data Structures and Algorithms · Language: C · Level: intermediate · 6 min read
Learn why sorting is needed, how comparison-based sorting works, and how to write clean bubble sort code.
Sorting means arranging data in a specific order. Most of the time, we sort numbers in ascending order or descending order.
If marks are arranged from lowest to highest, prices are arranged from cheapest to costliest, or names are arranged alphabetically, sorting is being used.
Why Sorting Is Important
Sorting makes data easier to search, compare, rank, and display. Many algorithms also become faster when data is sorted.
For example, binary search works only on sorted data. Leaderboards, rank lists, product filters, and database results all depend on sorting.
Sorting Order
- Ascending order means small to large, such as 1, 2, 3, 4
- Descending order means large to small, such as 4, 3, 2, 1
- Alphabetical order arranges words from A to Z
- Custom order arranges data by a rule, such as highest marks first
Comparison-Based Sorting
Many sorting algorithms work by comparing two values and deciding whether they are already in the correct order.
For ascending order, if the left value is greater than the right value, they should be swapped.
For descending order, if the left value is smaller than the right value, they should be swapped.
Swapping Two Values
Swapping means exchanging two values using a temporary variable.
```c
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
```
Bubble Sort
Bubble sort is one of the easiest sorting algorithms to understand. It repeatedly compares adjacent elements and swaps them if they are in the wrong order.
After the first full pass, the largest element reaches the end of the array. After the second pass, the second largest element reaches its correct position.
That is why the inner loop becomes shorter after every pass.
Bubble Sort Program
This program takes array elements from the user and sorts them in ascending order.
```c
#include <stdio.h>
int main(void) {
int n;
int arr[50];
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
Selection Sort Idea
Selection sort finds the smallest element and places it at the beginning. Then it finds the next smallest element and places it in the second position.
It performs fewer swaps than bubble sort, but it still takes O(n^2) time.
Insertion Sort Idea
Insertion sort builds the sorted array one element at a time. It takes one element and inserts it into its correct place among the previous sorted elements.
Insertion sort works well when the array is small or already almost sorted.
Merge Sort and Quick Sort
Merge sort and quick sort are faster for large data compared to bubble, selection, and insertion sort.
Merge sort divides the array into smaller parts, sorts them, and then merges them. Quick sort chooses a pivot and places smaller and larger values around it.
Stable and In-Place Sorting
A stable sorting algorithm keeps equal elements in their original relative order. This matters when sorting records by one field while preserving another order.
An in-place sorting algorithm uses very little extra memory. Bubble sort is stable and in-place, but it is not efficient for large input.
Time Complexity
Bubble sort takes O(n^2) time in the average and worst case because it uses nested loops.
Its best case can be improved to O(n) if we add a flag to stop when no swaps happen in a pass.
Which Sorting Should a Student Learn First?
Start with bubble sort to understand comparisons and swaps. Then learn selection sort and insertion sort. After that, move to merge sort and quick sort to understand efficient sorting.
Practice Question
Modify the program to sort the array in descending order by changing the comparison condition.