Sorting In Data Structure And Algorithms, Code, Working, Types Of Sorting

October 28, 2020February 21, 2022 CS Electrical And Electronics

Hello guys, welcome back to my blog. In this article, I will discuss sorting in data structure and algorithms, code for sorting, types of sorting, working of each sorting in the data structure.

If you need an article on some other topics then comment us below in the comment box. You can also catch me @ Instagram – Chetan Shidling.

Also, read:

Sorting In Data Structure And Algorithms

Sorting involves managing the elements of an array so that all are placed in some proper order which may be both ascending or descending. A sorting algorithm is specified as an algorithm that sets the elements of a list in a particular order, which can occur either numerical order, lexicographical order, or a user-defined order.

There are two kinds of sorting:

Internal sorting means sorting the data collected in the computer’s memory
External sorting means sorting the data collected in files. External sorting is used when there is abundant data that cannot be stored in the memory.

The various algorithms used for sorting are:

Bubble sort
Insertion sort
Selection sort
Merge sort
Quick sort
Radix sort
Heap sort
Shell sort
Tree sort

01. Bubble Sort

Bubble sort is a very easy method that sorts the array components by regularly moving the largest element to the highest index position of the array segment (in fact of arranging elements in ascending order). In bubble sorting, consecutive adjacent pairs of elements in the array are compared by each other. If the component at the lower index is greater than the component at the higher index, the two elements are interchanged so that the component is placed before the bigger one. This process will remain till the list of unsorted elements exhausts.

Let’s see how bubble sort works.

A[] = {30, 52, 29, 87, 63, 27, 19, 54}

Step 1:

(a) Compare 30 and 52. Since 30 < 52, no swapping is done.

(b) Compare 52 and 29. Since 52 > 29, swapping is done. 30, 29, 52, 87, 63, 27, 19, 54

(d) Compare 87 and 63. Since 87 > 63, swapping is done. 30, 29, 52, 63, 87, 27, 19, 54

(e) Compare 87 and 27. Since 87 > 27, swapping is done. 30, 29, 52, 63, 27, 87, 19, 54

(f) Compare 87 and 19. Since 87 > 19, swapping is done. 30, 29, 52, 63, 27, 19, 87, 54

(g) Compare 87 and 54. Since 87 > 54, swapping is done. 30, 29, 52, 63, 27, 19, 54, 87

Observe that after the end of the first step, the largest element is placed at the highest index of the array. All the other elements are still unsorted.

Step 2:

(a) Compare 30 and 29. Since 30 > 29, swapping is done. 29, 30, 52, 63, 27, 19, 54, 87

(b) Compare 30 and 52. Since 30 < 52, no swapping is done.

(d) Compare 63 and 27. Since 63 > 27, swapping is done. 29, 30, 52, 27, 63, 19, 54, 87

(e) Compare 63 and 19. Since 63 > 19, swapping is done. 29, 30, 52, 27, 19, 63, 54, 87

(f) Compare 63 and 54. Since 63 > 54, swapping is done. 29, 30, 52, 27, 19, 54, 63, 87

Observe that after the end of the second step, the second largest element is placed at the second-highest index of the array. All the other elements are still unsorted.

Step 3:

(a) Compare 29 and 30. Since 29 < 30, no swapping is done.

(b) Compare 30 and 52. Since 30 < 52, no swapping is done.

(d) Compare 52 and 19. Since 52 > 19, swapping is done. 29, 30, 27, 19, 52, 54, 63, 87

(e) Compare 52 and 54. Since 52 < 54, no swapping is done.

Observe that after the end of the third step, the third-largest element is placed at the third-highest index of the array. All the other elements are still unsorted.

Step 4:

(a) Compare 29 and 30. Since 29 < 30, no swapping is done.

(b) Compare 30 and 27. Since 30 > 27, swapping is done. 29, 27, 30, 19, 52, 54, 63, 87

(d) Compare 30 and 52. Since 30 < 52, no swapping is done.

Observe that after the end of the fourth step, the fourth largest element is placed at the fourth-highest index of the array. All the other elements are still unsorted.

Step 5:

(a) Compare 29 and 27. Since 29 > 27, swapping is done. 27, 29, 19, 30, 52, 54, 63, 87

(b) Compare 29 and 19. Since 29 > 19, swapping is done. 27, 19, 29, 30, 52, 54, 63, 87

Observe that after the end of the fifth step, the fifth-largest element is placed at the fifth-highest index of the array. All the other elements are still unsorted.

Step 6:

(a) Compare 27 and 19. Since 27 > 19, swapping is done. 19, 27, 29, 30, 52, 54, 63, 87

(b) Compare 27 and 29. Since 27 < 29, no swapping is done.

Observe that after the end of the sixth step, the sixth-largest element is placed at the sixth-largest index of the array. All the other elements are still unsorted.

Step 7:

(a) Compare 19 and 27. Since 19 < 27, no swapping is done.

Algorithm for bubble sort

Step 1: Repeat Step 2 For 1=0 to N-1
Step 2: Repeat For J=0 to N-I
Step 3: IF A[J] > A[J+1]
        SWAP A[J] and A[J+1]
        [END OF INNER LOOP]
        [END OF OUTER LOOP]
Step 4: EXIT

The complexity of the bubble sort algorithm is O(n2). It indicates the time needed to execute bubble sort is proportional to n2, where n is the total number of elements in the array.

Program for bubble sorting in data structure and algorithms?

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i, n, temp, j, arr[10];
    printf("Enter the maximum components or elements you want to store : ");
    scanf("%d", &n);
    printf("Enter the components or elements you want to store\n");
    for(i=0;i<n;i++)
    {
        scanf("%d", & arr[i]);
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n-1;j++)
        {
            if(arr[j]>arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    printf("The array sorted in ascending order is :\n");
    for(i=0;i<n;i++)
        printf("%d\t", arr[i]);
    getch();
    return 0;
}

Output:

Enter the maximum components or elements you want to store : 9
Enter the components or elements you want to store
2
4
5
6
8
7
9
1
3
The array sorted in ascending order is :
1       2       3       4       5       6       7       8       9

02. Insertion sort

Insertion sort is a very easy sorting algorithm in which the sorted array (or list) is made one element at a time. The main idea behind insertion sort is that it inserts each part into its proper place in the final list. To save memory, most implementations of the insertion sort algorithm performance is by moving the current data element past the already sorted values and frequently interchanging it with the preceding value until it is in its correct place. Insertion sort is less effective as compared to other more advanced algorithms such as quicksort, heap sort, and merge sort.

Working of insertion sort

The array of values to be sorted is split into two sets. One that stores sorted values and another that includes unsorted values.
The sorting algorithm will continue until there are elements in the unsorted set.
Assume there are n components in the array. Initially, the component with index 0 (assuming LB = 0) is in the sorted set. The rest of the components are in the unsorted set.
The first component element of the unsorted partition has array index 1 (if LB = 0).
While each iteration of the algorithm, the first element in the unsorted set is picked up and inserted into the correct position in the sorted set.

Program for insertion sorting in data structure?

#include <stdio.h>
#include <stdlib.h>
#define size 5
void insertion_sort(int arr[], int n);
int main()
{
    int arr[size], i, n;
    printf("Enter the number of components in the array :\n");
    scanf("%d",&n);
    printf("Enter the components or elements of the array :\n");
    for(i=0;i<n;i++)
    {
        scanf("%d", &arr[i]);
    }
    insertion_sort(arr, n);
    printf("The sorted array is :\n");
    for(i=0;i<n;i++)
        printf("%d\n", arr[i]);
    getch();
    return 0;
}

void insertion_sort(int arr[], int n)
{
    int i, j, temp;
    for(i=1;i<n;i++)
    {
        temp = arr[i];
        j = i-1;
        while((temp < arr[j]) && (j>=0))
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }
}

Output:

Enter the number of components in the array :
7
Enter the components or elements of the array :
3
65
87
34
420
12
54
The sorted array is :
3
12
34
54
65
87
420

03. Selection Sort

Selection sort is a sorting algorithm that has a quadratic running time complexity of O(n2), whereby making it ineffective to be used on big lists. Although selection sort does worse than the insertion sort algorithm, it is recorded for its simplicity and also has performance benefits over more complicated algorithms in certain circumstances. Selection sort is generally used for sorting files with very large objects (records) and small keys.

Working of selection sort

First, obtain the least value in the array and store it in the first position. Later, get the second least value in the array and put it in the second position. Replicate this procedure until the entire array is sorted. Therefore,

01. In Pass 1, get the position POS of the least value in the array and then swap ARR[POS] and ARR[0]. Thus, ARR[0] is sorted.
02. In Pass 2, get the position POS of the least value in the sub-array of N–1 elements. Swap ARR[POS] with ARR[1]. Now, ARR[0] and ARR[1] is sorted.
03. In Pass N–1, locate the position POS of the smaller of the elements ARR[N–2] and ARR[N–1]. Swap ARR[POS] and ARR[N–2] so that ARR[0], ARR[1], …, ARR[N–1] is sorted.

Program on selection sorting in data structure and algorithms ?

#include <stdio.h>
#include <stdlib.h>
int smallest(int arr[], int k, int n);
void selection_sort(int arr[], int n);
void main(int argc, char *argv[]){
    int arr[10], i, n;
    printf("Enter the number of components or elements :\n");
    scanf("%d", &n);
    printf("Enter the components to store\n");
    for(i=0;i<n;i++)
    {
        scanf("%d", &arr[i]);
    }
    selection_sort(arr, n);
    printf("The sorted array :\n");
    for(i=0;i<n;i++)
        printf("%d\t", arr[i]);
}

int smallest(int arr[], int k, int n)
{
    int pos=k, small=arr[k], i;
    for(i=k;i<n;i++)
    {
        if(arr[i]<small)
        {
            small = arr[i];
            pos = i;
        }
    }
    return pos;
}

void selection_sort(int arr[], int n)
{
    int k, pos, temp;
    for(k=0;k<n;k++)
    {
        pos = smallest(arr, k, n);
        temp = arr[k];
        arr[k] = arr[pos];
        arr[pos] = temp;
    }
}

Output:

Enter the number of components or elements :
7
Enter the components to store
22
1
66
98
57
34
678
The sorted array :
1       22      34      57      66      98      678
Process returned 7 (0x7)   execution time : 10.910 s

04. Merge Sort

Merge sort is a sorting algorithm that practices the divide, conquer, and combine algorithmic model. Divide involves partitioning the n-element array to be sorted in two sub-arrays of n/2 components. If A is an array holding zero or one component, then it is already sorted. But, if there are more components in the array, divide A into two sub-arrays, A1 and A2, all containing about half of the components of A. Conquer involves sorting the two sub-arrays recursively. Combine involves merging the two sorted sub-arrays of size n/2 to provide the sorted array of n elements.

Compare ARR[I] and ARR[J], the smaller of the two is located in TEMP at the position specified by INDEX and consequently the value I or J is incremented.

Program on merge sorting in data structures and algorithms?

#include <stdio.h>
#include <stdlib.h>
#define size 100
void merge(int arr[], int beg, int mid, int end);
void merge_sort(int arr[], int beg, int end);
void main()
{
    int arr[size], i, n;
    printf("Enter the number of components you want to store :\n");
    scanf("%d", &n);
    printf("Enter the components or elements :\n");
    for(i=0;i<n;i++)
    {
        scanf("%d", & arr[i]);
    }
    merge_sort(arr, 0, n-1);
    printf("The stored array is :\n");
    for(i=0;i<n;i++)
        printf("%d\t",arr[i]);
    getch();
}

void merge(int arr[], int beg, int mid, int end)
{
    int i=beg, j=mid+1, index=beg, temp[size], k;
    while((i<=mid) && (j<=end))
    {
        if(arr[i] < arr[j])
        {
            temp[index] = arr[i];
            i++;
        }
        else
        {
            temp[index] = arr[i];
            j++;
        }
        index++;
    }
    if(i>mid)
    {
        while(j<=end)
        {
            temp[index] = arr[j];
            j++;
            index++;
        }
    }
    else
    {
        while(i<mid)
        {
            temp[index] = arr[i];
            i++;
            index++;
        }
    }
    for(k=beg;k<index;k++)
        arr[k] = temp[k];
}
void merge_sort(int arr[], int beg, int end)
{
    int mid;
    if(beg<end)
    {
        mid = (beg+end)/2;
        merge_sort(arr, beg, mid);
        merge_sort(arr, mid+1, end);
        merge(arr, beg, mid, end);
    }
}

Output:

Enter the number of components you want to store :
8
Enter the components or elements :
23
1
67
55
89
45
34
98
The stored array is :
1      23       34      45      55      67      89      98

05. Quick Sort

Quick sort is a broadly used sorting algorithm revealed by C. A. R. Hoare that offers O(n log n) comparisons in the average case to sort an array of n elements. However, in the worst case, it has a quadratic running time given as O(n2). Primarily, the quick sort algorithm is faster than other O(n log n) algorithms, because its effective implementation can reduce the probability of requiring quadratic time. Quick sort is also identified as partition exchange sort.

Quick sort algorithm working

1. Set the index of the first component in the array to loc and left variables. Plus, set the index of the last component of the array to the right variable. That is, loc = 0, left = 0, and right = n–1 (where n is the number of elements in the array)

2. Start from the component pointed by right and scan the array from right to left, comparing each element on the way with the element pointed by the variable loc. That is, a[loc] should be less than a[right]. (a) If that is the case, then simply continue comparing until right becomes equal to loc. Once right = loc, it means the pivot has been located in its right position. (b) However, if at any point, we have a[loc] > a[right], then interchange the two values and jump to Step 3. (c) Set loc = right

3. Start from the component pointed by left and scan the array from left to right, comparing each element on the way with the component pointed by loc. That is, a[loc] should be greater than a[left]. (a) If that is the case, then just continue comparing until the left becomes equal to loc. Once left = loc, it implies the pivot has been located in its correct position. (b) However, if at any point, we have a[loc] < a[left], then interchange the two values and jump to Step 2. (c) Set loc = left.

Program on quick sorting in data structure and algorithms?

#include <stdio.h>
#include <stdlib.h>
#define size 100
int partition(int a[], int beg, int end);
void quick_sort(int a[], int beg, int end);
void main()
{
    int arr[size], i, n;
    printf("Enter the number of components you want to store :\n");
    scanf("%d",&n);
    printf("Enter the components to store :");
    for(i=0;i<n;i++)
    {
        scanf("%d", & arr[i]);
    }
    quick_sort(arr, 0, n-1);
    printf("The sorted array is :\n");
    for(i=0;i<n;i++)
        printf("%d\n",arr[i]);
    getch();
}

int partition(int a[], int beg, int end)
{
    int left, right, temp, loc, flag;
    loc = left = beg;
    right = end;
    flag = 0;
    while(flag != 1)
    {
        while((a[loc] <= a[right]) &&       (loc != right))
            right--;
        if(loc==right)
            flag = 1;
        else if(a[loc]>a[right])
        {
            temp = a[loc];
            a[loc] = a[right];
            a[right] = temp;
            loc = right;
        }
        if(flag!=1)
        {
            while((a[loc] >= a[left]) && (loc!=left))
                left++;
            if(loc==left)
                flag = 1;
            else if(a[loc] < a[left])
            {
                temp = a[loc];
                a[loc] = a[left];
                a[left] = temp;
                loc = left;
            }
        }
    }
    return loc;
}
void quick_sort(int a[], int beg, int end)
{
    int loc;
    if(beg<end)
    {
        loc = partition(a, beg, end);
        quick_sort(a, beg, loc-1);
        quick_sort(a, loc+1, end);
    }
}

Output:

Enter the number of components you want to store :
8
Enter the components to store :23
1
65
54
88
15
76
98
The sorted array is :
1
15
23
54
65
76
88
98

06. Radix Sort

Radix sort is a linear sorting algorithm for integers and does the concept of sorting names in alphabetical order. When we have a list of sorted names, the radix is 26 (or 26 buckets) because there are 26 letters in the English alphabet. So radix sort is also recognized as bucket sort. Observe that words are first sorted according to the first letter of the name. That is, 26 classes are utilized to arrange the names, where the first-class stores the names that start with A, the second class contains the names with B, and so on.

When radix sort is done on integers, sorting is done on each of the digits in the number. The sorting procedure proceeds by sorting the least significant to the most significant digit. While sorting the numbers, we have ten buckets, each for one digit (0, 1, 2, …, 9) and the number of passes will depend on the length of the number having a maximum number of digits.

Let’s take one example.

345, 654, 924, 123, 567, 472, 555, 808, 911 and now sort the elements using radix sort.

In the first step, the numbers are sorted according to the digit at one’s place. The buckets are pictured upside down as given below.

After this step, the numbers are collected bucket by bucket. The new list thus produced is used as an input for the next step. In the second step, the numbers are sorted according to the digit at the tens place. The buckets are pictured upside down.

In the third step, the numbers are sorted according to the digit at the hundreds place. The buckets are pictured upside down.

Final list is 123, 345, 472, 555, 567, 654, 808, 911, 924.

Program on radix sorting in data structures and algorithms?

#include <stdio.h>
#include <stdlib.h>
#define size 100
int largest(int arr[], int n);
void radix_sort(int arr[], int n);
void main()
{
    int arr[size], i, n;
    printf("Enter the numbers of elements you want to store :\n");
    scanf("%d",&n);
    printf("Enter elements\n");
    for(i=0;i<n;i++)
    {
        scanf("%d",& arr[i]);
    }
    radix_sort(arr, n);
    printf("The sorted elements are\n");
    for(i=0;i<n;i++)
        printf("%d\n", arr[i]);
    getch();
}
int largest(int arr[], int n)
{
    int large=arr[0], i;
    for(i=1;i<n;i++)
    {
        if(arr[i]>large)
            large = arr[i];
    }
    return large;
}
void radix_sort(int arr[], int n)
{
    int bucket[size][size], bucket_count[size];
    int i, j, k, remiander, NOP=0, divisor=1, large, pass;
    large = largest(arr, n);
    while(large>0)
    {
        NOP++;
        large/=size;
    }
    for(pass=0;pass<NOP;pass++) //Making buckets
    {
        for(i=0;i<size;i++)
            bucket_count[i] = 0;
        for(i=0;i<n;i++)
        {
            remiander = (arr[i]/divisor)%size;
            bucket[remiander][bucket_count[remiander]] = arr[i];
            bucket_count[remiander] += 1;
        }
        i=0;
        for(k=0;k<size;k++)
        {
            for(j=0;j<bucket_count[k];j++)
            {
                arr[i] = bucket[k][j];
                i++;
            }
        }
        divisor *= size;
    }
}

Output:

Enter the numbers of elements you want to store :
8
Enter elements
23
1
420
65
77
55
97
34
The sorted elements are
1
23
34
55
65
77
97
420

The remaining sorting algorithms I will discuss later, the remaining sorting algorithms are heap, shell, and tree sort. If you want an explanation soon, then comment below.

I hope this article may help you all a lot. Thank you for reading. If you have any doubts related to this article”Sorting in data structure”, then comment below in the comment box.

Also, read: