PROGRAM-15
AIM:Write a program for Shell Sort in C.
Theory:Shell Sort is an optimization of Insertion Sort that allows the exchange of far-apart
elements.
It works by sorting elements at specific intervals (called gaps), reducing the gap each time
until it becomes 1 (which is just a regular insertion sort).
This approach reduces the total number of shifts/swaps compared to regular insertion sort.
Algorithm (Shell Sort)
1. Start with a large gap (e.g., n/2), then reduce the gap by half each time.
2. For each gap:
○ Perform gapped insertion sort.
○ Compare and shift elements that are gap apart.
3. Repeat until the gap becomes 0.
Program
#include <stdio.h>
// Function to perform shell sort
void shellSort(int arr[], int n) {
// Start with a big gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {
// Do a gapped insertion sort for this gap size
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
// Shift earlier gap-sorted elements up until the correct location is found
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
// Put temp (the original arr[i]) in its correct location
arr[j] = temp;
}
}
}
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Main function
int main() {
int arr[] = {23, 12, 1, 8, 34, 54, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
shellSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
PROGRAM-16
Write a program for Heap Sort in C.
Theory – Heap Sort
Heap Sort is a comparison-based sorting technique based on a Binary Heap data structure.
It works by:
1. Building a max heap.
2. Repeatedly swapping the first (maximum) element with the last unsorted element.
3. Reducing the heap size and heapifying agaiN
Algorithm – Heap Sort
1. Build a max heap from the input data.
2. Swap the root element (maximum) with the last element.
3. Reduce the heap size by 1 and heapify the root.
4. Repeat steps 2 and 3 until the heap size is 1.
CODE:
#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
// If left child is larger
if (left < n && arr[left] > arr[largest])
largest = left;
// If right child is larger
if (right < n && arr[right] > arr[largest])
largest = right;
// If largest is not root
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
void heapSort(int arr[], int n) {
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract elements from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
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]);
printf("Original array: ");
printArray(arr, n);
heapSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
PROGRAM-17
Write a program for Radix Sort in C.
Theory – Radix Sort
Radix Sort is a non-comparative sorting algorithm.
It sorts integers by processing digits from least significant digit (LSD) to most significant
digit (MSD) using counting sort as a subroutine.
Works only with non-negative integers
Algorithm – Radix Sort
1. Find the maximum number to know the number of digits.
2. For every digit from least to most significant:
○ Use Counting Sort to sort based on that digit.
Program:
#include <stdio.h>
// Get maximum value in arr[]
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;
// Perform counting sort based on the digit at exp (1s, 10s, 100s...)
void countingSort(int arr[], int n, int exp) {
int output[n]; // Output array
int count[10] = {0};
// Store count of occurrences
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Update count[i] to contain actual positions
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
// Copy output[] to arr[]
for (int i = 0; i < n; i++)
arr[i] = output[i];
// Main radix sort function
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
// Apply counting sort for every digit
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;}