Design And Analysis of

Algorithms
LAB Report

Submitted by Submitted to

Name: Pratyush Pandey Kartikey Awasthi Sir

Section: X GLA University Mathura
Class Roll No.: 62
Batch: 2024 – 2025
University Roll No.: 2315990052
 Index
Exp. Page
No Title of the Experiment No Signature

1 Quick Sort 1

2 Merge Sort 3

3 Selection Sort 5

4 Bubble Sort 7

5 Insertion Sort 9

6 Linear Search 11

7 Binary Search 13
 Experiment – 01

Objective:

• Understand about Quick Sort.

• Implement Quick Sort in Java.

Theory:
Quick Sort is a divide-and-conquer sorting algorithm. It selects a pivot
element and partitions the array so that elements smaller than the pivot are moved to
the left, and larger to the right. Then it recursively sorts the subarrays. The average
time complexity is O(n log n), and the worst-case is O(n²).

Implementation

public class QuickSort {

public static 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);
}
}

private static int partition(int[] arr, int low, int high) {

int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

1
 public static void main(String[] args) {
int[] arr = { 10, 7, 8, 9, 1, 5 };

System.out.println("Original Array !!");

for (int i : arr)
System.out.print(i + " ");

System.out.println("\nAfter Quick Sort !!");

quickSort(arr, 0, arr.length - 1);
for (int i : arr)
System.out.print(i + " ");
}
}

public static void main(String[] args) {

int[] arr = { 10, 7, 8, 9, 1, 5 };

System.out.println("Original Array !!");

for (int i : arr)
System.out.print(i + " ");

System.out.println("\nAfter Quick Sort !!");

quickSort(arr, 0, arr.length - 1);
for (int i : arr)
System.out.print(i + " ");
}
}

Output:

2
 Experiment – 02

Objective:

• Understand about Merge Sort.

• Implement Merge Sort in Java.

Theory:
Merge Sort is a recursive sorting algorithm that splits the array into halves,
sorts each half, and then merges them. It is stable and has a consistent time complexity of
O(n log n) in all cases.

Implementation:

public class MergeSort {

public static 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);
}
}

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

int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[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)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}
3
 public static void main(String[] args) {
int[] arr = { 12, 11, 13, 5, 6, 7 };

System.out.println("Original Array !!");

for (int i : arr)
System.out.print(i + " ");

System.out.println("\nAfter Merge Sort !!");

mergeSort(arr, 0, arr.length - 1);
for (int i : arr)
System.out.print(i + " ");
}
}

Output:

4
 Experiment – 03

Objective:

• Understand about Selection Sort.

• Implement Selection Sort in Java.

Theory:
Selection Sort is a simple comparison-based sorting algorithm. It works by
repeatedly selecting the smallest (or largest) element from the unsorted portion and
moving it to the sorted portion. It has a time complexity of O(n²) for all cases. Though
inefficient on large lists, it is easy to understand and implement.

Implementation:
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}

public static void main(String[] args) {

int[] arr = { 64, 25, 12, 22, 11 };
System.out.println("Original Array !!");
for (int i : arr)
System.out.print(i + " ");

System.out.println("\nAfter Selection Sort !!");

selectionSort(arr);
for (int i : arr)
System.out.print(i + " ");
}
}
5
Output:

6
 Experiment – 04

Objective:

• Understand about Bubble Sort.

• Implement Bubble Sort in Java.

Theory:
Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly
stepping through the list, comparing adjacent elements, and swapping them if they are in
the wrong order. This process is repeated until the list is sorted. Though inefficient for
large datasets, it's useful for educational purposes. The time complexity is O(n²) in the
worst and average case, and O(n) in the best case when the list is already sorted.

Implementation:

public class BubbleSort {

public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped)
break;
}
}

public static void main(String[] args) {

int[] arr = { 5, 1, 4, 2, 8 };
System.out.println("Original Array !!");
for (int i : arr)
System.out.print(i + " ");

System.out.println("\nAfter Bubble Sort !!");

bubbleSort(arr); 7
 for (int i : arr)
System.out.print(i + " ");
}
}

Output:

8
 Experiment – 05

Objective:

• Understand about Insertion Sort.

• Implement Insertion Sort in Java.

Theory:
Insertion Sort is a simple sorting algorithm that builds the final sorted array
one item at a time. It is much like sorting playing cards in your hands—by comparing each
new card with the already-sorted ones and placing it in the correct position. It has a time
complexity of O(n²) in the average and worst cases, and O(n) in the best case (when the
array is already sorted). It is efficient for small datasets and mostly sorted arrays.

Implementation:

public class InsertionSort {

public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

public static void main(String[] args) {

int[] arr = { 12, 11, 13, 5, 6 };
System.out.println("Original Array !!");
for (int i : arr)
System.out.print(i + " ");

System.out.println("\nAfter Insertion Sort !!");

insertionSort(arr);
for (int i : arr)
System.out.print(i + " ");
}
}
9
Output:

10
 Experiment – 06

Objective:

• Understand about Linear Search.

• Implement Linear Search in Java.

Theory:
Linear Search is the most basic searching technique. It works by checking each
element in the array one by one until the desired value is found or the end of the list is
reached. It does not require the array to be sorted. The time complexity is O(n) for all
cases.

Implementation:

public class LinearSearch {

public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target)
return i;
}
return -1;
}

public static void main(String[] args) {

int[] arr = { 10, 20, 30, 40, 50 };
int target = 30;
int result = linearSearch(arr, target);
System.out.println("Original Array !!");
for (int i : arr)
System.out.print(i + " ");
System.out.println("\nTarget element: " + target);

if (result != -1)
System.out.println("Element found at index: " + result);
else
System.out.println("Element not found.");
}
}

11
Output:

12
 Experiment – 07

Objective:

• Understand about Binary Search.

• Implement Binary Search in Java.

Theory:
Binary Search is an efficient searching algorithm used on sorted arrays. It
works by repeatedly dividing the search interval in half. If the target value is less than the
middle element, the search continues in the left half; otherwise, it continues in the right
half. Its time complexity is O(log n), making it much faster than linear search for large
datasets.

Implementation:

public class BinarySearch {

public static int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;

if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}

public static void main(String[] args) {

int[] arr = { 10, 20, 30, 40, 50 };
int target = 40;
int result = binarySearch(arr, target);
System.out.println("Original Array !!");
for (int i : arr)
System.out.print(i + " ");
System.out.println("\nTarget element: " + target);
if (result != -1)
System.out.println("Element found at index: " + result);
else 13
 System.out.println("Element not found.");
}
}

Output:

14