Selection Sort
//The time complexity of selection sort is O(n^2)
#include <stdio.h>
void selection_sort(int array[], 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 (array[j] < array[min_idx]) {
min_idx = j;
}
}
temp = array[min_idx];
array[min_idx] = array[i];
array[i] = temp;
}
}
int main() {
int array[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(array) / sizeof(array[0]);
selection_sort(array, n);
printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", array[i]);
}
return 0;
}
Insertion Sort
//The time complexity of insertion sort is O(n^2)
#include <stdio.h>
void insertion_sort(int array[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = array[i];
j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
ShellSort
//The time complexity of shell sort is O(n^2)
#include <stdio.h>
void shell_sort(int array[], int n) {
int gap, i, j, temp;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
temp = array[i];
for(j = i;j>=gap && array[j-gap]>temp; j -= gap) {
array[j] = array[j - gap];
}
array[j] = temp;
}
}
}
QuickSort.c
The time complexity of quick sort is O(n log n) in the average case and O(n^2) in the
worst case, but it is generally faster in practice than other O(n log n) sorting
algorithms.
#include <stdio.h>
void quick_sort(int array[], int low, int high) {
int i, j, pivot, temp;
if (low < high) {
pivot = low;
i = low;
j = high;
while (i < j) {
while (array[i] <= array[pivot] && i <= high) {
i++;
}
while (array[j] > array[pivot] && j >= low) {
j--;
}
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
temp = array[j];
array[j] = array[pivot];
array[pivot] = temp;
quick_sort(array, low, j - 1);
quick_sort(array, j + 1, high);
}
}
MergeSort.c
The time complexity of merge sort is O(n log n) in all cases. It is generally slower in
practice than other O(n log n) sorting algorithms.
#include <stdio.h>
#include <stdlib.h>
void merge(int *,int, int , int );
void mergesort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return;
}
// Merge sort concepts start here
void merge(int *a, int low, int high, int mid)
{
int i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i] < a[j]) {
c[k] = a[i];
k++;
i++;
}
else{
c[k] = a[j];
k++;
j++;
}
} //end of while
while (i <= mid) {
c[k] = a[i];
k++;
i++;
}
while (j <= high){
c[k] = a[j];
k++;
j++;
} //end of while
//copy back to main array
for (i = low; i < k; i++)
{
a[i] = c[i];
}
}
Radix Sort
// A utility function to get maximum value in arr[]
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to the digit
represented by pos.
void countSort(int arr[], int n, int pos)
{
int output[n]; // output array
int i, count[10] = { 0 };
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(arr[i] / pos) % 10]++;
// Change count[i] so that count[i] now contains actual position of
this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / pos) % 10] - 1] = arr[i];
count[(arr[i] / pos) % 10]--;
}
// Copy the output array to arr[], so that arr[] now contains sorted
numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using Radix Sort
void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, pos is passed. pos is 10^i
// where i is current digit number
for (int pos = 1; m / pos > 0; pos *= 10)
countSort(arr, n, pos);
}
// A utility function to print an array
void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
radixsort(arr, n);
print(arr, n);
return 0;
}
HeapSort
#include <stdio.h>
#include <stdlib.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
for (int i=0; i<n; ++i)
printf("%d ",arr[i]);
return 0;
}
Counting Sort
#include <stdio.h>
#include <stdlib.h>
void countingSort(int *arr, int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int *count = (int *)calloc(max + 1, sizeof(int));
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
int k = 0;
for (int i = 0; i <= max; i++) {
for (int j = 0; j < count[i]; j++) {
arr[k++] = i;
}
}
free(count);
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
countingSort(arr, n);
printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
