This article will examine several array sorting techniques in C programming.
Sorting an Array in C
There are several sorting algorithms available in C programming, which are:
1: Bubble Sort
The bubble sort, a straightforward method that compares neighboring array items and exchanges them when they are not in the right order, is one of the most often used sorting algorithms. Bubble sort is ineffective for big data sets due to its time complexity, which is O(n^2). It is suited for tiny data sets, nevertheless, and is simple to grasp and put into practice.
When using the bubble sort method, the first and second elements of the array are compared, and if the first one is greater than the second one, the elements are switched. Repeat the process for the remaining entries until the array is sorted. Up till the array is sorted, the procedure is repeated for the remaining elements.
void bubbleSort(int array[], int size) {
int i, j;
for (i = 0; i < size - 1; i++) {
for (j = 0; j array[j + 1]) {
// Swap the elements
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
int main() {
int array[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(array) / sizeof(array[0]);
printf("Original Array: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
bubbleSort(array, size);
printf("\nSorted Array: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
return 0;
}
The bubbleSort method in this code requires an array and its size as inputs. It iterates across the array and compares nearby entries using nested loops. The elements are switched if they are out of sequence. Up till the array is completely sorted, this operation is repeated. An array and its size are defined in the main function. The bubbleSort function is then used to sort the array in ascending order. We output the original and sorted arrays then.
2: Selection Sort
The selection sort is another well-liked sorting algorithm that works by choosing the array’s lowest element and exchanging it with the first member. Once the array is sorted, the procedure is repeated for each of the unsorted elements that are still there. The selection sort is appropriate for tiny data sets and has an O(n^2) time complexity.
void selectionSort(int array[], int size) {
int i, j, minIndex, temp;
for (i = 0; i < size - 1; i++) {
minIndex = i;
for (j = i + 1; j < size; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}
int main() {
int array[] = {64, 25, 12, 22, 11};
int size = sizeof(array) / sizeof(array[0]);
printf("Original Array: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
selectionSort(array, size);
printf("\nSorted Array: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
return 0;
}
The selectionSort() function in this code requires an array and its size as inputs. To cycle over the array and locate the smallest entry in the unsorted section, it employs nested loops. The initial element of the unsorted segment is switched with the smallest element after it has been located.
Up till the array is completely sorted, this operation is repeated. An array and its size are defined in the main function. The array is then sorted using the selectionSort() method in ascending order. We output the initial and sorted arrays as a last check.
3: Insertion Sort
Another basic sorting method is the insertion sort, which involves picking out each element one at a time and placing it into the correct location. The process involves iterating over all the elements in the array and sorting them in the correct order. Although insertion sort is faster than bubble sort and selection sort for small data sets, its time complexity is O(n^2).
void insertionSort(int arr[], int size) {
for (int step = 1; step < size; step++) {
int key = arr[step];
int j = step - 1;
while (key = 0) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int data[] = {64, 25, 12, 22, 11};
int size = sizeof(data) / sizeof(data[0]);
printf("Original Array:\n");
printArray(data, size);
insertionSort(data, size);
printf("Sorted Array:\n");
printArray(data, size);
return 0;
}
The two functions printArray and insertionSort are defined in the code. The insertionSort function sorts an array using the insertion sort method, gives an array and its size as inputs. The printArray method writes the items of an array to the console after receiving an array and its size as parameters. In the main method, an integer array is set up with certain values.
By dividing the size of the array’s first element by its size, the size of the array is determined. The integer array and its size are passed as inputs to the insertionSort function, which sorts the array in ascending order. The printArray method is then used to print the sorted array on the console.
4: Quick Sort
One of the most effective sorting algorithms is quick sort, which is used in the C programming language. To sort the array, it divides it into smaller sub-arrays and recursively sorts each one until the array is sorted. Quick sort is appropriate for big data sets and has an average time complexity of O(nlogn).
During the Quick sort process, a pivot element is chosen from the array and the remaining elements are rearranged so that all items that are smaller than the pivot are placed to its left and all bigger elements are placed to its right. The two sub-arrays generated on either side of the pivot go through the identical procedure twice.
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
int partition(int arr[], int low, int high) {
int piv = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= piv) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int data[] = {64, 25, 12, 22, 11};
int size = sizeof(data) / sizeof(data[0]);
printf("Original Array: \n");
printArray(data, size);
quickSort(data, 0, size - 1);
printf("Sorted Array: \n");
printArray(data, size);
return 0;
}
The swap() function is first defined in the program to switch two array members. The partition function is then defined, which accepts an array, a low index, a high index, and a pivot index as arguments. The function selects the final array member as the pivot and arranges the array’s contents so that everything smaller than the pivot is to the left of it and everything bigger than the pivot is to the right of it.
An integer array and its size are defined in the main function. The array is then sorted in ascending order using the quickSort() function. The array is sorted using the partition function using the recursive quickSort() method. A low index, a high index, and an array are required inputs.
In order to sort the pivot’s left and right subarrays, it first chooses a pivot index using the partition function. The sorted array is printed in ascending order by calling the printArray() method at the conclusion of the main function.
5: Merge Sort
A sorting method called merge sort is based on the divide and conquer method. In merge sort, the array is split in half recursively until each sub-array has one element, at which point the sub-arrays are merged to create the sorted array. With the assumption that array[l.. n] and arr[n+1.. r] are sorted, the merge() method joins two sorted sub-arrays into one.
#include <stdlib.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
int arr[] = {23,65,2,65,87,3,65,27};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array: \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array: \n");
printArray(arr, arr_size);
return 0;
}
Two sorted subarrays are combined using the merge() function. The primary array, beginning index, middle index, and ending index are all required inputs. To hold the left and right subarrays, it constructs two temporary arrays. The function then does an iterative comparison of the elements from the two arrays and inserts them into the main array in the proper order.
Any items in the left or right subarrays that are still there are subsequently copied into the main array. The subarrays are joined into a bigger, sorted subarray through the merging process.
An example array is constructed and initialized in the main method. The original array is printed after calculating the array’s size. The array is sorted using the merge sort method by calling the mergeSort() function. The sorted array is then printed, with the elements shown in ascending order.
Output
Conclusion
A key to effective C language programming is the ability to sort an array, which is a fundamental idea in computer science. There are several sorting techniques available, such as bubble sort, selection sort, insertion sort, quick sort, and merge sort. The optimal algorithm relies on the size of the data collection and each of these techniques has strengths and disadvantages.
