Assignment
Name :-- Tushar Kudesia
Roll no. :-- 2300290100266
Count sort :--
#include <stdio.h>
#include <stdlib.h>
void countSort(int inputArray[], int N) {
int M = 0;
for (int i = 0; i < N; i++)
if (inputArray[i] > M)
M = inputArray[i];
int* countArray = (int*)calloc(M + 1, sizeof(int));
for (int i = 0; i < N; i++)
countArray[inputArray[i]]++;
for (int i = 1; i <= M; i++)
countArray[i] += countArray[i - 1];
// Creating outputArray[] from countArray[] array
int* outputArray = (int*)malloc(N * sizeof(int));
for (int i = N - 1; i >= 0; i--) {
outputArray[countArray[inputArray[i]] - 1] = inputArray[i];
countArray[inputArray[i]]--;
}
for (int i = 0; i < N; i++)
inputArray[i] = outputArray[i];
free(countArray);
free(outputArray);
}
int main() {
// Input array
int inputArray[] = {4, 3, 12, 1, 5, 5, 3, 9};
int N = 8;
// Sorting the array
countSort(inputArray, N);
for (int i = 0; i < N; i++)
printf("%d ", inputArray[i]);
return 0;
}
Output :--
Radix sort :--
#include <stdio.h>
#include <stdlib.h>
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
void countingSort(int arr[], int n, int exp) {
int output[n]; // output array
int count[10] = {0}; // count array for digits (0-9)
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
void radixSort(int arr[], int n) {
// Get the maximum element to know the number of digits
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, n, exp);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
radixSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Output :--
Build Min heap using top down approach :--
#include <stdio.h>
#include <stdlib.h>
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int heap[], int i, int n) {
int smallest = i; // Initialize the smallest element as root
int left = 2 * i + 1; // Left child index
int right = 2 * i + 2; // Right child index
if (left < n && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < n && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != i) {
swap(&heap[i], &heap[smallest]);
heapify(heap, smallest, n);
}
}
void insertMinHeap(int heap[], int* n, int value) {
// Increase the size of the heap
(*n)++;
int i = *n - 1;
heap[i] = value;
while (i != 0 && heap[(i - 1) / 2] > heap[i]) {
swap(&heap[i], &heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void buildMinHeap(int heap[], int n) {
// Start with the first non-leaf node and heapify all nodes
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(heap, i, n);
}
}
void printHeap(int heap[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", heap[i]);
}
printf("\n");
}
int main() {
int heap[10];
int n = 0; // Initial size of the heap is 0
insertMinHeap(heap, &n, 10);
insertMinHeap(heap, &n, 20);
insertMinHeap(heap, &n, 5);
insertMinHeap(heap, &n, 30);
insertMinHeap(heap, &n, 40);
insertMinHeap(heap, &n, 15);
printf("Min-Heap after insertions (Top-Down approach): ");
printHeap(heap, n);
int arr[] = {10, 20, 5, 30, 40, 15};
int size = sizeof(arr) / sizeof(arr[0]);
buildMinHeap(arr, size);
printf("Min-Heap after building from unsorted array: ");
printHeap(arr, size);
return 0;
}
Output :--
Build Max heap using top down approach :--
#include <stdio.h>
#include <stdlib.h>
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int heap[], int i, int n) {
int largest = i; // Initialize the largest element as root
int left = 2 * i + 1; // Left child index
int right = 2 * i + 2; // Right child index
// If left child is larger than root
if (left < n && heap[left] > heap[largest]) {
largest = left;
}
if (right < n && heap[right] > heap[largest]) {
largest = right;
}
if (largest != i) {
swap(&heap[i], &heap[largest]);
heapify(heap, largest, n); // Recursive call to heapify the affected subtree
}
}
void insertMaxHeap(int heap[], int* n, int value) {
(*n)++;
int i = *n - 1;
heap[i] = value;
while (i != 0 && heap[(i - 1) / 2] < heap[i]) {
swap(&heap[i], &heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void buildMaxHeap(int heap[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(heap, i, n);
}
}
void printHeap(int heap[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", heap[i]);
}
printf("\n");
}
int main() {
int heap[10];
int n = 0; // Initial size of the heap is 0
insertMaxHeap(heap, &n, 10);
insertMaxHeap(heap, &n, 20);
insertMaxHeap(heap, &n, 5);
insertMaxHeap(heap, &n, 30);
insertMaxHeap(heap, &n, 40);
insertMaxHeap(heap, &n, 15);
printf("Max-Heap after insertions (Top-Down approach): ");
printHeap(heap, n);
int arr[] = {10, 20, 5, 30, 40, 15};
int size = sizeof(arr) / sizeof(arr[0]);
buildMaxHeap(arr, size);
printf("Max-Heap after building from unsorted array: ");
printHeap(arr, size);
return 0;
}
Output :--
