-------------------BUBBLE SORT -----------------
public class Main{
// bubble sort = pairs of adjacent elements are compared, and the elements
// swapped if they are not in order.
// Quadratic time O(n^2)
// small data set = good-ish
// large data set = BAD (plz don't)
public static void main(String[] args) {
int array[] = {9, 1, 8, 2, 7, 3, 6, 4, 5};
bubbleSort(array);
for(int i : array) {
System.out.print(i);
}
}
public static void bubbleSort(int array[]) {
for(int i = 0; i < array.length - 1; i++) {
for(int j = 0; j < array.length - i - 1; j++) {
if(array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
-------------------BUBBLE SORT -----------------
-------------------INSERTION SORT -----------------
public class Main{
// Insertion sort = after comparing elements to the left,
// shift elements to the right to make room to insert a
value
// Quadratic time O(n^2)
// small data set = decent
// large data set = BAD
// Less steps than Bubble sort
// Best case is O(n) compared to Selection sort O(n^2)
public static void main(String[] args) {
int array[] = {9, 1, 8, 2, 7, 3, 6, 5, 4};
insertionSort(array);
for(int i : array) {
System.out.print(i + " ");
}
}
private static void insertionSort(int[] array) {
for(int i = 1; i < array.length; i++) {
int temp = array[i];
int j = i - 1;
while(j >= 0 && array[j] > temp) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
}
YT LINK : https://www.youtube.com/watch?v=8mJ-OhcfpYg
-------------------INSERTION SORT -----------------
-------------------SELECTION SORT -----------------
public class Main{
// selection sort = search through an array and keep track of the minimum
value during
// each iteration. At the end of each iteration, we
swap values.
// Quadratic time O(n^2)
// small data set = okay
// large data set = BAD
public static void main(String[] args) {
int array[] = {8, 7, 9, 2, 3, 1, 5, 4, 6};
selectionSort(array);
for(int i : array) {
System.out.print(i);
}
}
private static void selectionSort(int[] array) {
for(int i = 0; i < array.length - 1; i++) {
int min = i;
for(int j = i + 1; j < array.length; j++) {
if(array[min] > array[j]) {
min = j;
}
}
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
YT LINK : https://www.youtube.com/watch?v=EwjnF7rFLns&t=195s
-------------------SELECTION SORT -----------------
-------------------BINARY SEARCH ALGO -----------------
import java.util.Arrays;
public class Main{
// binary search = Search algorithm that finds the position
// of a target value within a sorted array.
// Half of the array is eliminated during each "step"
public static void main(String[] args) {
int array[] = new int[1000000];
int target = 777777;
for(int i = 0; i < array.length; i++) {
array[i] = i;
}
//int index = Arrays.binarySearch(array, target);
int index = binarySearch(array, target);
if(index == -1) {
System.out.println(target + " not found");
}
else {
System.out.println("Element found at: " + index);
}
private static int binarySearch(int[] array, int target) {
int low = 0;
int high = array.length - 1;
while(low <= high) {
int middle = low + (high - low) / 2;
int value = array[middle];
System.out.println("middle: " + value);
if(value < target) low = middle + 1;
else if(value > target) high = middle - 1;
else return middle; //target found
}
return -1;
}
}
YT LINK : https://www.youtube.com/watch?v=xrMppTpoqdw&t=194s
-------------------BINARY SEARCH ALGO -----------------
-------------------LINEAR SEARCH ALGO -----------------
public class Main{
public static void main(String args[]){
// linear search = Iterate through a collection one element at a time
int[] array = {9, 1, 8, 2, 7, 3, 6, 4, 5};
int index = linearSearch(array, 5);
if(index != -1) {
System.out.println("Element found at index: " + index);
}
else {
System.out.println("Element not found");
}
private static int linearSearch(int[] array, int value) {
for(int i = 0; i < array.length; i++) {
if(array[i] == value) {
return i;
}
}
return -1;
}
}
YT LINK : https://www.youtube.com/watch?v=246V51AWwZM
-------------------LINEAR SEARCH ALGO -----------------
