what is Bubble Sort algorithm

what is Bubble Sort algorithm

  2월 24, 2022    Eunhan's library

---

Bubble Sort Algorithm

Definition

one way of sorting algorithms by using brute force.
check every possible ways to sort the list.

Algorithm steps

1. compare two numbers
2. smaller number will be left and bigger number will be in right side.
3. compare over and over again until the end of the list
4. Now, biggest number will stay in most right side. This number is sorted
5. Start over from first number except sorted place.
6. Repeat 1~5 until all of them sorted.

Avg. time complexity

$O(n^2)$

Worst time complexity

$O(n^2)$

space complexity

$O(1)$

stability

yes

Java code

    public static int[] bubbleSort(int[] input) {
        for (int i = 0; i < input.length - 1; ++i) {
            for (int j = 0; j < input.length - i - 1; ++j) {
                if (input[j] > input[j + 1]) {
                    int temp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = temp;
                }
            }
        }
        return input;
    }

---

How to calculate

numbers of loop

$n-1$

The most visited place of the list

$n-1$ (the first place)

The least visited place of the list

$1$ (the last place)

Avg. visited numbers of the list

(The most visited place of the list+The least visited place of the list)/2 $= \frac{(n-1+1)}{2} = \frac{n}{2}$

Polynomial Time

numbers of loop*Avg. visited numbers of the list $=(n-1)\cdot \frac{n}{2}$

Time Complexity

$O(Polynomial\; Time)=O((n-1)\cdot \frac{n}{2})=O(\frac{n^2}{2}-\frac{n}{2})=>O(n^2)$

Read More

what is Heap Sort algorithm

what is Heap Sort algorithm

  2월 22, 2022    Eunhan's library

---

Heap Sort Algorithm

Definition

one way of sorting algorithms by using binary tree data structure

Algorithm steps

insert data into binary tree and print out from the tree

1. insert data into binary tree
2. The data sorted as binary tree
3. print

Avg.

$O(n\, log\, n)$

Worst time complexity

$O(n\, log\, n)$

space complexity

$O(1)$

stability

no

insert time complexity

$O(log\, n)$

print time complexity

$O(n)$

Java code

    public static void heapSort(int arr[]) {
        int n = arr.length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapTree(arr, n, i);

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            heapTree(arr, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    public static void heapTree(int arr[], int n, int i) {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapTree(arr, n, largest);
        }
    }

*this code is from https://www.geeksforgeeks.org/heap-sort/

Read More

what is Brute Force Algorithm

what is Brute Force Algorithm

  2월 22, 2022    Eunhan's library

---

Brute Force Algorithm

Definition

check every possible ways to find answer.

Points

• No efficiency
• most intuitive way to solving problems

Example

import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {

        int[] inputList = {1, 9, 44, 55, 88};
        int value = 55;

        System.out.println(findNumIndexArr(inputList, value));

    }
    public static int findNumIndexArr(int[] input, int value) {
        for (int i = 0; i < input.length; ++i) {
            if (input[i] == value) {
                return i;
            }
        }
        throw new NoSuchElementException();
    }
}

Read More

what is Binary Search Algorithm

what is Binary Search Algorithm

  2월 21, 2022    Eunhan's library

---

Binary Search Algorithm

Definition

check middle of list first. if the number is smaller than what you are looking for, check right side only and doing this continuously. It will decrease search list in half.

• pre-condition : the list sorted
• pre-condition : when new data inserted, need to sort
• Since it need to sort when new data inserted, it can be very slow if there are a lot of insertion
• divide-and-conquer technique

Time complexity

$O(log\; n)$

Example

import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {

        int[] inputList = {1, 9, 44, 55, 88};
        int value = 55;

        System.out.println(getIndexValueArr(inputList, value));

    }

    private static int getIndexValueArr(int[] input, int value) {
        return binarySearchRecur(input, 0, input.length - 1, value);

    }

    private static int binarySearchRecur(int[] input,
                                         int mostLeft,
                                         int mostRight,
                                         int value) {
        if (mostRight < mostLeft) { /*value not found*/
            throw new NoSuchElementException();
        }

        int mid = mostLeft + ((mostRight - mostLeft) / 2);

        if (input[mid] == value) { /*found the value*/
            return mid;
        } else if (input[mid] > value) { /*value is left side*/
            return binarySearchRecur(input, mostLeft, mid - 1, value);
        } else { /*value is right side*/
            return binarySearchRecur(input, mid + 1, mostRight, value);
        }
    }
}

Explanation

step 1

step 2

step 3

step 4

step 5

step 6

step 7

Read More

what is Linear Search Algorithm

what is Linear Search Algorithm

  2월 20, 2022    Eunhan's library

---

Linear Search Algorithm

Definition

How to find certain element in the list.
check all elements of the list one by one to search one element.

Time complexity

O(n)

Example

import java.util.NoSuchElementException;

public class Main {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 2, 2, 5};
        System.out.println(getIndexValueArr(nums, 5));
    }

    public static int getIndexValueArr(int[] input, int value) {
        for (int i = 0; i < input.length; ++i) {
            if (input[i] == value) {
                return i;
            }
        }
        throw new NoSuchElementException();
    }
}

Explanation

step 1

step 2

step 3

step 4

step 5

Read More

what is enum

what is enum

  2월 19, 2022    Eunhan's library

---

enum in Java

Definition

enum class is for define constant.
It will contain the value that will not change during the program is working

Reason for using the enum

debugging easily.

History

C: preprocessor : certain number
Java: static final String MALE: certain string
enum in Java: enum: certain object

C code example

#include <stdio.h>

#define MALE 1 // #define Preprocessor 

int main()
{
    const int FEMALE = 2; // const keyward
    
    int input = 2;
    
    if(input==MALE){
        printf("I am male");
    }else{
        printf("I am Female");
    }

    return 0;
}

result

I am Female

if you put 3 in input variable, it still print, "I am Female" We need additional if statement for checking the issue.

In Java, we started use "final." The final is not exactly same as the Preprocessor, But we used it with static final keyward

java code example

public class Main {

    public static final String MALE = "MALE";
    public static final String FEMALE = "FEMALE";

    public static void main(String[] args) {
        String gender;
        gender = Main.MALE;
        gender = "male"; //mistake, but no error
                
        if(gender.equals(Main.MALE)){
            System.out.println("I am male");
        }else{
            System.out.println("I am female");
        }        

    }
} 

result

I am female

However, still same issue stated. The constant's data type is String and it caused wrong result.

Thus, we use enum class since java 1.5.
We calls, "enumeration", "enumerated type", and "enum"

enum java code example

public class Main {

    public static void main(String[] args) {
        Gender gender;
        gender = Gender.MALE;
        gender = "male"; //mistake, but it shows error

        if(gender==Gender.MALE){
            System.out.println("I am male");
        }else{
            System.out.println("I am female");
        }

    }
}

enum Gender {MALE, FEMALE;}

Read More

what is Dynamic Programming

what is Dynamic Programming

  2월 18, 2022    Eunhan's library

---

Dynamic Programming

Definition

One of problem solving technique

Split huge problem into many simple subproblems and reduce steps of subproblems.
Then get solution by addition of all subproblems.

Example

if you calculate $2^1+2^2+2^3+2^4+2^5$,

You can find answer by calculating
$2+(2*2)+(2*2*2)+(2*2*2*2)+(2*2*2*2*2)$

However, there is another way in computer.
$2^1=2=2$
$2^2=2*2=2^1*2$
$2^3=2*2*2=2^2*2$
$2^4=2*2*2*2=2^3*2$
$2^5=2*2*2*2*2=2^4*2$

You can skip some of parts that you already calculated. When you calculate the $2^5$, you done have to calculate $2^4$ if that number $2^4$ is already calculated.

Read More