Ex. No.
10 Implementation of Sorting algorithms : Quick Sort
Date: 24/10/2
4
Aim
To implement the Quick Sort algorithm to sort an array of integers in ascending order. Quick
Sort is an efficient, comparison-based sorting algorithm that uses the divide-and conquer
strategy.
Algorithm
1. Choose a Pivot:
o Select an element from the array as the pivot. The choice of pivot can vary (e.g., first
element, last element, middle element).
2. Partitioning:
o Rearrange the array such that elements less than the pivot are on the left, and elements
greater than the pivot are on the right.
3. Recursively Apply:
o Recursively apply the same procedure to the left and right sub-arrays.
4. Base Case:
o The recursion terminates when the sub-array has one or zero elements.
PROGRAM CODE:
#include <stdio.h>
#define MAX 100
int a[MAX], n, i, l, h;
// Function prototypes
void input(void);
void output(int arr[], int size);
void quick_sort(int arr[], int low, int high);
int main() {
input();
return 0;
}
void input(void){
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
l = 0;
h = n - 1;
quick_sort(a, l, h);
output(a, n);
}
void quick_sort(int arr[], int low, int high) {
int temp, key, i, j;
if (low < high) {
key = arr[(low + high) / 2];
OUTPUT:
Input (stdin)
5
3 6 8 10 1
Output (stdout)
1
3
6
8
10
i = low;
j = high;
do {
while (arr[i] < key) i++;
while (arr[j] > key) j--;
if (i <= j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
} while (i <= j);
if (low < j) quick_sort(arr, low, j);
if (i < high) quick_sort(arr, i, high);
}
}
void output(int arr[], int size) {
for (i = 0; i < size; i++) {
printf("%d\n", arr[i]);
}
}
INFERENCE:
Quick Sort is a comparison-based sorting algorithm that efficiently sorts elements by
dividing the array into smaller sub-arrays based on a pivot element. It performs well with a
time complexity of O(n log n) on average and is widely used for its simplicity and efficiency.
RESULT:
Thus , the C program to implement the Quick Sort algorithm to sort an array of integers in
ascending order was compiled and verified using hackerrank
Ex. No. 11 Implementation of Hashing – Linear Probing collision avoiding
Date:24/10/2 technique
4
AIM
To implement a hash table using linear probing for collision resolution in C, which supports
key insertion and displays the contents of the hash table.
ALGORITHM
1. Initialization:
o Define the hash table with a fixed size and initialize all slots to -1 (indicating empty slots).
2. Hash Function:
o Compute the index for a key using the modulo operation (key % TABLE_SIZE).
3. Insertion:
o Calculate the initial index using the hash function.
o If the slot at the computed index is occupied, probe linearly to find the next available slot.
o Insert the key into the first available slot found or return an error if the table is full.
4. Display:
o Iterate through the hash table array and print the contents of each slot, indicating whether it
is empty or contains a key.
PROGRAM:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#define size 11
int table[size];
void initialization()
{
for (int i = 0; i < size; i++)
{
table[i] = -1;
}
}
int code(int key)
{
return key % size;
}
void insert(int key)
{
int index = code(key);
int o_index = index;
while(table[index]!=-1)
{
OUTPUT:
Input (stdin)
5
10
24
34
24
98
Your Output (stdout)
Index 0: Key = 98
Index 1: Key = 34
Index 2: Key = 24
Index 3: Key = 24
Index 4: Empty
Index 5: Empty
Index 6: Empty
Index 7: Empty
Index 8: Empty
Index 9: Empty
Index 10: Key = 10
index = (index + 1) % size;
if (index == o_index)
{
printf("Hash table is full\n");
return;
}
}
table[index] = key;
}
void display()
{
for (int i = 0; i < size; i++)
{
if (table[i] != -1)
{
printf("Index %d: Key = %d\n", i, table[i]);
} else
{
printf("Index %d: Empty\n", i);
}
}
}
int main()
{
int n, key;
initialization();
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &key);
insert(key);
}
display();
return 0;
}
INFERENCE:
A hash table is a data structure that provides fast insertion, deletion, and lookup of keys.
When a collision occurs (i.e., two keys hash to the same index), linear probing is used to find
the next available slot by sequentially checking subsequent slots. This approach helps in
resolving collisions and efficiently managing the storage of keys.
RESULT:
Thus , the C program to implement a hash table using linear probing for collision resolution
in C, which supports key insertion and displays the contents of the hash table was compiled
and verified using hackerrank
