2022년 2월 25일 금요일

what is Selection Sort algorithm

2월 25, 2022 Eunhan's library

Selection Sort Algorithm

Definition

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

Algorithm steps

find smallest number in the list
swap the smallest number and first place
the first element is sorted
find smallest number in the list except the sorted element.
swap the smallest number and second place
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

Java code

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

How to calculate

numbers of loop

$n-1$

The most visited place of the list

$n-1$ (the last place)

The least visited place of the list

$1$ (the first 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)$

Algorithm Study

No Comments

2022년 2월 24일 목요일

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

compare two numbers
smaller number will be left and bigger number will be in right side.
compare over and over again until the end of the list
Now, biggest number will stay in most right side. This number is sorted
Start over from first number except sorted place.
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)$

Algorithm Study

No Comments

2022년 2월 22일 화요일

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

insert data into binary tree
The data sorted as binary tree
print

Avg.

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

Worst time complexity

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

space complexity

$O(1)$

stability

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/

Algorithm Study

No Comments

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();
    }
}

Algorithm Study

No Comments

2022년 2월 21일 월요일

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

Algorithm Study

No Comments

2022년 2월 20일 일요일

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

Algorithm Study

No Comments

2022년 2월 19일 토요일

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;}

Java Study

No Comments

2022년 2월 18일 금요일

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.

Coding Technique

No Comments

2022년 2월 17일 목요일

what is Hash Crash

2월 17, 2022 Eunhan's library

Hash Crash or Hash Collision

Definition

one of the hash function's problems .

If the input value is different, the output value should be different.
But, the output is same.

less hash crush is better
No hash crush is almost impossible. We calls that "perfect hash function"
If you limited insert value a lot, you may create the perfect hash function

Example of Hash Crash

insert "A" --Hash Function--> return "3"
insert "B" --Hash Function--> return "1"
insert "C" --Hash Function--> return "3"

inserted values are different, but the returned values are same

check this- what is Hashing or Hash Algorithm

Algorithm Study

No Comments

what is Hashing or Hash Algorithm

2월 17, 2022 Eunhan's library

Hash Algorithm

Definition

1. Hashing or Hash function

one of mathematical function that converts an input of arbitrary length into an encrypted output of a fixed length.

Example of Hash function

insert "A" --Hash Function--> return "123"
insert "ABG" --Hash Function--> return "778"
insert "HEU" --Hash Function--> return "998"

2. Hash Data Structure

Programmers used hash function to create many data structures.

Examples of Java Hash Data Structures

Hash set
LinkedHashSet
Hash table
Hash map
LinkedHashMap
TreeSet
ConcurretHashMap

3. Hash Algorithm

Programmers used the hash data structures to solve problems.
The way to solving problems is Hash algorithm

Characteristics

Hash Data Structures need more memories than total list n
The worst case, Hash algorithm can be slow because of hash collision

Properties

Hash crash or hash collision
efficiency
uniformity
collision resistance
pre-image resistance
second pre-image resistance

Hash algorithms can be used as..

encryption
store values
verify same files or not

Algorithm Study

No Comments

what is Fibonacci sequence

2월 17, 2022 Eunhan's library

Definition

Certain patterns of numbers.
first and second numbers are always 0,1. next number is addition of previous two numbers

The List of Fibonacci numbers

$0,1,1,2,3,5,8,13,21,34,55...$

Recurrence Relation

$F_0=0$
$F_1=1$
$F_n=F_{n-1}+F_{n-2}$

Example

index	fibonacci numbers	calculation
0	0	0
1	1	1
2	1	0+1
3	2	1+1
4	3	1+2
5	5	2+3
6	8	3+5
7	13	5+8
8	21	8+13
9	34	13+21
10	55	21+34
11	89	34+55
12	144	55+89
13	233	89+144
14	377	144+233
15	610	233+377
16	987	377+610

Math

No Comments

tags

Popular Posts

2022년 2월 25일 금요일

Selection Sort Algorithm

Definition

Algorithm steps

Avg. time complexity

Worst time complexity

space complexity

stability

Java code

How to calculate

numbers of loop

The most visited place of the list

The least visited place of the list

Avg. visited numbers of the list

Polynomial Time

Time Complexity

2022년 2월 24일 목요일

Bubble Sort Algorithm

Definition

Algorithm steps

Avg. time complexity

Worst time complexity

space complexity

stability

Java code

How to calculate

numbers of loop

The most visited place of the list

The least visited place of the list

Avg. visited numbers of the list

Polynomial Time

Time Complexity

2022년 2월 22일 화요일

Heap Sort Algorithm

Definition

Algorithm steps

Avg.

Worst time complexity

space complexity

stability

insert time complexity

print time complexity

Java code

Brute Force Algorithm

Definition

Points

Example

2022년 2월 21일 월요일

Binary Search Algorithm

Definition

Time complexity

Example

Explanation

step 1

step 2

step 3

step 4

step 5

step 6

step 7

2022년 2월 20일 일요일

Linear Search Algorithm

Definition

Time complexity

Example

Explanation

step 1

step 2

step 3

step 4

step 5

2022년 2월 19일 토요일

enum in Java

Definition

Reason for using the enum

History

C code example

result