Common Sorting Algorithms for Non-numeric Computing in C
Sorting Definition
Sorting is a computer operation that aims to adjust an unordered record list to an ordered record list. Sorting is classified into internal sorting and external sorting.
Bubble Sort
Definition: Bubble Sort sequentially compares adjacent elements in a list, swapping them if the first is larger than the second to move the larger value toward the end of the list. This process repeats through multiple passes until the entire list is sorted in ascending order.
Advantage: stable
Disadvantage: slow. Only two adjacent data records can be moved at a time.
Algorithm implementation: Assume that a list containing n numbers needs to be sorted in ascending order. The steps are as follows:
- Sequentially compare adjacent elements starting from the first to the last in the array, swapping their positions if the preceding element is greater than the succeeding one.
- After the first pass, the largest element is positioned at the final index of the array. Subsequently, compare adjacent elements from the first to the penultimate position, swapping them if the former is greater than the latter.
- Repeat step 1 for n – 1 passes, reducing the number of comparisons by one in each subsequent pass to complete the sorting process.
Bubble Sort example: Read any 10 integers, sort them in ascending order, and then output the sorted integers.
#define n 10
void main()
{
int a[n],i,j,t;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(j=1;j<=n-1;j++) /*Process the n numbers for n – 1 passes.*/
for(i=0;i<=n-1-j;i++) /*Reduce the number of comparisons by one in each subsequent pass.*/
if(a[i]>a[i+1])
{
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
for(i=0;i<n;i++)
printf("%d\n",a[i]);
}
Conventional sorting example:
#include <stdio.h>
void main()
{
int a[11],i,j,t;
printf("Input 10 numbers:\n");
for(i=1;i<11;i++)
{
scanf("%d",&a[i]);
}
printf("\n");
for(j=1;j<=9;j++)
for(i=1;i<=10-j;i++)
if(a[i]>a[i+1])
{
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
printf("The sorted numbers:\n");
for(i=1;i<11;i++)
printf("%d ",a[i]);
}
Selection Sort
Definition: Selection Sort identifies the record with the minimum key among n – i + 1 (i = 1, 2, …, n – 1) records during each pass, assigning it as the i-th record within the sorted list. Algorithms based on this principle primarily include Simple Selection Sort, Tree Selection Sort, and Heap Sort.
Advantage: The number of data swapping is known (n – 1).
Disadvantage: Many comparisons are required, and the algorithm is unstable.
Algorithm implementation: Assume that a list containing n numbers needs to be sorted in ascending order. The steps are as follows:
- Find the smallest element (refer to the following algorithm implementation) in the n numbers stored in the array and then swap it with the first element.
- Find the smallest element in the remaining n – 1 elements or the second smallest in the n elements, and swap it with the second element.
- Repeat step 1 for n – 1 passes to complete the sorting process.
Selection Sort example: Read any 10 integers, sort them in ascending order, and then output the sorted integers.
#include <stdio.h>
#define n 10
void main()
{
int a[n],i,j,k,t;
for(i=0;i<n;i++) scanf("%d",&a[i]);
for(i=0;i<n-1;i++) /*Processing n – 1 passes*/
{
k = i;
/*Assume that the first number (the i-th number among n numbers) is the smallest one in this pass. k records the index of this number.*/
for(j=i+1;j<n;j++)
if(a[j] < a[k])
k = j;
if (k != i)
{
t = a[i];
a[i] = a[k];
a[k] = t;
}
}
for(i=0;i<n;i++)
printf("%d\n",a[i]);
}
Conventional sorting example:
#include <stdio.h>
void main()
{ int a[11],i,j,k,x;
printf("Input 10 numbers:\n");
for(i=1;i<=10;i++)
scanf("%d",&a[i]);
printf("\n");
for(i=1;i<=10;i++)
{ k=i;
for(j=i+1;j<=10;j++)
if(a[j]<a[k]) k=j;
if(i!=k)
{
x=a[i];
a[i]=a[k];
a[k]=x;
}
}
printf("The sorted numbers:\n");
for(i=1;i<=10;i++)
printf("%d ",a[i]);
}
Function-based sorting example:
#include <stdio.h>
void sort(int array[],int n)
{ int i,j,k,t;
for(i=0;i<n-1;i++)
{ k=i;
for(j=i+1;j<n;j++)
if(array[j]<array[k])
k=j;
if(k!=i)
{ t=array[i];
array[i]=array[k];
array[k]=t;
}
}
}
main()
{ int a[10],i;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
sort(a,10);/*Array name as a function parameter*/
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
}
Insertion Sort
Definition: Insertion Sort treats n elements as two lists, one sorted and one unsorted. Initially, the sorted list contains only one element, while the unsorted list contains n – 1 elements. It works by iteratively inserting the first element in the unsorted list into a correct position in the sorted list after comparing with the elements in the sorted list from back to front.
Advantage: stable and fast
Disadvantage: The number of comparisons is not fixed. A higher frequency of comparisons leads to increased data movement for elements following the insertion point, particularly with large datasets. Using a linked list can resolve this issue.
Algorithm implementation: The key to Insertion Sort is to insert each newly read element into the final array immediately, ensuring the array remains sorted after every insertion.
Insertion Sort example 1: Insert any integer x into an ascending list and ensure the list remains in ascending order.
#include <stdio.h>
#define n 10
void main()
{
int a[n]={-1,3,6,9,13,22,27,32,49},x,j,k; /*Note that a position is reserved for the number to be inserted.*/
scanf("%d",&x);
if(x>a[n-2]) a[n-1]=x ; /*If x is greater than the last number, store x in the last element.*/
else /*Search for the insertion position.*/
{j=0;
while( j<=n-2 && x>a[j]) j++;
/*Move numbers one position rightward, starting from the last number to the number at the insertion position.*/
for(k=n-2; k>=j; k- -)
a[k+1]=a[k];
a[j]=x; /*Insert the number.*/
}
for(j=0;j<=n-1;j++) printf("%d ",a[j]);
}
Insertion Sort example 2: Read any 10 integers, sort them in descending order, and then output the sorted integers.
#include <stdio.h>
#define n 10
main()
{int a[n],i,j,k,x;
scanf("%d",&a[0]); /*Read the first number and store it to a[0].*/
for(j=1;j<n;j++) /*Iteratively insert the second to tenth numbers into array a in order.*/
{scanf("%d",&x);
if(x<a[j-1]) a[j]=x;
/*If the newly read number is smaller than the last number in the array, store the new number after the last element.*/
else /*Search for the insertion position.*/
{i=0;
while(x<a[i]&&i<=j-1) i++;
/*The for loop moves numbers one position rightward, starting from the last number to the number at the insertion position.*/
for(k=j-1;k>=i;k--) a[k+1]=a[k];
a[i]=x; /*Insert the number.*/
}
}
for(i=0;i<n;i++)
printf("%d\n",a[i]);
}
Merge Sort
Definition: Merge Sort is an efficient sorting algorithm based on the merge operation and follows the divide and conquer approach. It works by merging sorted sub-lists to obtain an entire sorted list. Specifically, each sub-list is sorted, followed by the merging of these sub-list segments to ensure ordering across the entire list. The merging of two sorted lists into a single sorted list is defined as two-way merging, which combines two lists—both in ascending or descending order—into a new list that is sorted in original ordering.
Merge Sort example: Merge two sorted lists in ascending order, one with six data records and the other with four data records.
#include <stdio.h>
#define m 6
#define n 4
void main()
{
int a[m]={-3,6,19,26,68,100} ,b[n]={8,10,12,22};
int i,j,k,c[m+n];
i=j=k=0;
while(i<m && j<n) /*Iteratively store the smaller numbers from arrays a and b into array c.*/
{if(a[i]<b[j]){c[k]=a[i]; i++;}
else {c[k]=b[j]; j++;}
k++; }
while(i>=m && j<n) /*If all numbers in array a have been processed, append the remaining numbers of array b to array c.*/
{c[k]=b[j]; k++; j++;}
while(j>=n && i<m) /*If all numbers in array b have been processed, append the remaining numbers of array a to array c.*/
{c[k]=a[i]; k++; i++;}
for(i=0;i<m+n;i++) printf("%d ",c[i]);
}
- Reversing the order of a character array
Sort the input character string in reverse order. For example, if the input character string is ABCDE, the output character string should be EDCBA. Code example:
#include <stdio.h> #include<string.h> void main() { char c,str[80]; int i,j; printf("Enter a string:\n"); scanf("%s",str); /*Or gets(str);puts(str); */ for(i=0,j=strlen(str)-1;i<j;i++,j--) { c=str[i]; str[i]=str[j]; str[j]=c; } printf("\nReversed string:\n%s\n",str); }