Semester Course Code Course Title
Data Structures Lab
Winter 2024-25 CS162
Student Details: Student Name: Ajudiya Krish Prafulkumar
Roll/Reg No: 2024111005
Email:
[email protected] Mobile:8799400820
Faculty Details: Faculty Name: Dr. VENKATA PHANIKRISHNA B
Department: Computer Science and Engineering
Email:
[email protected]Assessment No: 5
Assessment Title. Implementation of non-Comparison Sorting
Date of Submission 15-March-2025
Format/Frame Work
Question Provided by the professor.
Program Must be typed content (not screenshots).
Can include program code, syntax, or relevant theory.
Include your roll number and name in comments.
Output: Typed or copy-pasted content of your program's output is preferred.
If difficult, output screenshots are acceptable.
Note: Ensure your name is included in the comments of all submitted programs.
Your
Observation
A5: Implementation of Sorting Algorithms Part 2
A5: P1@Write a program to implement Count Sort
A5: P2@ Write a program to implement Radix Sort
A5: P3@Write a program to implement Bucket Sort
Question 1 Write a program to implement Count Sort
Program #include <stdio.h>
#include <limits.h>
int main() {
int n;
scanf("%d", &n);
int arr[n];
int maxi = INT_MIN, mini = INT_MAX;
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
if (arr[i] > maxi) maxi = arr[i];
if (arr[i] < mini) mini = arr[i];
}
int range = maxi - mini + 1;
int count[range];
for (int i = 0; i < range; i++) {
count[i] = 0;
}
printf("Original Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n\n");
printf("Step 1: Initialize count array\n");
for (int i = 0; i < range; i++) {
printf("%d ", count[i]);
}
printf("\n\n");
for (int i = 0; i < n; i++) {
count[arr[i] - mini]++;
}
printf("Step 2: Count occurrences\n");
for (int i = 0; i < range; i++) {
printf("%d ", count[i]);
}
printf("\n\n");
for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}
printf("Step 3: Cumulative count\n");
for (int i = 0; i < range; i++) {
printf("%d ", count[i]);
}
printf("\n\n");
printf("Step 4: Placing elements in sorted order\n\n");
printf("Original Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
int ans[n];
for (int i = 0; i < n; i++) {
ans[i] = -1;
}
int total_swaps = 0;
for (int i = n - 1; i >= 0; i--) {
int val = arr[i] - mini;
int pos = count[val] - 1;
printf("Placing %d at index %d\n", arr[i], pos);
ans[pos] = arr[i];
count[val]--;
total_swaps++;
printf("Updated Count Array: ");
for (int j = 0; j < range; j++) {
printf("%d ", count[j]);
}
printf("\n");
printf("Updated Output Array: ");
for (int j = 0; j < n; j++) {
printf("%d ", ans[j]);
}
printf("\n\n");
}
printf("Step 4: Sorted output array\n");
for (int i = 0; i < n; i++) {
printf("%d ", ans[i]);
}
printf("\n\n");
printf("Time Complexity Analysis:\n");
printf("Best Case: O(n + k)\n");
printf("Worst Case: O(n + k)\n");
printf("Average Case: O(n + k)\n");
printf("Space Complexity: O(n + k)\n");
printf("Total Swaps: %d\n\n", total_swaps);
printf("Sorted Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", ans[i]);
}
printf("\n");
return 0;
}
Output:
Your This code uses counting sort to efficiently organize an array by counting how many times
Observation each number appears and then placing them in order.
Question 2 Write a program to implement Radix Sort
Program #include <stdio.h>
#include <limits.h>
int main() {
int n;
scanf("%d", &n);
int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Original Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
int max_value = INT_MIN;
for (int i = 0; i < n; i++) {
if (arr[i] > max_value)
max_value = arr[i];
}
int count[10], ans[n];
int a = 1;
int split = 0;
int movements = 0;
while (max_value / a > 0) {
for (int i = 0; i < 10; i++) {
count[i] = 0;
}
for (int i = 0; i < n; i++) {
int digit = (arr[i] / a) % 10;
count[digit]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / a) % 10;
ans[count[digit] - 1] = arr[i];
count[digit]--;
movements++;
}
for (int i = 0; i < n; i++) {
arr[i] = ans[i];
}
printf("Sorting by %d's place: ", a);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
split++;
a *= 10;
}
printf("\nSorted Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n\nPerformance Analysis:\n");
printf("Number of Splits (Digit Passes): %d\n", split);
printf("Number of Element Movements: %d\n", movements);
printf("Time Complexity: O(d * (n + k))\n");
printf("Space Complexity: O(n + k) (for counting sort auxiliary array)\n");
return 0;
}
Output:
Your This code efficiently sorts an array using Radix sort by processing each digit with counting
Observation sort and tracks the number of passes and movements for performance analysis.
Question 3 Write a program to implement Bucket Sort
Program #include <stdio.h>
#include <stdlib.h>
#include <math.h>
void insertion_sort(float bucket_arr[], int size) {
for (int i = 1; i < size; i++) {
float key = bucket_arr[i];
int j = i - 1;
while (j >= 0 && bucket_arr[j] > key) {
bucket_arr[j + 1] = bucket_arr[j];
j--;
}
bucket_arr[j + 1] = key;
}
}
int main() {
int mode, n;
scanf("%d", &mode);
scanf("%d", &n);
float arr[100];
if (mode == 3) {
char temp;
for (int i = 0; i < n; i++) {
scanf(" %c", &temp);
arr[i] = (float)temp;
}
} else {
for (int i = 0; i < n; i++) {
scanf("%f", &arr[i]);
}
}
printf("Original Array:\n");
for (int i = 0; i < n; i++) {
if (mode == 1)
printf("%.0f ", arr[i]);
else if (mode == 2)
printf("%.2f ", arr[i]);
else
printf("%c", (char)arr[i]);
}
printf("\n");
int bucket_count = (mode == 3) ? 26 : n;
float buckets[100][100];
int bucket_sizes[100] = {0};
if (mode == 3)
printf("\nStep 1: Buckets Created (Count = 26 for a-z)\n");
else
printf("\nStep 1: Buckets Created (Count = %d)\n", bucket_count);
for (int i = 0; i < n; i++) {
int ind;
if (mode == 1) {
ind = ((int)arr[i] % bucket_count + bucket_count) % bucket_count;
} else if (mode == 2) {
ind = ((int)(arr[i] * bucket_count) % bucket_count + bucket_count) %
bucket_count;
} else {
ind = (int)(arr[i] - 'a');
}
buckets[ind][bucket_sizes[ind]] = arr[i];
bucket_sizes[ind]++;
if (mode == 3)
printf("Inserted '%c' into Bucket[%d]\n", (char)arr[i], ind);
else
printf("Inserted %.2f into Bucket[%d]\n", arr[i], ind);
}
printf("\nStep 2: Sorting Buckets Using Insertion Sort\n");
for (int i = 0; i < bucket_count; i++) {
insertion_sort(buckets[i], bucket_sizes[i]);
}
int index = 0;
for (int i = 0; i < bucket_count; i++) {
for (int j = 0; j < bucket_sizes[i]; j++) {
arr[index] = buckets[i][j];
if (mode == 3)
printf("Bucket[%d]: Placing '%c' back into array at index %d\n", i,
(char)arr[index], index);
else
printf("Bucket[%d]: Placing %.2f back into array at index %d\n", i, arr[index],
index);
index++;
}
}
printf("\n---- Sorting Statistics ----\n");
printf("Total Swaps: %d\n", n);
printf("Total Insertions into Buckets: %d\n", n);
if (mode == 3)
printf("Space Complexity: O(n + k) where k is 26 for characters\n");
else
printf("Space Complexity: O(n + k) where k is number of buckets (%d)\n",
bucket_count);
printf("\nSorted Array:\n");
for (int i = 0; i < n; i++) {
if (mode == 1)
printf("%.0f ", arr[i]);
else if (mode == 2)
printf("%.2f ", arr[i]);
else
printf("%c", (char)arr[i]);
}
printf("\n");
return 0;
}
Output:
Your This program groups data into buckets, sorts each bucket with insertion sort, and then
Observation merges them to create a sorted list while showing each step.
