This post is also available in: हिन्दी (Hindi) العربية (Arabic)
In any computer science, sorting and searching are two of the most important processes which are part of almost every computer application. Sorting algorithms are part of coding classes for kids. This article is about the 5 best sorting algorithms explained to kids in an easy and simple way.
What is Sorting?
Sorting means arranging the items in a list in order. The items in a list can be numerical, alphabetical, or lexicographical. This order can be either ascending or descending.
- Ascending Order is arranging the items from lowest to highest. 0 to 9 in case of numbers and A to Z in case of alphabets.
- Descending Order is arranging the items from highest to highest. 9 to 0 in case of numbers and Z to A in case of alphabets.
In the case of lexicographical order (a, b) < (c, d), if and only if a < c and b < d. Similarly, (a, b) > (c, d), if and only if a > c and b > d.
In computers, sorting can be done on names, numbers, and records.
What is a Sorting Algorithm?
A sorting algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of the element in the respective data structure. The comparison order can be < (less than) or >(greater than).
For example, if we want to arrange 45 and 23 in ascending order, the process will be
If 45 > 23 then interchange the positions else do nothing.
Similarly, we want to arrange 45 and 23 in descending order, the process will be
If 45 < 23 then interchange the positions else do nothing.
Why Do We Need Sorting Algorithms?
Sorting reduces the time needed to process the data and get information. For example, it is relatively easy to look up the phone number of a friend from a telephone directory because the names in it have been sorted into alphabetical order.
This example clearly illustrates one of the main reasons that sorting large quantities of information is desirable. That is, sorting greatly improves the efficiency of searching. This considerably decreases the computer’s processing time. Efficient sorting is important to optimize the use of other algorithms!
Types of Sorting
Classification of sorting algorithms is done on the basis of the following parameters:
- Computational complexity (worst, average and best behaviour) in terms of the size of the list (n). Typically, good behaviour is O(n log n) and bad behaviour is Ω(n2). Ideal behaviour for a sort is O(n).
- Memory usage (and use of other computer resources). Algorithms using less memory space usually run faster than those using more memory.
- Stability: Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.
- The general method used to perform the sorting like Insertion, Exchange, Selection, Merging, etc.
5 Best Sorting Algorithms Explained to Kids
Depending on the method used in sorting, these algorithms are of the following types:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Quick Sort
- Merge Sort
To understand the working of these algorithms, let’s consider arranging numbered cards in ascending order.
Bubble Sort
You lay all the cards in a line. Now, start from one end. Is the first card of a smaller value than the second? Then leave them as it is. If not, interchange their positions.
Next look at the second and the third card. Here also repeat the previous process. Is the second card of a smaller value than the third? Then leave them as it is. If not, interchange their positions.
Repeat the process with the next pair of cards. When you hit the end of the line, go back to the beginning and repeat the process. Keep doing this until you go through the line and never interchange two cards. In this process, the maximum number of times you repeat the process is equal to the number of cards.
Algorithm for Bubble Sort
Step 1: Starting with the first element(index = 0), compare the current element with the next element of the array.
Step 2: If the current element is greater than the next element of the array, swap them.
Step 3: If the current element is less than the next element, move to the next element. Repeat Step 1.
Code for Bubble Sort in C++
void swapping(int &a, int &b) {
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void bubbleSort(int *array, int size) {
for(int i = 0; i<size; i++) {
int swaps = 0;
for(int j = 0; j<size-i-1; j++) {
if(array[j] > array[j+1]) {
swapping(array[j], array[j+1]);
swaps = 1;
}
}
if(!swaps)
break;
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n];
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
bubbleSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
Insertion Sort
Imagine you are holding the cards in your hand, and these cards are sorted. The dealer hands you exactly one new card. The new card could be smaller than some cards you are already holding, and so you go down the line, comparing the new card against each card in your hand until you find the place to put it. You insert the new card in the right place, and once again, your hand holds a fully sorted card.
Then the dealer gives you another card, and you repeat the same procedure. Then another card, and so on, until the dealer stops giving you cards.
Algorithm for Insertion Sort
Step 1: Iterate from arr[1] to arr[n] over the array.
Step 2: Compare the current element (key) to its predecessor.
Step 3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Code for Insertion Sort in C++
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void insertionSort(int *array, int size) {
int key, j;
for(int i = 1; i<size; i++) {
key = array[i];
j = i;
while(j > 0 && array[j-1]>key) {
array[j] = array[j-1];
j--;
}
array[j] = key;
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n];
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
insertionSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
Selection Sort
Lay the cards again. Start at one end. Look at the first card. Remember that number.
Now, look at the second card. Does it have a smaller number? Then start remembering the second number instead of the first number. Otherwise, just remember the first number.
After that go to the third card. Does it have a smaller value? If so, remember this value instead. If not, remember the old value. Keep doing this until you reach the end of the line. Now you have the smallest value card. Put the card first. Now do this again, but instead of starting from the first position, start from the second.
Repeat this process until you are starting with the last card in the line. At this point, you have sorted the cards in ascending order.
Algorithm for Selection Sort
Step 1: Set MIN to location 0
Step 2: Search the minimum element in the list
Step 3: Swap with value at location MIN
Step 4: Increment MIN by 1 and Goto Step 2
Step 5: Exit
Code for Selection Sort in C++
void swapping(int &a, int &b) {
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void selectionSort(int *array, int size) {
int i, j, imin;
for(i = 0; i<size-1; i++) {
imin = i;
for(j = i+1; j<size; j++)
if(array[j] < array[imin])
imin = j;
swap(array[i], array[imin]);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n];
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
selectionSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);Quick Sort
Lay out the cards in a line. Pick a card at random. Now place all cards with a value greater than the randomly selected card to the right side and place all cards with a value lesser than the randomly selected card to the left side.
Now go to one of the sides and pick a card at random and place all the cards with a greater value than the randomly selected card to the right side and place all cards with value lesser than the randomly selected card to the left side.
Continue doing this until all the cards are sorted.
Algorithm for Quick Sort
Step 1: Make any element as pivot
Step 2: Partition the array on the basis of pivot
Step 3: Apply quick sort on left partition recursively
Step 4: Apply quick sort on right partition recursively
Code for Quick Sort in C++
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int Partition(int a[], int l, int h) {
int pivot, index, i;
index = l;
pivot = h;
for(i = l; i < h; i++) {
if(a[i] < a[pivot]) {
swap(&a[i], &a[index]);
index++;
}
}
swap(&a[pivot], &a[index]);
return index;
}
int RandomPivotPartition(int a[], int l, int h) {
int pvt, n, temp;
n = rand();
pvt = l + n%(h-l+1);
swap(&a[h], &a[pvt]);
return Partition(a, l, h);
}
int QuickSort(int a[], int l, int h) {
int pindex;
if(l < h) {
pindex = RandomPivotPartition(a, l, h);
QuickSort(a, l, pindex-1);
QuickSort(a, pindex+1, h);
}
return 0;
}
int main() {
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++) {
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
QuickSort(arr, 0, n-1);
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}
Merge Sort
Lay out the cards in a line. Split the line in half. Then each half in half. Keep doing this until you have only pairs of cards. Sort the pairs. Then group two pairs together into groups of four. Sort the group of four. Keep doing this until you are back to the full length of cards.
Algorithm for Merge Sort
Step 1: If it is only one element in the list it is already sorted, return
Step 2: Divide the list recursively into two halves until it can no more be divided
Step 3: Merge the smaller lists into a new list in sorted order
Code for Merge Sort in C++
void swapping(int &a, int &b) {
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void merge(int *array, int l, int m, int r) {
int i, j, k, nl, nr;
nl = m-l+1; nr = r-m;
int larr[nl], rarr[nr];
for(i = 0; i<nl; i++)
larr[i] = array[l+i];
for(j = 0; j<nr; j++)
rarr[j] = array[m+1+j];
i = 0; j = 0; k = l;
while(i < nl && j<nr) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
}else{
array[k] = rarr[j];
j++;
}
k++;
}
while(i<nl) {
array[k] = larr[i];
i++; k++;
}
while(j<nr) {
array[k] = rarr[j];
j++; k++;
}
}
void mergeSort(int *array, int l, int r) {
int m;
if(l < r) {
int m = l+(r-l)/2;
mergeSort(array, l, m);
mergeSort(array, m+1, r);
merge(array, l, m, r);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n];
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
mergeSort(arr, 0, n-1);
cout << "Array after Sorting: ";
display(arr, n);
}
