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.

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