Binary  Search Tree:

A Binary Search Tree (BST) is a type of data structure that helps in organizing and managing data efficiently. Here’s a simple explanation of its properties and how it works:

What is a Binary Search Tree?

A Binary Search Tree is a tree structure where each node has at most two children, referred to as the left child and the right child. This type of tree has a specific way of arranging data to make searching, insertion, and deletion operations very efficient.

Properties of a Binary Search Tree

1. Node Arrangement:

   • Each node in a BST contains a key (a value).
   • The left subtree of a node contains only nodes with keys that are less than the node’s key.
   • The right subtree of a node contains only nodes with keys that are greater than the node’s key.

2. Subtree Structure:

   • Both the left and right subtrees of each node must also be binary search trees. This means the rules for arranging nodes apply to every subtree within the tree.

How Does It Work?

Consider you have a BST, and you want to find a particular value. You start at the root node:

• Searching:

  • If the value you are searching for is less than the root’s key, you move to the left child.
  • If it is greater, you move to the right child.
  • You repeat this process until you find the value or reach a leaf node (a node with no children).

• Insertion:

  • To insert a new value, you follow the same logic as searching.
  • Starting at the root, you move left or right depending on whether the new value is less than or greater than the current node’s key.
  • When you find an appropriate empty spot (where a child node would be null), you insert the new value there.

• Deletion:

  • Deleting a node from a BST requires a bit more thought:
    • If the node is a leaf, you can simply remove it.
    • If the node has one child, you remove the node and replace it with its child.
    • If the node has two children, you need to find the in-order successor (the smallest node in the right subtree) or the in-order predecessor (the largest node in the left subtree), replace the node's key with this successor’s (or predecessor’s) key, and then delete the successor (or predecessor)

Inorder Traversal:

At first traverse left subtree then visit the root and then traverse the right subtree.

Follow the below steps to implement the idea:

·         Traverse left subtree

·         Visit the root and print the data.

·         Traverse the right subtree

Program:

// C++ code to implement the approach

 //Inorder

#include <bits/stdc++.h>

using namespace std;

// Class describing a node of tree

class Node {

public:

    int data;

    Node* left;

    Node* right;

    Node(int v)

    {

        this->data = v;

        this->left = this->right = NULL;

    }

};

// Inorder Traversal

void printInorder(Node* node)

{

    if (node == NULL)

        return;

    // Traverse left subtree

    printInorder(node->left);

    // Visit node

    cout << node->data << " ";

    // Traverse right subtree

    printInorder(node->right);

}

// Driver code

int main()

{

    // Build the tree

    Node* root = new Node(100);

    root->left = new Node(20);

    root->right = new Node(200);

    root->left->left = new Node(10);

    root->left->right = new Node(30);

    root->right->left = new Node(150);

    root->right->right = new Node(300);

    // Function call

    cout << "Inorder Traversal: ";

    printInorder(root);

    return 0;

}

 Output:

Radix sort:

Understanding Radix Sort: A Linear Sorting Algorithm

Radix Sort is a fascinating and efficient sorting algorithm, especially suitable for sorting integers or strings with fixed-size keys. Unlike traditional comparison-based sorting algorithms like QuickSort or MergeSort, Radix Sort processes elements by their individual digits, achieving linear time complexity under certain conditions.

How Radix Sort Works

Radix Sort sorts elements by distributing them into buckets based on each digit's value. It processes the elements digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). This method ensures that the elements are sorted in their correct order by the end of the process.

Here's a step-by-step breakdown of how Radix Sort works:

1. Identify the Maximum Number of Digits: Determine the maximum number of digits (d) in the largest number or longest string in the list. This step ensures that the algorithm knows how many passes it needs to make.

2. Sorting by Each Digit: For each digit, from the least significant to the most significant:

   • Distribute the elements into buckets based on the current digit's value.
   • Collect the elements from the buckets and reconstruct the list. This process is repeated for each digit until all digits have been processed.

Example: Radix Sort in Action

Let's illustrate Radix Sort with a simple example. Suppose we want to sort the following list of integers:

List = [170, 45, 75, 90, 802, 24, 2, 66]

1. Identify the Maximum Number of Digits: The maximum number in the list is 802, which has 3 digits. So, we need to make 3 passes (one for each digit).

2. First Pass (Least Significant Digit):

   • Distribute the numbers into buckets based on the units place (LSD):

     
     
     0-9 Buckets: [170, 90, 802, 2], [45], [75], [24], [66]
     

   • Reconstruct the list: List = [170, 90, 802, 2, 45, 75, 24, 66]

3. Second Pass (Tens Digit):

   • Distribute the numbers into buckets based on the tens place:

     
     
     0-9 Buckets: [802, 2], [24], [45], [66, 75, 170, 90]
     

   • Reconstruct the list: List = [802, 2, 24, 45, 66, 75, 170, 90]

4. Third Pass (Most Significant Digit):

   • Distribute the numbers into buckets based on the hundreds place:

     
     0-9 Buckets: [2, 24, 45, 66, 75, 90], [170], [802]
     

   • Reconstruct the list: List = [2, 24, 45, 66, 75, 90, 170, 802]

After these passes, the list is sorted in ascending order.

Why Use Radix Sort?

Radix Sort is particularly useful when:

• The range of input values is known and not too large.
• The keys are of fixed size, such as integers or strings of uniform length.
• A stable sorting algorithm is required, as Radix Sort maintains the relative order of elements with equal keys.

This explanation provides a clear and human-readable overview of how Radix Sort operates, including a detailed example to illustrate its process.

Program:

#include <iostream>

using namespace std;

// A utility function to get maximum

// value in arr[]

int getMax(int arr[], int n)

{

    int mx = arr[0];

    for (int i = 1; i < n; i++)

        if (arr[i] > mx)

            mx = arr[i];

    return mx;

}

// A function to do counting sort of arr[]

// according to the digit

// represented by exp.

void countSort(int arr[], int n, int exp)

{

    // Output array

    int output[n];

    int i, count[10] = { 0 };

    // Store count of occurrences

    // in count[]

    for (i = 0; i < n; i++)

        count[(arr[i] / exp) % 10]++;

    // Change count[i] so that count[i]

    // now contains actual position

    // of this digit in output[]

    for (i = 1; i < 10; i++)

        count[i] += count[i - 1];

    // Build the output array

    for (i = n - 1; i >= 0; i--) {

        output[count[(arr[i] / exp) % 10] - 1] = arr[i];

        count[(arr[i] / exp) % 10]--;

    }

    // Copy the output array to arr[],

    // so that arr[] now contains sorted

    // numbers according to current digit

    for (i = 0; i < n; i++)

        arr[i] = output[i];

}

// The main function to that sorts arr[]

// of size n using Radix Sort

void radixsort(int arr[], int n)

{

    // Find the maximum number to

    // know number of digits

    int m = getMax(arr, n);

    // Do counting sort for every digit.

    // Note that instead of passing digit

    // number, exp is passed. exp is 10^i

    // where i is current digit number

    for (int exp = 1; m / exp > 0; exp *= 10)

        countSort(arr, n, exp);

}

// A utility function to print an array

void print(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

// Driver Code

int main()

{

    int arr[] = { 543, 986, 217, 765, 329 };

    int n = sizeof(arr) / sizeof(arr[0]);

    // Function Call

    radixsort(arr, n);

    print(arr, n);

    return 0;

}

Output:

Quick Sort

QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.

How does QuickSort work?

The key process in quickSort is a partition(). The target of partitions is to place the pivot (any element can be chosen to be a pivot) at its correct position in the sorted array and put all smaller elements to the left of the pivot, and all greater elements to the right of the pivot.

Partition is done recursively on each side of the pivot after the pivot is placed in its correct position and this finally sorts the array.

Program:

#include <bits/stdc++.h>

using namespace std;

int partition(int arr[],int low,int high)

{

  //choose the pivot

  int pivot=arr[high];

  //Index of smaller element and Indicate

  //the right position of pivot found so far

  int i=(low-1);

  for(int j=low;j<=high;j++)

  {

    //If current element is smaller than the pivot

    if(arr[j]<pivot)

    {

      //Increment index of smaller element

      i++;

      swap(arr[i],arr[j]);

    }

  }

  swap(arr[i+1],arr[high]);

  return (i+1);

}

// The Quicksort function Implement

void quickSort(int arr[],int low,int high)

{

  // when low is less than high

  if(low<high)

  {

    // pi is the partition return index of pivot

    int pi=partition(arr,low,high);

    //Recursion Call

    //smaller element than pivot goes left and

    //higher element goes right

    quickSort(arr,low,pi-1);

    quickSort(arr,pi+1,high);

  }

}

int main() {

  int arr[]={10,7,8,9,1,5};

  int n=sizeof(arr)/sizeof(arr[0]);

  // Function call

  quickSort(arr,0,n-1);

  //Print the sorted array

  cout<<"Sorted Array\n";

  for(int i=0;i<n;i++)

  {

    cout<<arr[i]<<" ";

  }

  return 0;

}

Output:

Merge sort:

 Merge sort is a sorting technique based on divide and conquer technique. Merge sort first divides the array into equal halves and then combines them in a sorted manner.  

Steps of Merge Sort:

1. Divide: Split the array into two halves.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves to produce the sorted array.

Detailed Process:

1. Splitting the Array:

   • If the array has one or zero elements, it is already sorted.
   • Otherwise, split the array into two halves.

2. Recursively Sorting Each Half:

   • Apply merge sort recursively to each half.

3. Merging the Sorted Halves:

   • Compare the elements of the two halves and merge them into a single sorted array.

Program:

#include <iostream>

#define max 10

using namespace std;

int a[10] = { 14 , 33 , 27 , 10 , 35 , 19 , 42 , 44  };

int b[10];

void merging(int low, int mid, int high)

{

 int l1, l2, i;

 for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {

 if(a[l1] <= a[l2])

 b[i] = a[l1++];

 else

 b[i] = a[l2++];

 }

 while(l1 <= mid)

 b[i++] = a[l1++];

 while(l2 <= high)

 b[i++] = a[l2++];

 for(i = low; i <= high; i++)

 a[i] = b[i];

}

void sort(int low, int high)

{

 int mid;

 if(low < high) {mid = (low + high) / 2;

 sort(low, mid);

 sort(mid+1, high);

 merging(low, mid, high);

 }

 else

 {

 return; }

}

int main()

 {

 int i;

 cout<<("List before sorting\n");

 for(i = 0; i <= max; i++)

 cout<<a[i]<<"  ";

 sort(0, max);

 cout<<"\nList after sorting\n";

 for(i = 0; i <= max; i++)

 cout<<a[i]<<"  "; 

}

Output:      

Insertion sort:

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heap sort, or merge sort

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'inserted in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n²), where n is the number of items.

Basic Operation:

Ø  First we take an unsorted array for our example.

 Ø  Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub list.

Ø  Finds that 33 is not in the correct position.

Ø  It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping.

Ø  By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

Ø  However, swapping makes 27 and 10 unsorted.

Hence, we swap them too.

Ø  Again we find 14 and 10 in an unsorted order.

 Ø  We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items.

Program:

#include <bits/stdc++.h>

using namespace std;

// Function for Insertion sort

void insertionSort(int arr[], int n)

{  int i, key, j;

    for (i = 1; i < n; i++)

    {

        key = arr[i];

        j = i - 1;

        // Move elements of arr[0..i-1] that are greater than key

        // to one position ahead of their current position

        while (j >= 0 && arr[j] > key)

        {

            arr[j + 1] = arr[j];

            j = j - 1;

        }

        arr[j + 1] = key;

    }

}

// Function to print an array

void printArray(int arr[], int size)

{

    int i;

    for (i = 0; i < size; i++)

    {

        cout << arr[i] << " ";

    }

    cout << endl;

}

// Driver program

int main()

{

    int arr[] = {64, 25, 12, 22, 11};

    int n = sizeof(arr) / sizeof(arr[0]);

    // Function Call

    insertionSort(arr, n);

    cout << "Sorted array: \n";

    printArray(arr, n);

    return 0;}

Output: