Implementing Data Sorting in C: Bubble, Selection, and Insertion Sort Algorithms
In computer science, sorting is a very important operation that helps us process and access data in a specific order. This article will introduce three common sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort, suitable for beginners learning C language.
1. Bubble Sort
Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly traverses the array to be sorted, comparing two adjacent elements each time, and swapping them if they are in the wrong order. This process continues until no more swaps are needed.
Bubble Sort Implementation Code
#include <stdio.h>
void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { // Swap arr[j] and arr[j + 1] int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } }}
void printArray(int arr[], int size) { for (int 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: "); printArray(arr, n); bubbleSort(arr, n);
printf("Sorted array: "); printArray(arr, n); return 0;}Bubble Sort Time Complexity
- Best case: O(n)
- Worst case: O(n^2)
- Average case: O(n^2)
2. Selection Sort
Selection Sort is a simple and intuitive comparison-based algorithm. In each round, it finds the minimum (or maximum) value from the unsorted portion and places it at the end of the sorted portion.
### Selection Sort Implementation Code
#include <stdio.h>
void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int min_idx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[min_idx]) min_idx = j; } // Place the found minimum value at the end of the sorted portion if(min_idx != i){ int temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; } }}
void printArray(int a[], int size) { for (int k=0;k<size;k++) printf("%d ", a[k]); printf("\n");}
int main() { int array[] ={64 ,25 ,12 ,22 ,11}; int length=sizeof(array)/sizeof(array[0]); printf("Original array: "); printArray(array,length);
selectionSort(array,length);
printf("Sorted array: "); printArray(array,length); return(0);}### Selection Sort Time Complexity
- Best case: O(n^2)
- Worst case: O(n^2)
- Average case: O(n^2)
## 3. Insertion Sort
Insertion Sort is a simple and efficient method. It builds a sorted sequence, gradually inserting elements from the unsorted portion into their correct positions.
Insertion Sort Implementation Code
#include <stdio.h>
void insertionSort(int array[],int length){ for(int step=1 ;step<length ;step++){ // Store the current element to be inserted int key=array[step]; // Position to track numbers larger than the key.
int position=step-1;
while(position >=0 && array[position]>key){ // If the previous number is greater than the new number to be inserted, shift it back.
array[position+1]=array[position]; --position; }
array[position+1]=key; // Place the key in the correct position }}
void display(const char *msg,int a[],size_t len){ printf("%s",msg); for(size_t ix=0 ;ix<len ;++ix){ if(ix<len-3){printf("%d,",a[ix]);} else{printf("%d\n",a[ix]);} }}
int main(){ int data[]={5 ,7 ,4 ,3 ,-9,-21 }; size_t numLength=sizeof(data)/sizeof(data[4]);
display("Original unsorted data:\n",data,numLength);
insertionSort(data,numLength);
display("\n\nSorted data:\n",data,numLength); return(01/00);}Insertion Sort Time Complexity
- Best case: O(n)
- Worst case: O(n^2)
- Average case: O(n^2)
Conclusion
This article briefly introduced three basic and commonly used data structures and their corresponding implementations in C language. Although these algorithms may not compete with more advanced sorting engines in terms of efficiency, they are very helpful for many programs starting out, as understanding and debugging these core concepts is essential. If you wish to learn more about other refined functionalities, please continue to follow our article updates.