How does the Bucket Sort Algorithm work?

•  Suppose the input array is:

Bucket Sort Algorithm

algorithm for bucket sort

• Insert items into buckets from the array. the weather are inserted consistent with the reach of the bucket.

Bucket sort

• In our code example, we've compartments each of which matches from 0 to 1, 1 to 2, 2 to 3, ...... (n-1) to n.

• Suppose an input element of .23 is taken. it's multiplied by the dimensions = 10 (i.e. .23 * 10 = 2.3). Then, it's converted to an integer (i.e. 2.3≈2). Finally, .23 is inserted into bucket-2.

sorting algorithms

• Items in each compartment are sorted using one among the stable sorting algorithms. Here we've used quicksort (built-in function).

bucket sort in c

• The elements of every bucket are put together.

bucket sort algorithm

bucket sort complexity

•  Worst-case complexity: O (n2)

•  Best case complexity: O (n + k)

•  Average complexity of cases: O (n)

Bucket Sort Algorithm

Bucket Sort Algorithm

Bucket sort program in c programming

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

#define NARRAY 7   
#define NBUCKET 6  
#define INTERVAL 10  

struct Node {
  int data;
  struct Node *next;
};

void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);

// Sorting function
void BucketSort(int arr[]) {
  int i, j;
  struct Node **buckets;

  // Create buckets and allocate memory size
  buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);

  // Initialize empty buckets
  for (i = 0; i < NBUCKET; ++i) {
    buckets[i] = NULL;
  }

  // Fill the buckets with respective elements
  for (i = 0; i < NARRAY; ++i) {
    struct Node *current;
    int pos = getBucketIndex(arr[i]);
    current = (struct Node *)malloc(sizeof(struct Node));
    current->data = arr[i];
    current->next = buckets[pos];
    buckets[pos] = current;
  }

  // Print the buckets along with their elements
  for (i = 0; i < NBUCKET; i++) {
    printf("Bucket[%d]: ", i);
    printBuckets(buckets[i]);
    printf("\n");
  }

  // Sort the elements of each bucket
  for (i = 0; i < NBUCKET; ++i) {
    buckets[i] = InsertionSort(buckets[i]);
  }

  printf("-------------\n");
  printf("Bucktets after sorting\n");
  for (i = 0; i < NBUCKET; i++) {
    printf("Bucket[%d]: ", i);
    printBuckets(buckets[i]);
    printf("\n");
  }

  // Put sorted elements on arr
  for (j = 0, i = 0; i < NBUCKET; ++i) {
    struct Node *node;
    node = buckets[i];
    while (node) {
      arr[j++] = node->data;
      node = node->next;
    }
  }

  return;
}

// Function to sort the elements of each bucket
struct Node *InsertionSort(struct Node *list) {
  struct Node *k, *nodeList;
  if (list == 0 || list->next == 0) {
    return list;
  }

  nodeList = list;
  k = list->next;
  nodeList->next = 0;
  while (k != 0) {
    struct Node *ptr;
    if (nodeList->data > k->data) {
      struct Node *tmp;
      tmp = k;
      k = k->next;
      tmp->next = nodeList;
      nodeList = tmp;
      continue;
    }

    for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
      if (ptr->next->data > k->data)
        break;
    }

    if (ptr->next != 0) {
      struct Node *tmp;
      tmp = k;
      k = k->next;
      tmp->next = ptr->next;
      ptr->next = tmp;
      continue;
    } else {
      ptr->next = k;
      k = k->next;
      ptr->next->next = 0;
      continue;
    }
  }
  return nodeList;
}

int getBucketIndex(int value) {
  return value / INTERVAL;
}

void print(int ar[]) {
  int i;
  for (i = 0; i < NARRAY; ++i) {
    printf("%d ", ar[i]);
  }
  printf("\n");
}

// Print buckets
void printBuckets(struct Node *list) {
  struct Node *cur = list;
  while (cur) {
    printf("%d ", cur->data);
    cur = cur->next;
  }
}

// Driver code
int main(void) {
  int array[NARRAY] = {42, 32, 33, 52, 37, 47, 51};

  printf("Initial array: ");
  print(array);
  printf("-------------\n");

  BucketSort(array);
  printf("-------------\n");
  printf("Sorted array: ");
  print(array);
  return 0;
}

Applications For the Bucket sort Algorithm

•  the entry is evenly distributed over a variety.
   there are floating-point values

How does the count sort Algorithm work?

•  Find the utmost element (be it max) from the given array.

counting sort in c

• Initialize an array of max length + 1 with all 0 elements. This array is employed to store the number of elements within the array.

count sort algorithm

• Store the amount of every element at their respective index within the count array

count sort algorithm

• Store the cumulative sum of things within the count array. This helps to put the weather within the correct index of the sorted array.

counting sort

• Find the index of every element within the original array within the count array. this provides the cumulative count. Place the element at the calculated index as shown within the figure below.

counting sort algorithm in c programming

• After placing each item in its correct position, decrease its number by one

Counting Sort Algorithm

Counting Sort Algorithm

// Counting sort in C programming

#include <stdio.h>

void countingSort(int array[], int size) {
  int output[10];

  // Find the largest element of the array
  int max = array[0];
  for (int i = 1; i < size; i++) {
    if (array[i] > max)
      max = array[i];
  }

  int count[10];

  // Initialize count array with all zeros.
  for (int i = 0; i <= max; ++i) {
    count[i] = 0;
  }

  // Store the count of each element
  for (int i = 0; i < size; i++) {
    count[array[i]]++;
  }

  for (int i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }


  for (int i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }

 
  for (int i = 0; i < size; i++) {
    array[i] = output[i];
  }
}

void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}


int main() {
  int array[] = {4, 2, 2, 8, 3, 3, 1};
  int n = sizeof(array) / sizeof(array[0]);
  countingSort(array, n);
  printArray(array, n);
}

counting sort of time complexity

•  Worst case complexity: O (n + k)
•  Best case complexity: O (n + k)
•  Average complexity of cases: O (n + k)

Space complexity For counting sort algorithm:

Counting sorting Applications

•  there are smaller integers with multiple counts.

•  linear complexity is the need.

How the QuickSort Algorithm Works?

•  A pivot element is chosen from the array. you'll choose any element from the array because of the pivot element. Here, we've taken the rightmost (ie. the last element) of the array because of the pivot element.

Select a pivot element in Quicksort

• The elements smaller than the pivot element are placed on the left and therefore the elements greater than the pivot element are placed on the proper.

put the greater element in right and other in left

•  A pointer is fixed at the pivot element. The pivot element is compared with the weather beginning from the primary index. If the element greater than the pivot element is reached, a second pointer is about for that element.

•  Now, the pivot element is compared with the opposite elements (a third pointer). If a component smaller than the pivot element is reached, the smaller element is swapped with the greater element found earlier.

compare the element for the quicksort sorting algorithm

• The process goes on until the second last element is reached.

Swap pivot element with the second pointer for sorting algorithm

• Pivot elements are again chosen for the left and therefore the right sub-parts separately. With the help of these sub-parts, the chosen pivot elements are placed in their right position. Then, step 2 is repeated.

Select pivot element in Quicksort algorithm of in each half and put at the correct place using recursion

• The sub-parts are again divided into smaller sub-parts until each subpart is made of one element.

• At now, the array is already sorted.

Check For Quick Sort Algorithm:-

Check For Quick Sort Algorithm

Quicksort algorithm Program In C 

#include <stdio.h>

// check out the Function to swap position of elements in quicksort algorithm
void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

// Function to partition for the quick sort algorithm array on the basis of pivot element
int partition(int array[], int low, int high) {
  
  // Now Select the pivot element
  int pivot = array[high];
  int i = (low - 1);

  // comparison for element Put the elements smaller than pivot on the left 
  // and put the greater element than pivot on the right of pivot
  for (int j = low; j < high; j++) {
    if (array[j] <= pivot) {
      i++;
      swap(&array[i], &array[j]);
    }
  }

  swap(&array[i + 1], &array[high]);
  return (i + 1);
}

void quickSort(int array[], int low, int high) {
  if (low < high) {
    
   
    int pi = partition(array, low, high);
    
    // Sort the elements on the left of the pivot
    quickSort(array, low, pi - 1);
    
    // Sort the elements on the right of pivot
    quickSort(array, pi + 1, high);
  }
}

// Function to print eklements of an array in quicksort
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

// Driver code
int main() {
  int data[] = {8, 7, 2, 1, 0, 9, 6};
  int n = sizeof(data) / sizeof(data[0]);
  quickSort(data, 0, n - 1);
  printf("Sorted array in ascending order: \n");
  printArray(data, n);
}

Quicksort Algorithm uses recursion for sorting the sub-parts.

•  Divide

•  Conquer

• Combine

Sorting the left side elements by recursion

Sorting the right side elements by recursion

Complexity For Quicksort Algorithm

• Time Complexities

• Space Complexity For Quicksort Algorithm

Quicksort Applications

•  the programing language is sweet for recursion
•  time complexity matters
•  space complexity matters

Learn How the Selection Sort Works

•  Set the primary element as a minimum.

check the first minimum number

• Compare minimum with the second element. If the second number is smaller than minimum, so assign the second number as minimum in the selection sort algorithm.
  
  Compare minimum with the third element. Again, if the third number is smaller, then assign minimum to the third number in the selection sort algorithm or do nothing. the method goes on until the last element. 

Compare the number with the remaining number

• After each iteration, minimum is placed within the front of the unsorted list.

Swap the first number with the minimum in sorting algorithm

• For each iteration, indexing starts from the primary unsorted element. Step 1 to three are repeated until all the weather are placed at their correct positions.

step - 0 for sorting

step - 1 for sorting

step - 2 for sorting

step - 3 for sorting

 Algorithm For Selection Sort

selectionSort(array, size)
 repeat (size - 1) times
 set the primary unsorted element because the minimum
 for every of the unsorted elements
 if element < currentMinimum
 set element as new minimum
 swap minimum with first unsorted position
end selectionSort

Time Complexities:

Time Complexities Selection Sort Algorithm

•  Worst Case Complexity: O(n2)

•  Best Case Complexity: O(n2)

•  Average Case Complexity: O(n2)

Space Complexity:

• Selection Sort Applications

•  a little list is to be sorted

•  cost of swapping doesn't matter

•  checking of all the weather is compulsory

•  cost of writing to a memory matter like in non-volatile storage (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)

Divide and Conquer Strategy for merge sort algorithm

The MergeSort Algorithm

MergeSort(A, p, r):
 if p > r 
 return
 q = (p+r)/2
 mergeSort(A, p, q)
 mergeSort(A, q+1, r)
 merge(A, p, q, r)

merge sort algorithm

The merge Step of Merge Sort algorithm

Have we reached the top of any of the arrays?
 No:
 Compare current elements of both arrays
 Copy smaller element into a sorted array
 Move pointer of the element containing smaller element
 Yes:
 Copy all remaining elements of a non-empty array

merge sort algorithm steps

Writing the Code for Merge Algorithm

•  Create copies of the subarrays L ← A[p..q] and M ← A[q+1..r].
•  Create three-pointers i, j and k

•  Until we reach the top of either L or M, pick the larger among the weather from L and M and place them within the correct position at A[p..q]
•  once we run out of elements in either L or M, devour the remaining elements and put in A[p..q]

// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {

 // Create L ← A[p..q] and M ← A[q+1..r]
 int n1 = q - p + 1;
 int n2 = r - q;

 int L[n1], M[n2];

 for (int i = 0; i < n1; i++)
 L[i] = arr[p + i];
 for (int j = 0; j < n2; j++)
 M[j] = arr[q + 1 + j];

 // Handle the current index of sub-arrays and main array
 int i, j, k;
 i = 0;
 j = 0;
 k = p;

 // follow these steps until we reach either end of either L or M, pick larger among
 // elements L and M and place them within the correct position at A[p..r]
 while (i < n1 && j < n2) {
 if (L[i] <= M[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = M[j];
            j++;
        }
        k++;
    }

    // When all the elements are end in either L or M,
    // then take the remaining elements and put in A[p..r]
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = M[j];
        j++;
        k++;
    }
}

Merge( ) Function Explained Step-By-Step

mergesort algorithm

void merge(int arr[], int p, int q, int r) {
// Here, p = 0, q = 4, r = 5 (size of array)

// Create L ← A[p..q] and M ← A[q+1..r]
 int n1 = q - p + 1 = 3 - 0 + 1 = 4;
 int n2 = r - q = 5 - 3 = 2;

 int L[4], M[2];

 for (int i = 0; i < 4; i++)
 L[i] = arr[p + i];
 // L[0,1,2,3] = A[0,1,2,3] = [1,5,10,12]

 for (int j = 0; j < 2; j++)
 M[j] = arr[q + 1 + j];
 // M[0,1,2,3] = A[4,5] = [6,9] 

mergesort algorithm

maintain copies of sub-array

  while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            arr[k] = L[i]; i++; 
        } 
        else { 
            arr[k] = M[j]; 
            j++; 
        } 
        k++; 
    }

mergesort algorithm

while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

Copy the remaining elements

    while (j < n2)
    {
        arr[k] = M[j];
        j++;
        k++;
    }
}

mergesort in c

// Merge sort in C

#include 

// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {

  // Create L ← A[p..q] and M ← A[q+1..r]
  int n1 = q - p + 1;
  int n2 = r - q;

  int L[n1], M[n2];

  for (int i = 0; i < n1; i++)
    L[i] = arr[p + i];
  for (int j = 0; j < n2; j++)
    M[j] = arr[q + 1 + j];

  // Maintain current index of sub-arrays and main array
  int i, j, k;
  i = 0;
  j = 0;
  k = p;

  // Until we reach either end of either L or M, pick larger among
  // elements L and M and place them in the correct position at A[p..r]
  while (i < n1 && j < n2) {
    if (L[i] <= M[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = M[j];
      j++;
    }
    k++;
  }

  // When we run out of elements in either L or M,
  // pick up the remaining elements and put in A[p..r]
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < n2) {
    arr[k] = M[j];
    j++;
    k++;
  }
}

// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
  if (l < r) {

    // m is the point where the array is divided into two subarrays
    int m = l + (r - l) / 2;

    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);

    // Merge the sorted subarrays
    merge(arr, l, m, r);
  }
}

// Print the array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

// Driver program
int main() {
  int arr[] = {6, 5, 12, 10, 9, 1};
  int size = sizeof(arr) / sizeof(arr[0]);

  mergeSort(arr, 0, size - 1);

  printf("Sorted array: \n");
  printArray(arr, size);
}

Merge Sort Complexity

• Best Case Complexity: O(n*log n)
• Worst Case Complexity: O(n*log n)
• Average Case Complexity: O(n*log n)

• Space Complexity

• Merge Sort Applications

•  Inversion count problem
•  External sorting
•  E-commerce applications

Insertion sort algorithm

Learn How the Insertion Sort algorithm is going to Works

Initial array in insertion sort

in this photo first element greater then key is  in insertion sort

insertion sort algorithm step 1

insertion sort algorithm step 2

in step 3 behind 1, all array is sorted

Algorithm for Insertion Sort:-

insertionSort(array)
 mark first element as sorted
 for every unsorted element X
 'extract' the element X
 for j X
 move sorted element to the proper by 1
 break loop and insert X here
end insertionSort

Complexity:-

Time Complexities

Space Complexity for Insertion sort algorithm

Insertion Sort Applications

•  the array features a small number of elements

•  there are only a couple of elements left to be sorted

insertion sort algorithm with example in c

// Insertion sort in C

#include <stdio.h>

// Function to print an array
void printArray(int array[], int size) {
 for (int i = 0; i < size; i++) {
 printf("%d ", array[i]);
 }
 printf("\n");
}

void insertionSort(int array[], int size) {
 for (int step = 1; step < size; step++) {
 int key = array[step];
 int j = step - 1;

 // Compare key with each element on the left of it until a component smaller than
 // it's found.
 // For descending order, change keyarray[j].
 while (key < array[j] && j >= 0) {
 array[j + 1] = array[j];
 --j;
 }
 array[j + 1] = key;
 }
}

// Driver code
int main() {
 int data[] = {9, 5, 1, 4, 3};
 int size = sizeof(data) / sizeof(data[0]);
 insertionSort(data, size);
 printf("Sorted array in ascending order:\n");
 printArray(data, size);
}

What is Sorting(Bubble Sort in C) - Definition

Bubble Sort algorithm in C and bubble sort program in c

 Ascending order for Bubble Sort in C algorithm:

Descending order Bubble Sort algorithm in C:

Problem statement for bubble sort in c

Bubble Sort Algorithm in C - Introduction

#include  <stdio.h>
  
void swap(int *tp, int *qp) 
{ 
    int temp = *tp; 
    *tp = *qp; 
    *qp = temp; 
} 
  //function for bubble sort algorithm
void bubbleSort(int arr[], int n) 
{ 
   int k, l; 
   for (k = 0; k < n-1; k++)       
     
       for (l = 0; l < n-k-1; l++)  
           if (arr[l] > arr[l+1]) 
              swap(&arr[j], &arr[l+1]); 
} 
  

void printArray(int arr[], int size) 
{ 
    int k; 
    for (k=0; k < size; k++) 
        printf("%d ", arr[k]); 
    printf("\n"); 
} 
  
int main() 
{ 
    int arr[] = {1, 2, 4, 3, 5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    bubbleSort(arr, n); 
    printf("Sorted array: \n"); 
    printArray(arr, n); 
    return 0; 
} 

Bubble Sort in C - Explanation

Bubble sorting program in C

Conclusion for Bubble sort in c