For 20 and 21 December (Java Batch)

Java Program to Implement Bubble Sort algorithm

// Import the Class
import java.util.Arrays;
import java.util.Scanner;

class Main {

  // Method to perform bubble sort
  void bubbleSort(int array[], int sortOrder) {
    int size = array.length;

    // Run loops two times: first loop accesses each element of the array
    for (int i = 0; i < size - 1; i++) {
      // Second loop performs the comparison in each iteration
      for (int j = 0; j < size - i - 1; j++) {
        // Sort the array in ascending order
        if (sortOrder == 1) {
          // Compare adjacent elements
          if (array[j] > array[j + 1]) {
            // Swap if left element is greater than right
            int temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
          }
        }
        // Sort the array in descending order
        else {
          // Compare adjacent elements
          if (array[j] < array[j + 1]) {
            // Swap if left element is smaller than right
            int temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
          }
        }
      }
    }
  }

  // Driver code
  public static void main(String args[]) {
    // Create an array
    int[] data = { -2, 45, 0, 11, -9 };

    // Create a Scanner object to take input
    Scanner input = new Scanner(System.in);

    // Ask the user for sorting order
    System.out.println("Choose Sorting Order:");
    System.out.println("1 for Ascending \n2 for Descending");
    int sortOrder = input.nextInt();

    // Validate input
    if (sortOrder != 1 && sortOrder != 2) {
      System.out.println("Invalid input. Please enter 1 or 2.");
      input.close();
      return;
    }

    // Create an object of Main class
    Main bs = new Main();

    // Call the method bubbleSort using object bs
    // Pass the array and sorting order as arguments
    bs.bubbleSort(data, sortOrder);

    // Display the sorted array
    if (sortOrder == 1) {
      System.out.println("Sorted Array in Ascending Order:");
    } else {
      System.out.println("Sorted Array in Descending Order:");
    }
    System.out.println(Arrays.toString(data));

    // Close the Scanner
    input.close();
  }
}

Java Program to Implement Quick Sort Algorithm

import java.util.Arrays;

class Quicksort {

  // Method to find the partition position
  static int partition(int array[], int low, int high) {
    // Choose the rightmost element as pivot
    int pivot = array[high];
    // Pointer for greater element
    int i = (low - 1);

    // Traverse through all elements
    // Compare each element with the pivot
    for (int j = low; j < high; j++) {
      if (array[j] <= pivot) {
        // If element smaller than pivot is found
        // Swap it with the greater element pointed by i
        i++;
        // Swapping element at i with element at j
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }

    // Swap the pivot element with the greater element specified by i
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    // Return the position from where partition is done
    return (i + 1);
  }

  // Method to perform QuickSort
  static void quickSort(int array[], int low, int high) {
    if (low < high) {
      // Find the pivot element such that
      // Elements smaller than pivot are on the left
      // Elements greater than pivot are on the right
      int pi = partition(array, low, high);

      // Recursive call on the left of pivot
      quickSort(array, low, pi - 1);

      // Recursive call on the right of pivot
      quickSort(array, pi + 1, high);
    }
  }

  // Driver code
  public static void main(String args[]) {
    // Input array
    int[] data = { 8, 7, 2, 1, 0, 9, 6 };
    System.out.println("Unsorted Array:");
    System.out.println(Arrays.toString(data));

    // Call quickSort() on array
    quickSort(data, 0, data.length - 1);

    // Output the sorted array
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

Java Program to Implement Merge Sort Algorithm

import java.util.Arrays;

// Merge sort in Java
class Main {

  // Merge two subarrays L and M into array
  void merge(int array[], int p, int q, int r) {

    // Sizes of the two subarrays
    int n1 = q - p + 1;
    int n2 = r - q;

    // Temporary arrays
    int L[] = new int[n1];
    int M[] = new int[n2];

    // Fill the left and right arrays
    for (int i = 0; i < n1; i++)
      L[i] = array[p + i];
    for (int j = 0; j < n2; j++)
      M[j] = array[q + 1 + j];

    // Indices for traversing L, M, and the main array
    int i = 0, j = 0, k = p;

    // Merge the temporary arrays into the main array
    while (i < n1 && j < n2) {
      if (L[i] <= M[j]) {
        array[k] = L[i];
        i++;
      } else {
        array[k] = M[j];
        j++;
      }
      k++;
    }

    // Copy any remaining elements of L
    while (i < n1) {
      array[k] = L[i];
      i++;
      k++;
    }

    // Copy any remaining elements of M
    while (j < n2) {
      array[k] = M[j];
      j++;
      k++;
    }
  }

  // Divide the array into two subarrays, sort them, and merge them
  void mergeSort(int array[], int left, int right) {
    if (left < right) {

      // Find the middle point
      int mid = left + (right - left) / 2;

      // Recursively sort each half
      mergeSort(array, left, mid);
      mergeSort(array, mid + 1, right);

      // Merge the sorted halves
      merge(array, left, mid, right);
    }
  }

  public static void main(String args[]) {

    // Create an unsorted array
    int[] array = { 6, 5, 12, 10, 9, 1 };

    // Print the original array
    System.out.println("Unsorted Array:");
    System.out.println(Arrays.toString(array));

    // Create an object of Main class
    Main ob = new Main();

    // Call the method mergeSort()
    ob.mergeSort(array, 0, array.length - 1);

    // Print the sorted array
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(array));
  }
}


Java Program to Implement Binary Search Algorithm

import java.util.Scanner;

// Binary Search in Java
class Main {

  // Method to perform binary search
  int binarySearch(int array[], int element, int low, int high) {

    // Repeat until the pointers low and high meet each other
    while (low <= high) {

      // Get the index of the mid element
      int mid = low + (high - low) / 2;

      // Check if the element is the mid element
      if (array[mid] == element)
        return mid;

      // If the element is greater than the mid element,
      // search only the right side of mid
      if (element > array[mid])
        low = mid + 1;

      // If the element is less than the mid element,
      // search only the left side of mid
      else
        high = mid - 1;
    }

    // Element not found
    return -1;
  }

  public static void main(String args[]) {

    // Create an object of the Main class
    Main obj = new Main();

    // Create a sorted array
    int[] array = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;

    // Get input from the user for the element to be searched
    Scanner input = new Scanner(System.in);

    System.out.println("Enter the element to be searched:");
    int element = input.nextInt();
    input.close();

    // Call the binary search method
    // Pass arguments: array, element, index of first and last element
    int result = obj.binarySearch(array, element, 0, n - 1);

    // Display the result
    if (result == -1)
      System.out.println("Element not found in the array.");
    else
      System.out.println("Element found at index: " + result);
  }
}

Theory Part:
Write down the following in your notebook.

1. Bubble Sort

Concept:

  • A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
  • The process is repeated until the list is sorted.

Key Points:

  • Time Complexity:
    • Best Case: O(n) (when the array is already sorted).
    • Worst Case: O(n²).
  • Space Complexity: O(1) (in-place sorting).
  • Suitable for small datasets but inefficient for large ones.

2. Quick Sort

Concept:

  • A divide-and-conquer algorithm that selects a pivot element and partitions the array into two sub-arrays:
    • Elements less than the pivot.
    • Elements greater than the pivot.
  • Recursively applies the same logic to sub-arrays.

Key Points:

  • Time Complexity:
    • Best and Average Case: O(n log n).
    • Worst Case: O(n²) (occurs when the pivot is poorly chosen, e.g., the smallest or largest element in an already sorted array).
  • Space Complexity: O(log n) (due to recursion).
  • Efficient for large datasets.

3. Merge Sort

Concept:

  • Another divide-and-conquer algorithm that:
    • Divides the array into halves until each sub-array contains a single element.
    • Merges these sub-arrays in a sorted manner.

Key Points:

  • Time Complexity: O(n log n) in all cases.
  • Space Complexity: O(n) (requires temporary arrays for merging).
  • Stable sorting algorithm (maintains the relative order of equal elements).

4. Binary Search

Concept:

  • Searches for an element in a sorted array by repeatedly dividing the search interval in half.
  • Compares the target value to the middle element.

Key Points:

  • Time Complexity: O(log n).
  • Space Complexity: O(1) (iterative) or O(log n) (recursive).
  • Works only on sorted arrays. If the array is unsorted, sort it first (e.g., using Merge Sort).

Comments

Post a Comment

Popular posts from this blog

Programming Notes by Atul Kalukhe

Arrays in C Programming Introduction to Python Programming Circle Part 1 Set A Set B Sorting Algorithm for all programming languages Bubble Sort Selection Sort Insertion Sort: Merge Sort: Quick Sort: Radix Sort: Bucket Sort: Heap Sort JAVA Notes User-Defined Functions in Java Java Type Casting For 20 and 21 December (Java Batch) Swing Exception Handling in Java 23 Jan Java Prog 1 23 Jan Java Prog 2 Python Notes Numpy Library Pandas library 20 dec Example Python MCQ Test (25 Marks) The Pandas library Lecture 1 What is tkinter? Pygame Library Bouncing Ball Explanation Catch the Falling Object Game Explanation C Programming Notes C Prog Notes triangle patterns using numbers in C 20 Dec Example in C C Prog MCQ Test (25 Marks) 23 Jan C Prog 1 SS 23 Jan C Prog 2 SS DS Using CPP Data Structures Using C++ Sorting Algorithms: Bubble Sort and Selection Sort with C++ Implementation Python Notes (Vrushali's Batch) Introduction to Python Data structures in Python Math Library in Python 23 Jan P...
Read more