Counting sort in C programming
// Counting sort in C programming
#include<stdio.h>
#define MAX 255
void countSort(int array[], int size)
{
int output[MAX];
int count[MAX];
int max = array[0];
// Here we find the largest item in the array
for (int i = 1; i < size; i++) { if (array[i] > max)
max = array[i];
}
// Initialize the count for each element in array to 0
for (int i = 0; i <= max; ++i)
{
count[i] = 0;
}
// For each element we store the count
for (int i = 0; i < size; i++)
{
count[array[i]]++;
}
// Store the cummulative count of each array
for (int i = 1; i <= max; i++)
{
count[i] += count[i - 1];
}
// Search the index of each element of the actual array in count
array, and
// place the elements in output array
for (int i = size - 1; i >= 0; i--)
{
output[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// Transfer the sorted items into actual array
for (int i = 0; i < size; i++)
{
array[i] = output[i];
}
}
// printing items of the array
void display(int array[], int size)
{
for (int i = 0; i < size; i++)
printf("%d ",array[i]);
printf("\n");
}
// Driver code
int main() {
int array[] = {2, 5, 2, 8, 1, 4, 1};
int n = sizeof(array) / sizeof(array[0]);
countSort(array, n);
display(array, n);
return 0;
}
BUCKET SORT PROGRAM
#include <stdio.h>
//Function to find maximum element of the array
int max_element(int array[], int size)
{
// Initializing max variable to minimum value so that it can be updated
// when we encounter any element which is greater than it.
int max = -32767;
for (int i = 0; i < size; i++)
{
//Updating max when array[i] is greater than max
if (array[i] > max)
max = array[i];
}
//return the max element
return max;
}
//Implementing bucket sort
void Bucket_Sort(int array[], int size)
{
//Finding max element of array which we will use to create buckets
int max = max_element(array, size);
// Creating buckets
int bucket[max+1];
//Initializing buckets to zero
for (int i = 0; i <= max; i++)
bucket[i] = 0;
// Pushing elements in their corresponding buckets
for (int i = 0; i < size; i++)
bucket[array[i]]++;
// Merging buckets effectively
int j=0; // j is a variable which points at the index we are updating
for (int i = 0; i <= max; i++)
{
// Running while loop until there is an element in the bucket
while (bucket[i] > 0)
{
// Updating array and increment j
array[j++] = i;
// Decreasing count of bucket element
bucket[i]--;
}
}
}
/* The main() begins */
int main()
{
int array[100], i, num;
printf("Enter the size of array: ");
scanf("%d", &num);
printf("Enter the %d elements to be sorted:\n",num);
for (i = 0; i < num; i++)
scanf("%d", &array[i]);
printf("\nThe array of elements before sorting: \n");
for (i = 0; i < num; i++)
printf("%d ", array[i]);
printf("\nThe array of elements after sorting: \n");
// Calling bucket sort function
Bucket_Sort(array, num);
for (i = 0; i < num; i++)
printf("%d ", array[i]);
printf("\n");
return 0;
}
HEAPSORT
• #include <stdio.h>
• void swap(int* a, int* b)
• {
• int temp = *a;
• *a = *b;
• *b = temp;
• }
• void heapify(int arr[], int N, int i)
• {
• int largest = i;
• int left = 2 * i + 1;
• int right = 2 * i + 2;
• if (left < N && arr[left] > arr[largest])
• largest = left;
• if (right < N && arr[right] > arr[largest])
• largest = right;
• if (largest != i)
• {
• swap(&arr[i], &arr[largest]);
• heapify(arr, N, largest);
• }
• }
• void heapSort(int arr[], int N)
• {
• for (int i = N / 2 - 1; i >= 0; i--)
• heapify(arr, N, i);
•
• for (int i = N - 1; i >= 0; i--)
• {
• swap(&arr[0], &arr[i]);
• heapify(arr, i, 0);
• }
• }
• void printArray(int arr[], int N)
• {
• for (int i = 0; i < N; i++)
• printf("%d ", arr[i]);
• printf("\n");
• }
• int main()
• {
• int arr[] = { 12, 11, 13, 5, 6, 7 };
• int N = sizeof(arr) / sizeof(arr[0]);
• heapSort(arr, N);
• printf("Sorted array is\n");
• printArray(arr, N);
• }
