Bubble sorting
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.
notes:
package Sorting;
public class Example {
public static void main(String[] args) {
int[] a = {50,40,30,20,10};
for(int i=0; i<a.length-1;i++)
{
if(a[i]>a[i+1])
{
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}
for(int i=0; i<a.length; i++)
System.out.print(a[i] + " ");
System.out.println("Maximum " + a[a.length-1]);
}
}
output:
40 30 20 10 50 Maximum 50
notes2:
int[] a = {100,90,80,70,60,50,40,30,20,10};
for(int j=1; j<a.length; j++)
{
for(int i=0; i<a.length-j;i++)
{
if(a[i]>a[i+1])
{
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}
}
for(int i=0; i<a.length; i++)
System.out.print(a[i] + " ");
output:
10 20 30 40 50 60 70 80 90 100
Insertion sort
Insertion Sort is a simple sorting algorithm that sorts the array one element at a time by comparing it with the elements before it and inserting it into the correct position.
int[] arr = {5, 2, 4, 1, 3};
Step-by-step sorting:
- Compare 2 with 5 → insert before 5 → [2, 5, 4, 1, 3]
- Compare 4 → insert between 2 and 5 → [2, 4, 5, 1, 3]
- Compare 1 → insert at beginning → [1, 2, 4, 5, 3]
- Compare 3 → insert between 2 and 4 → [1, 2, 3, 4, 5]
[TBD]
public class InsertionSortExample {
public static void main(String[] args) {
int[] a = {100, 90, 80, 70, 60, 50, 40, 30, 20, 10};
for (int j = 1; j < a.length; j++) {
int key = a[j];
int i = j - 1;
// Move elements that are greater than key to one position ahead
while (i >= 0 && a[i] > key) {
a[i + 1] = a[i];
i = i - 1;
}
a[i + 1] = key;
}
// Print sorted array
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
}
}
Merge sort:
Merge Sort is a divide and conquer algorithm.
Input array: [38, 27, 43, 3, 9, 82, 10]
Steps:
- Split: [38, 27, 43] and [3, 9, 82, 10]
- Recursively split until one element remains
- Merge back in sorted order → Final result: [3, 9, 10, 27, 38, 43, 82]
[TBD]
public class MergeSortExample {
// Function to merge two subarrays
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temp arrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data
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];
// Merge the temp arrays
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main mergeSort function
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge sorted halves
merge(arr, left, mid, right);
}
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr, 0, arr.length - 1);
// Print sorted array
System.out.print("Sorted array: ");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}
Quick sort[TBD]
Quick Sort is a divide-and-conquer sorting algorithm.
It works by:
1.Choosing a pivot element from the array.
2.Partitioning the array so that:
- Elements less than the pivot go to the left.
- Elements greater than the pivot go to the right. 3.Then it recursively sorts the left and right parts.
Input: [30, 10, 50, 20, 60, 40]
Choose pivot = 40
Partition: [30, 10, 20] [40] [50, 60]
Then sort left and right recursively
Final result: [10, 20, 30, 40, 50, 60]
[TBD]
public class QuickSortExample {
// Partition function
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // Choosing last element as pivot
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and pivot
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Return pivot index
}
// QuickSort function
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
// Recursively sort left and right
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String[] args) {
int[] arr = {30, 10, 50, 20, 60, 40};
quickSort(arr, 0, arr.length - 1);
// Print sorted array
System.out.print("Sorted array: ");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}
Binary search
Binary Search is an efficient algorithm for finding an element in a sorted array by repeatedly dividing the search interval in half.
- It compares the target value to the middle element.
- If they are not equal, it eliminates half of the array where the target cannot lie.
- Repeats until the target is found or the search interval is empty.
package Sorting;
import java.util.Scanner;
public class Example4 {
public static void main(String[] args) {
int[] ar = {10,56,78,87,99,100};
Scanner sc = new Scanner(System.in);
System.out.println("Enter key to search: ");
int key = sc.nextInt();
int min = 0, max = ar.length-1;
while(min<=max)
{
int mid = (min + max)/2;
if(key == ar[mid])
{
System.out.println("Your key is present in index " + mid);
break;
}
else if(key<ar[mid])
{
max = mid - 1;
}
else
{
min = mid + 1;
}
}
}
}
output:
Enter key to search:
56
Your key is present in index 1
Linear Search is the simplest searching algorithm. It checks each element in the array one by one from the beginning until it finds the target element or reaches the end.
public class LinearSearchExample {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Return index if found
}
}
return -1; // Return -1 if not found
}
public static void main(String[] args) {
int[] arr = {10, 25, 30, 45, 50};
int target = 45;
int result = linearSearch(arr, target);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index: " + result);
}
}
}
output:
Element found at index: 3
Top comments (0)