DAA PRACTICALS
Practical 1-
Implementation and Time analysis of sorting algorithms. Bubble sort, Selection sort, Insertion sort, Merge sort and Quicksort
import [Link];
import [Link];
public class SortVisualizer {
// Bubble Sort with process
public static void bubbleSort(int[] arr) {
[Link]("\n--- Bubble Sort Process ---");
int n = [Link];
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
[Link]("Pass " + (i + 1) + ":");
for (int j = 0; j < n - i - 1; j++) {
[Link](" Comparing " + arr[j] + " and " + arr[j + 1]);
if (arr[j] > arr[j + 1]) {
// Swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
[Link](" => Swapped");
} else {
[Link](" => No change");
}
}
[Link](" Result after pass: " + [Link](arr));
if (!swapped) {
[Link](" No swaps in this pass. Array is sorted.");
break;
}
}
}
// Merge Sort with process
public static void mergeSort(int[] arr) {
[Link]("\n--- Merge Sort Process ---");
mergeSortRecursive(arr, 0, [Link] - 1);
}
private static void mergeSortRecursive(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2
mergeSortRecursive(arr, left, mid);
mergeSortRecursive(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
[Link]("Merging: " + [Link]([Link](arr, left, right + 1)));
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
[Link]("After merge: " + [Link]([Link](arr, left, right + 1)));
}
// Insertion Sort with process
public static void insertionSort(int[] arr) {
[Link]("\n--- Insertion Sort Process ---");
for (int i = 1; i < [Link]; i++) {
int key = arr[i];
int j = i - 1;
[Link]("Inserting " + key);
while (j >= 0 && arr[j] > key) {
[Link](" " + arr[j] + " > " + key + ", shifting " + arr[j] + " to the right");
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
[Link](" Placed " + key + " at position " + (j + 1));
[Link](" Array now: " + [Link](arr));
}
}
// Selection Sort with process
public static void selectionSort(int[] arr) {
[Link]("\n--- Selection Sort Process ---");
int n = [Link];
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
[Link]("Pass " + (i + 1) + ":");
for (int j = i + 1; j < n; j++) {
[Link](" Comparing " + arr[j] + " and " + arr[minIdx]);
if (arr[j] < arr[minIdx]) {
minIdx = j;
[Link](" => New min found at index " + j);
} else {
[Link](" => No change");
}
}
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
[Link](" Swapped " + arr[minIdx] + " with " + arr[i]);
}
[Link](" Result: " + [Link](arr));
}
}
// Quick Sort with process
public static void quickSort(int[] arr) {
[Link]("\n--- Quick Sort Process ---");
quickSortRecursive(arr, 0, [Link] - 1);
}
private static void quickSortRecursive(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSortRecursive(arr, low, pi - 1);
quickSortRecursive(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
[Link]("Partitioning with pivot " + pivot + " in " + [Link]([Link](arr, low, high + 1)));
int i = low - 1;
for (int j = low; j < high; j++) {
[Link](" Comparing " + arr[j] + " with pivot " + pivot);
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
[Link](" => Swapped " + arr[i] + " and " + arr[j]);
} else {
[Link](" => No change");
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
[Link](" Swapped pivot to correct position: " + [Link](arr));
return i + 1;
}
// Utility methods for input
public static int[] getNumbers() {
Scanner scanner = new Scanner([Link]);
[Link]("Enter numbers separated by space: ");
String[] tokens = [Link]().split(" ");
int[] arr = new int[[Link]];
for (int i = 0; i < [Link]; i++) {
arr[i] = [Link](tokens[i]);
}
return arr;
}
public static int chooseAlgorithm() {
Scanner scanner = new Scanner([Link]);
[Link]("\nChoose a sorting algorithm:");
[Link]("1. Bubble Sort");
[Link]("2. Merge Sort");
[Link]("3. Insertion Sort");
[Link]("4. Selection Sort");
[Link]("5. Quick Sort");
[Link]("Enter your choice (1–5): ");
return [Link]();
}
// Main method
public static void main(String[] args) {
int[] arr = getNumbers();
int choice = chooseAlgorithm();
// Copy array for sorting (to avoid modifying original input)
int[] arrCopy = [Link](arr, [Link]);
switch (choice) {
case 1:
bubbleSort(arrCopy);
break;
case 2:
mergeSort(arrCopy);
break;
case 3:
insertionSort(arrCopy);
break;
case 4:
selectionSort(arrCopy);
break;
case 5:
quickSort(arrCopy);
break;
default:
[Link]("Invalid choice.");
return;
}
[Link]("\n✅ Final sorted array: " + [Link](arrCopy));
}
}
OUTPUT: -
Practical 2-
Implementation and Time analysis of linear and binary search algorithm.
import [Link];
import [Link];
public class SearchAlgorithmsWithSteps {
// Linear Search Algorithm with process output
public static int linearSearch(int[] arr, int target) {
[Link]("\n--- Linear Search Process ---");
for (int i = 0; i < [Link]; i++) {
[Link]("Checking index " + i + " (value: " + arr[i] + ")");
if (arr[i] == target) {
[Link]("Found target at index " + i);
return i;
}
}
[Link]("Target not found in array.");
return -1;
}
// Binary Search Algorithm with process output
public static int binarySearch(int[] arr, int target) {
[Link]("\n--- Binary Search Process ---");
int low = 0;
int high = [Link] - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
[Link]("Checking mid index " + mid + " (value: " + arr[mid] + ")");
if (arr[mid] == target) {
[Link]("Found target at index " + mid);
return mid;
} else if (arr[mid] < target) {
[Link]("Target is greater than " + arr[mid] + ", searching right half");
low = mid + 1;
} else {
[Link]("Target is less than " + arr[mid] + ", searching left half");
high = mid - 1;
}
}
[Link]("Target not found in array.");
return -1;
}
// Get array input from user
public static int[] getArrayInput() {
Scanner scanner = new Scanner([Link]);
[Link]("Enter numbers separated by spaces: ");
String[] tokens = [Link]().split(" ");
int[] arr = new int[[Link]];
for (int i = 0; i < [Link]; i++) {
arr[i] = [Link](tokens[i]);
}
return arr;
}
// Get target value from user
public static int getTargetInput() {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the target value: ");
return [Link]();
}
// Get algorithm choice from user
public static int getChoice() {
Scanner scanner = new Scanner([Link]);
[Link]("\nChoose a search algorithm:");
[Link]("1. Linear Search");
[Link]("2. Binary Search");
[Link]("Enter your choice (1 or 2): ");
return [Link]();
}
// Main method
public static void main(String[] args) {
int[] arr = getArrayInput();
int target = getTargetInput();
int choice = getChoice();
int result = -1;
if (choice == 1) {
result = linearSearch(arr, target);
} else if (choice == 2) {
[Link](arr); // Binary search requires sorted array
[Link]("Sorted array for Binary Search: " + [Link](arr));
result = binarySearch(arr, target);
} else {
[Link]("Invalid choice. Please enter 1 or 2.");
return;
}
// Final result
if (result != -1) {
[Link]("\n✅ Target found at index: " + result);
} else {
[Link]("\n❌ Target not found in the array.");
}
}
}
Output:-
Practical 3-
Implementation of max-heap sort algorithm
import [Link];
import [Link];
public class MaxHeapSort {
// Heapify subtree rooted at index i for heap size n
public static void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child index
int right = 2 * i + 2; // right child index
[Link]("\nHeapifying at index " + i + " (value: " + arr[i] + ")");
if (left < n && arr[left] > arr[largest]) {
[Link](" Left child " + arr[left] + " is greater than root " + arr[largest]);
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
[Link](" Right child " + arr[right] + " is greater than current largest " + arr[largest]);
largest = right;
}
if (largest != i) {
[Link](" Swapping " + arr[i] + " and " + arr[largest]);
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
[Link](" Array after swap: " + [Link](arr));
// Recursively heapify affected subtree
heapify(arr, n, largest);
} else {
[Link](" No swapping needed, subtree is a valid max heap.");
}
}
// Heap sort function
public static void heapSort(int[] arr) {
int n = [Link];
[Link]("Building max heap...");
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
[Link]("Max heap built: " + [Link](arr));
for (int i = n - 1; i > 0; i--) {
[Link]("\nSwapping root " + arr[0] + " with element " + arr[i]);
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
[Link]("Array after swapping: " + [Link](arr));
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter numbers separated by space: ");
String[] input = [Link]().split(" ");
int[] arr = new int[[Link]];
for (int i = 0; i < [Link]; i++) {
arr[i] = [Link](input[i]);
}
[Link]("Original array: " + [Link](arr));
heapSort(arr);
[Link]("\nSorted array: " + [Link](arr));
[Link]();
}
}
Output:-