Program No.

-1

Aim: Write a program to implement the selection sort using array.

Selection Sort:-

 Selection sort is a simple and efficient sorting algorithm that works by repeatedly
selecting the smallest (or largest) element from the unsorted portion of the list and
moving it to the sorted portion of the list.
 The algorithm repeatedly selects the smallest (or largest) element from the
unsorted portion of the list and swaps it with the first element of the unsorted part.
 This process is repeated for the remaining unsorted portion until the entire list is
sorted.

Complexity:-

 Worst-case complexity: O(n2)

 Best-case complexity: O(n2)
 Average-case complexity: O(n2)

Algorithm:-

Step 1: Set minIndex to position 0 (minIndex will hold the index of the smallest
number in the unsorted subarray)
Step 2: Search for the smallest element in the unsorted subarray and update minIndex
Step 3: Swap the element at the position minIndex with the first element of the
unsorted subarray.
Step 4: Again set minIndex to the first position of the unsorted subarray
Step 5: Repeat steps 2 to 4 until the array gets sorted
Source Code:-
# include <stdio.h>
int main( )
{
int n, temp, a[25];
printf("Enter no. of elements of array\n");
scanf("%d",&n);
printf("Enter %d elements: \n",n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i]>a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("Sorted Elements: ");
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}
Output:-
Enter no. of elements of array
5
Enter 5 elements:
29401
Sorted Elements: 0 1 2 4 9
 Program No - 2
Aim:- Write a program to implement the insertion sort using array.

Insertion Sort:-
 Insertion sort is a simple sorting algorithm that works similar to the way you sort
playing cards in your hands. The array is virtually split into a sorted and an
unsorted part. Values from the unsorted part are picked and placed at the correct
position in the sorted part.
 Insertion Sort is a simple sorting algorithm that builds the final sorted array one
item at a time. It works by considering one element at a time and comparing it
with the elements to its left, shifting elements to the right as necessary to make
room for the current element.

Complexity:-
 Worst case complexity: O(n2)
 Best-case complexity: O(n)
 Average-case complexity: O(n2)

Algorithm:-
1. for j = 2 to A.length
2. key = A[j]
3. // Insert A[j] into the sorted sequence A[1.. j - 1]
4. i=j-1
5. while i > 0 and A[i] > key
6. A[i + 1] = A[i]
7. i = i -1
8. A[i + 1] = key

Process:
1. We will store the random set of numbers in an array.
2. We will traverse this array and insert each element of this array, to its correct
position where it should actually be, by shifting the other elements on the left if
required.
3. The first element in the array is considered as sorted, even if it is an unsorted
array. The array is sub-divided into two parts, the first part holds the first element
of the array which is considered to be sorted and second part contains all the
remaining elements of array.
4. With each iteration one element from the second part is picked and inserted into
the first part of array at its correct position by shifting the existing elements if
required.
5. This goes until the last element in second part of array is placed in correct position
in the output array.
 6. Now, we have the array in sorted order.

Source Code:-
#include<stdio.h>
int main()
{
int n, temp, a[25];
printf("Enter no. of elements of array\n");
scanf("%d",&n);
printf("Enter %d elements: \n",n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i = 1; i <= n - 1; i++)
{
for(int j = i; j > 0 && a[j - 1] > a[j]; j--)
{
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
printf("Sorted Elements: ");
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}

Output:-
Enter no. of elements of array
5
Enter 5 elements:
25 65 10 1 9
Sorted Elements: 1 9 10 25 65
 Program No - 3
Aim:- Write a program to implement the quick sort using array.

Quick Sort:-
 Quick Sort is a sorting algorithm based on the Divide and Conquer algorithm that
picks an element as a pivot and partitions the given array around the picked pivot
by placing the pivot in its correct position in the sorted array.

How Quicksort Works:-

Quicksort works by dividing a large array into smaller arrays and then sorting those smaller
arrays. A pivot element is used to partition a large array into smaller arrays; smaller arrays are
divided recursively until an array with only one or no elements is created.

Quicksort implementation requires two main methods:

 quickSort(): Selects a pivot element, partitions the array around the pivot
element, and recursively sorts the partitioned subarrays.
 partition(): Assigns the pivot element and places the pivot element at its right
position in the sorted array. Then, it places all smaller elements to the left of the
pivot and places all larger or equal elements to the pivot’s right.

Complexity:-
 Worst case complexity: O ( N2 )
 Best-case complexity: O ( N*log(N) )
 Average-case complexity: O ( N*log(N) )

Algorithm:-
Step-1: Select a pivot element.
Step-2: Partition the array around the pivot element.
Move all the elements < pivot to the left of the pivot and move all elements >= pivot
to the pivot’s right.
Step-3: After Step-2, the pivot element is in its correct position.
Step-4: Apply the quicksort recursively on the left partition.
Step-5: Apply the quicksort recursively on the right partition.
Step-6: Stop the recursion when the base case is reached. The base case is an array of
size zero or one.
Source Code:-
#include <stdio.h>
int partition(int ar[], int low, int high)
{
int pivot = ar[high];
int i = low - 1;
for (int j = low; j < high; j++)
{
if (ar[j] <= pivot)
{
i++;
int temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
}
int temp = ar[i + 1];
ar[i + 1] = ar[high];
ar[high] = temp;
return i + 1;
}

void quickSort(int arr[], int low, int high)

{
if (low < high)
{
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

int main( )
{
printf("Enter the number of elements in the array: ");
int n;
scanf("%d", &n);
int arr[n];
printf("Enter the elements of the array: ");
for (int i = 0; i < n; i++)
{
printf("%d: ", i);
scanf("%d", &arr[i]);
 }
quickSort(arr, 0, n - 1);
printf("The sorted array is: ");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}

Output:-
Enter the number of elements in the array:
6
Enter the elements of the array:
arr[0]: 12
arr[1]: 76
arr[2]: 33
arr[3]: 65
arr[4]: 5
arr[5]: 88
The sorted array is:
5 12 33 65 76 88
 Program No. – 4
Aim: Write a program to implement the Heap Sort using array.

Heap Sort:
 Heap Sort is a comparison-based sorting algorithm that uses a binary heap data
structure to build a max-heap (or min-heap) and performs sorting by repeatedly
extracting the maximum (or minimum) element.
 Heapsort is a popular and efficient sorting algorithm.

 Worst case complexity: O(𝑛 log 𝑛)

Complexity:

 Best-case complexity: O(𝑛 log 𝑛)

 Average-case complexity: O(𝑛 log 𝑛)

Algorithm:
1. Build a max-heap from the array.
2. Swap the root (maximum element) with the last element.
3. Remove the last element (maximum value) from the heap.
4. Heapify the remaining elements.
5. Repeat steps 2-4 until the heap is empty.

Pseudo Code:
HeapSort(arr)
BuildMaxHeap(arr)
for i = length(arr) - 1 to 1
swap arr[0] with arr[i]
heap_size[arr] = heap_size[arr] - 1
MaxHeapify(arr, 0)
End

BuildMaxHeap(arr)
heap_size(arr) = length(arr)
for i = length(arr)/2 - 1 to 0
MaxHeapify(arr, i)
End

MaxHeapify(arr, i)
L=2*i+1
R=2*i+2
largest = i

if L < heap_size[arr] and arr[L] > arr[i]

largest = L
 End
if R < heap_size[arr] and arr[R] > arr[largest]
largest = R
End

if largest ≠ i
swap arr[i] with arr[largest]
MaxHeapify(arr, largest)
End
End

Source Code:
#include <stdio.h>

void swap(int* a, int* b) {

int temp = *a;
*a = *b;
*b = temp;
}

void maxHeapify(int arr[], int heapSize, int i) {

int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < heapSize && arr[left] > arr[largest])

largest = left;

if (right < heapSize && arr[right] > arr[largest])

largest = right;

if (largest != i) {
swap(&arr[i], &arr[largest]);
maxHeapify(arr, heapSize, largest);
}
}

void buildMaxHeap(int arr[], int length) {

int heapSize = length;

for (int i = length / 2 - 1; i >= 0; i--) {

maxHeapify(arr, heapSize, i);
}
}

void heapSort(int arr[], int length) {

 buildMaxHeap(arr, length);

for (int i = length - 1; i >= 1; i--) {

swap(&arr[0], &arr[i]);
buildMaxHeap(arr, i);
}
}

int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter the elements: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

heapSort(arr, n);a

printf("\nSorted Array: ");

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

Result:
Enter the number of elements: 8
Enter the elements: 13 16 10 11 4 12 6 7
Sorted Array: 4 6 7 10 11 12 13 16
 Program No. – 5

Aim: Write a program to implement the Merge Sort using array.

Merge Sort: In the context of sorting elements in a list and in ascending order, the merge sort
method divides the list into halves, then iterates through the new halves, continually dividing
them down further to their smaller parts. Subsequently, a comparison of smaller halves is
conducted, and the results are combined together to form the final sorted list.

 Worst case complexity: O(𝑛 log 𝑛)

Complexity:

 Best-case complexity: O(𝑛 log 𝑛)

 Average-case complexity: O(𝑛 log 𝑛)

Algorithm:
1. Divide the unsorted array into two halves.
2. Recursively sort each half.
3. Merge the sorted halves.

Pseudo Code:
MergeSort(arr[], l, r)
if l < r
middle = l + (r - l) / 2
MergeSort(arr, l, middle)
MergeSort(arr, middle + 1, r)
Merge(arr, l, middle, r)

Merge(arr[], l, m, r)
n1 = m - l + 1
n2 = r - m

// Create temporary arrays

L[n1], R[n2]
// Copy data to temporary arrays L[] and R[]
for i = 0 to n1 - 1
L[i] = arr[l + i]
for j = 0 to n2 - 1
R[j] = arr[m + 1 + j]

// Merge the temporary arrays back into arr[l..r]

i=0j=0k=l
while i < n1 and j < n2
if L[i] <= R[j]
arr[k] = L[i]
i=i+1
 else
arr[k] = R[j]
j=j+1
k=k+1

// Copy the remaining elements of L[], if there are any

while i < n1
arr[k] = L[i]
i=i+1
k=k+1
// Copy the remaining elements of R[], if there are any
while j < n2
arr[k] = R[j]
j=j+1
k=k+1

Source Code:
#include <stdio.h>

void merge(int arr[], int l, int m, int r) {

int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

for (int i = 0; i < n1; i++)

L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
} k+
+;
}

while (i < n1) {

arr[k] = L[i]; i+
+;
k++;
 }

while (j < n2) {

arr[k] = R[j]; j+
+;
k++;
}
}

void mergeSort(int arr[], int l, int r) {

if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter the elements: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

mergeSort(arr, 0, n - 1);

printf("\nSorted array is: ");

printArray(arr, n);

return 0;
}
Result:
Enter the number of elements: 8
Enter the elements: 13 16 10 11 4 12 6 7
Sorted Array is: 4 6 7 10 11 12 13 16
 Program No. – 6

Aim: Write a program to implement the Linear Search using array.

Linear Search: Linear Search is a simple search algorithm that sequentially checks each
element of the array until a match is found or the entire array has been searched.

Complexity:
 Worst case complexity: O(𝑛)
 Best-case complexity: O(1)
 Average-case complexity: O(𝑛)

Algorithm:
1. Start from the first element of the array.
2. Compare the target element with each element of the array sequentially.
3. If a match is found, return the index of the element.
4. If the end of the array is reached without finding the element, return -1 (indicating the
element is not present).

Pseudo Code:
LinearSearch(arr, target)
for i from 0 to length(arr) - 1
if arr[i] equals target
return i
return -1

Source Code:
#include <stdio.h>

int linearSearch(int arr[], int length, int target) {

for (int i = 0; i < length; i++) {
if (arr[i] == target) {
return i; // Return the index if the element is found
}
}
return -1; // Return -1 if the element is not found
}

int main() {
int n, target;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
 printf("Enter the elements: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

printf("Enter the target element to search: ");

scanf("%d", &target);

int result = linearSearch(arr, n, target);

if (result != -1) {
printf("Element %d found at index %d\n", target, result);
} else {
printf("Element %d not found in the array\n", target);
}

return 0;
}

Result:
Enter the number of elements: 8
Enter the elements: 13 16 10 11 4 12 6 7
Enter the target element to search: 12
Element 12 found at index 5
 Program No. – 7

Aim: Write a program to implement the Binary Search using array.

Binary Search: Binary Search is a search algorithm that works by repeatedly dividing the
search interval in half. It compares the target element with the middle element of the array
and eliminates half of the remaining elements, continuing this process until the target element
is found or the remaining interval is empty.

 Worst case complexity: O(log 𝑛)

Complexity:

 Average-case complexity: O(log 𝑛)

 Best-case complexity: O(1)

Algorithm:
1. Initialize two pointers, low and high, to the start and end of the array, respectively.
2. Repeat until low is less than or equal to high:
a. Calculate the middle index as (low + high) / 2.
b. If the middle element is equal to the target, return the middle index.
c. If the target is less than the middle element, update high to mid - 1.
d. If the target is greater than the middle element, update low to mid + 1.
3. If the loop exits without finding the target, return -1.

Pseudo Code:
BinarySearch(arr, target)
low = 0
high = length(arr) - 1

while low <= high

mid = (low + high) / 2

if arr[mid] equals target

return mid
else if arr[mid] < target
low = mid + 1
else
high = mid - 1

return -1

Source Code:
#include <stdio.h>

int binarySearch(int arr[], int length, int target) {

int low = 0;
 int high = length - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) {
return mid; // Return the index if the element is found
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}

return -1; // Return -1 if the element is not found

}

int main() {
int n, target;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter the sorted elements: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter the target element to search: ");
scanf("%d", &target);

int result = binarySearch(arr, n, target);

if (result != -1) {
printf("Element %d found at index %d\n", target, result);
} else {
printf("Element %d not found in the array\n", target);
}

return 0;
}

Result:
Enter the number of elements: 8
Enter the elements: 13 16 10 11 4 12 6 7
Enter the target element to search: 12
Element 12 found at index 5
 Program No. – 8

Aim: Write a program to implement the Knaps problem using Greedy solution.

Theory : The Knapsack Problem involves selecting a combination of items with maximum
total value, considering a constraint on the total weight that can be carried.

 Worst case complexity: O(𝑛 log 𝑛)

Complexity:

 Best-case complexity: O(𝑛 log 𝑛)

 Average-case complexity: O(𝑛 log 𝑛)

Algorithm:
1. Calculate the value-to-weight ratio for each item.
2. Sort the items based on the value-to-weight ratio in non-decreasing order.
3. Initialize the total weight in the knapsack (currentWeight) to 0 and initialize the total
value (totalValue) to 0.
4. Iterate through the sorted items and add items to the knapsack until the knapsack is
full.
5. Return the total value as the solution.

Pseudo Code:
GreedyKnapsack(items[], capacity)
Sort items based on value-to-weight ratio in non-decreasing order
currentWeight = 0
totalValue = 0

for each item in sorted items

if (currentWeight + item.weight) <= capacity
currentWeight += item.weight
totalValue += item.value

return totalValue

Code:
#include <stdio.h>
#include <stdlib.h>

// Structure to represent an item

struct Item {
int value;
int weight;
};

// Comparison function for sorting items based on value-to-weight ratio

int compare(const void* a, const void* b) {
double ratioA = ((struct Item*)a)->value / (double)((struct Item*)a)-
>weight;
double ratioB = ((struct Item*)b)->value / (double)((struct Item*)b)-
>weight;
return (ratioB > ratioA) ? 1 : -1; // Sort in non-decreasing order of ratio
}

// Function to solve the Knapsack problem using Greedy approach

double greedyKnapsack(struct Item items[], int n, int capacity) {
// Sort items based on value-to-weight ratio
qsort(items, n, sizeof(struct Item), compare);

int currentWeight = 0; // Current weight in the knapsack

double totalValue = 0.0; // Total value obtained

for (int i = 0; i < n; i++) {

if (currentWeight + items[i].weight <= capacity) {
// Add the entire item if it fits in the knapsack
currentWeight += items[i].weight;
totalValue += items[i].value;
} else {
// Add a fraction of the item to fill the knapsack to its capacity
double remainingCapacity = capacity - currentWeight;
totalValue += (remainingCapacity / items[i].weight) * items[i].value;
break; // Knapsack is full, exit the loop
}
}

return totalValue;
}

int main() {
int n, capacity;

// Get the number of items and knapsack capacity from the user
printf("Enter the number of items: ");
scanf("%d", &n);
printf("Enter the knapsack capacity: ");
scanf("%d", &capacity);

// Create an array of items

struct Item items[n];

// Get the value and weight of each item from the user
for (int i = 0; i < n; i++) {
 printf("Enter the value and weight of item %d: ", i + 1);
scanf("%d %d", &items[i].value, &items[i].weight);
}

// Solve the Knapsack problem using Greedy approach

double result = greedyKnapsack(items, n, capacity);

// Display the result

printf("Maximum value in the knapsack: %.2f\n", result);

return 0;
}

Input:
Enter the number of items: 4
Enter the knapsack capacity: 10
Enter the value and weight of item 1: 60 5
Enter the value and weight of item 2: 100 20
Enter the value and weight of item 3: 120 30
Enter the value and weight of item 4: 50 10
Output:
Maximum value in the knapsack: 240.00