Scribd
Upload
2 views3 pages

Java Implementation For Two Fundamental Algorithms

The document provides Java implementations for two fundamental algorithms: Bubble Sort and Binary Search. Bubble Sort is a simple sorting algorithm with a time complexity of O(n) in the best case and O(n^2) in average/worst cases, while Binary Search is an efficient searching algorithm with a time complexity of O(log n) that requires a sorted array. Both algorithms include performance analyses and example code demonstrating their functionality.

Uploaded by

Miki Mikaa
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views3 pages

Java Implementation For Two Fundamental Algorithms

The document provides Java implementations for two fundamental algorithms: Bubble Sort and Binary Search. Bubble Sort is a simple sorting algorithm with a time complexity of O(n) in the best case and O(n^2) in average/worst cases, while Binary Search is an efficient searching algorithm with a time complexity of O(log n) that requires a sorted array. Both algorithms include performance analyses and example code demonstrating their functionality.

Uploaded by

Miki Mikaa
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

JAVA IMPLEMENTATION FOR TWO FUNDAMENTAL

ALGORITHMS: BINARY SEARCH (SEARCHING) AND


BUBBLE SORT (SORTING).

Sorting Algorithm – Bubble Sort

Bubble Sort is a simple, comparison-based algorithm. It works by repeatedly


stepping through the list, comparing adjacent elements, and swapping them if they are
in the wrong order. This process "bubbles" the largest unsorted element to its correct
position at the end of the list in each iteration.

Java Implementation: Bubble Sort

Java
public class BubbleSortDemo {
public static void bubbleSort(int[] arr) {
int n = [Link];
boolean swapped;

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


swapped = false;
// Last i elements are already in place
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap adjacent elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were swapped by inner loop, then break
if (!swapped) break;
}
}

public static void main(String[] args) {


int[] data = {64, 34, 25, 12, 22, 11, 90};
[Link]("Original Array: " + [Link](data));

bubbleSort(data);

[Link]("Sorted Array: " + [Link](data));


}
}
Performance Analysis

 Best Case Time Complexity: $O(n)$ (when the array is already sorted).

 Average/Worst Case Complexity: $O(n^2)$.

 Space Complexity: $O(1)$ (In-place sorting).

Searching Algorithm – Binary Search


Binary Search is an efficient algorithm for finding an item from a sorted list of
items. It works by repeatedly dividing the search interval in half. If the value of the
search key is less than the item in the middle of the interval, narrow the interval to the
lower half. Otherwise, narrow it to the upper half.

Java Implementation: Binary Search

Java
public class BinarySearchDemo {
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = [Link] - 1;

while (low <= high) {


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

// Check if target is present at mid


if (arr[mid] == target) {
return mid;
}

// If target is greater, ignore left half


if (arr[mid] < target) {
low = mid + 1;
}
// If target is smaller, ignore right half
else {
high = mid - 1;
}
}
return -1; // Target not found
}

public static void main(String[] args) {


int[] sortedData = {11, 12, 22, 25, 34, 64, 90};
int target = 25;

int result = binarySearch(sortedData, target);


if (result == -1) {
[Link]("Element not present in array.");
} else {
[Link]("Element " + target + " found at index: " + result);
}
}
}

Performance Analysis

 Time Complexity: $O(\log n)$.

 Space Complexity: $O(1)$ for the iterative approach.

 Prerequisite: The input array must be sorted beforehand.

You might also like