Sorting Algorithms in Data Structure

Sorting is a process of arranging information either in ascending or in descending order of key values. In data structures there are techniques available to sort the data.

Types of sorting algorithms

  • Bubble sort
  • Insertion sort
  • Selection sort
  • Quick sort
  • Radix sort
  • Merge sort

 

1. Bubble Sort

It is one of the simplest & popular sorting method. The basic idea of this sorting is that in each pass we have to compare a successive pair of element i.e. a[i] & a[i+1]. Interchange these two values, if they are not place in proper order. Place the element in it's correct position in each pass. In first pass largest element is shifted at bottom. In second pass second largest will be shifted to the second last position & so on. Thus to sort n values n-1 passes are required.
Algorithm
Bubble Sort

Step 1: Start
Step 2: Set 1 to pass
Step 3: Set o to i
Step 4: if a[i]> a[i+1] then, Swap a[i] & a[i+1]
Step 5: Add I to i.
Step 6: If i<n-pass, then go to step 4
Step 7: Add 1 to pass.
Step 8: If pass<n then, go to step 3
Step 9: Stop
Source Code (Bubble Sort)
#include <stdio.h>

// To print the array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
void bubbleSort(int arr[], int n)
{
    for (int pass = 1; pass < n; pass++)
    {
        printf("Pass %d executed.\n", pass);
        for (int i = 0; i < n - pass; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
    }
}
void main()
{
    int arr[] = {3, 56, 45, 23, 67, 46, 1, 2, 89, 10};
    int n = 10;
    printArray(arr, n);
    bubbleSort(arr, n);
}

Output

Original Array : 3 56 45 23 67 46 1 2 89 10
Sorted Array : 1 2 3 10 23 45 46 56 67 89

Source Code (Adaptive Bubble Sort)
#include <stdio.h>

// To print the array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
/* Adaptive means, if  in any pass array gets sorted then function will be retured and other passes will not get executed. */
void bubbleSortAdaptive(int arr[], int n)
{
    int isSorted = 0;
    for (int pass = 1; pass < n; pass++)
    {
        printf("Pass %d executed.\n", pass);
        printf("After Pass : %d\n", pass);
        isSorted = 1;
        for (int i = 0; i < n - pass; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                printArray(arr, n);
                isSorted = 0;
            }
        }
        if (isSorted)
        {
            return;
        }
    }
}
void main()
{
    int arr[] = {3, 56, 45, 23, 67, 46, 1, 2, 89, 10};
    int n = 10;
    printArray(arr, n);
    bubbleSortAdaptive(arr, n);
    printArray(arr, n);
}

Output

Original Array : 3 56 45 23 67 46 1 2 89 10
Sorted Array : 1 2 3 10 23 45 46 56 67 89
 

2. Insertion Sort
The main idea of this Sorting is to place unsorted element in its correct position from a list of unsorted data. When new element is to be inserted in a list, first find out its position & the elements from this position shift one position to the right to create a new place. For new element.
Algorithm
Insertion Sort

Step 1: Start
Step 2: Set 1 to us
Step 3: Set a[us] to new
Step 4: Set us-1 to sp
Step 5: if a[sp]> new & sp>=0 then, store a[sp] in a[sp+1]
Step 6: Subtract 1 from sp and repeat step 5
Step 7: Store new in a[sp+1]
Step 8: Add 1 to us.
Step 9: If us<n then, go to step 3
Step 10:Stop


Source Code (Insertion Sort)
#include <stdio.h>

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
void insertionSort(int arr[], int n)
{
    for (int pass = 1; pass < n; pass++)
    {
        int key = arr[pass];
        int j = pass - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
void main()
{
    int arr[] = {3, 5, 56, 7, 23, 34, 1, 38, 6, 90};
    int n = 10;
    printArray(arr, n);
    insertionSort(arr, n);
    printArray(arr, n);
}

Output

Original Array : 3 5 56 7 23 34 1 38 6 90
Sorted Array : 1 3 5 6 7 23 34 38 56 90

 


3. Selection Sort

It is a sorting in which successive elements are selected in order and place into their proper sorted position. In this case, in pass one first find out the smallest element from a[1], a[2] ,...a[n-1] & interchange it with a[0]. It means this interchange places smallest element in the first position. Similarly in 2nd pass find out second smallest from a[2], a[3],...a[n-1] & place at a[1]. The process of locating smallest element continues until all elements are in sorted order. If there are 'n' elements, then 'n-1' passes are required.
Source Code (Selection Sort)
#include <stdio.h>

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
void selectionSort(int arr[], int n)
{
    int min;
    for (int i = 0; i < n; i++)
    {
        min = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
        printf("After Pass : %d\n", i + 1);
        printArray(arr, n);
    }
}
void main()
{
    int arr[] = {3, 5, 56, 7, 23, 34, 1, 38, 6, 90};
    int n = 10;
    printArray(arr, n);
    selectionSort(arr, n);
    printArray(arr, n);
}

Output

Original Array : 3 5 56 7 23 34 1 38 6 90
Sorted Array : 1 3 5 6 7 23 34 38 56 90

Comments

Post a Comment

Popular posts from this blog

Searching Algorithms in Data Structure

Searching is a process of retriving or locating or finding information matching with some specific value. In data structure there are two types of searching. Linear or sequencial search Binary search   Linear or Sequencial Search It is a simplest form of searching and can be applied for sequencial storage such as array, stack, queue, linked list. Algorithm Linear/Sequencial Search Step 1: Start Step 2: Set 0 to i Step 3: Read and store value to search in val Step 4: if a(i) = val, print value is found at (i+1) position and go to step 8 Step 5: Set i to i + 1 Step 6: If i is less than n then, go to Step 4 Step 7: Print element not found Step 8: Stop n - size of array a - array val - value to be searched in array Source Code #include <stdio.h> #include <conio.h> #include <stdlib.h> int main() { int n; printf("Enter the size of array : "); scanf("%d", &n); int arr[n]; for...
Read more

Circular Linked List

Image
I n a Circular Linked List the first and the last elements are adjacent. A linked list can be made circular by storing the address of the first node in the next field of the last node. In a circular linked list, last node is connected back to the first node. In some applications, it is convenient to use circular linked list. A queue data structure can be implemented using a circular linked list, with a single pointer "rear" as the front node can be accessed through the rear node. Implementation of Circular Linked List Circular Linked List Creation and Traversal Algorithm for traversing a circular list is slightly different than the same algorithm for a singly linked list because "NULL" is not encountered. Source Code (Circular Linked List Creation and Traversal) #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; void CircularLinkedListTraversal(stru...
Read more