레이블이 Algorithm Study인 게시물을 표시합니다. 모든 게시물 표시

2022년 3월 4일 금요일

what is Quick Sort

3월 04, 2022 Eunhan's library

Quick Sort

Definition

one of sort algorithms

The most important sort algorithm
Use this algorithm anywhere with any languages
The best way to avoid worst time complexity is pick pivot randomly.
if program most not have $O(n^2)$ , need to use other sorting algorithm.

Technique

Decrease and Conquer

Algorithm steps

Recusively loop based on Lomuto.

pick pivot the most right element.
left side will be smaller than pivot value and right side will be bigger than pivot.
let's say most left value is selected index and comaparing index without pivot.
if comaparing index value is smaller than pivot, swap with selected index and increase the selected index.
if comaparing index value is bigger than or equal pivot, increase the comaparing index.
when the comaparing index is equal to pivot index, swap pivot and the selected index.
Recusively loop step 1~6.

how to pick pivot

Lomuto
- pivot : the most right element.
- starting selected index (i) : 0
- starting comaparing index (j) : 0
Hoare
- pivot : the most left element.
- starting selected index (i) : 1
- starting comaparing index (j) : the most right element.
Randomly Choose

Java code - Lomuto


   public static void quickSort(int[] input) {
        quickSortRecur(input, 0, input.length - 1);
    }


    public static void quickSortRecur(int[] input, int left, int right) {

        if (left >= right) {
            return;
        }

        int pivotPos = partition(input, left, right);

        quickSortRecur(input, left, pivotPos - 1);
        quickSortRecur(input, pivotPos + 1, right);

    }

    public static void swap(int[] input, int a, int b) {
        int temp = input[a];
        input[a] = input[b];
        input[b] = temp;

    }

    public static int partition(int[] input, int left, int right) {
        int pivot = input[right];

        int i = (left - 1);
        for (int j = left; j < right; ++j) {
            if (input[j] < pivot) {
                ++i;
                swap(input, i, j);
            }
        }
        swap(input, (i + 1), right);
        return i + 1;
    }

Avg. time complexity

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

Worst time complexity

$O(n^2)$

space complexity

$O(log\, n)$

stability

How to calculate

numbers of loop

base recursion: $O(n)$
If separated evenly : $O(log\,n)$
If separated not evenly : $O(n)$

Time Complexity

If separated evenly : $O(n \cdot log\,n)=O(n\,log\,n)$
If separated not evenly (the worst case) : $O(n \cdot n)=O(n^2)$

Algorithm Study

No Comments

2022년 3월 3일 목요일

what is Merge Sort

3월 03, 2022 Eunhan's library

Merge Sort

Definition

one way of sorting algorithms by Decrease and Conquer.

Algorithm steps

Recusively loop

Recusively loop left side and right side until the input array cannot separated
every separated parts only one element is in there. This is sorted.
merge arrays with sort.

Java code


   public static void mergeSort(int[] input) {
        mergeSortRecurr(input, 0, input.length - 1);
    }

    public static void mergeSortRecurr(int[] input, int left, int right) {
        if (left < right) {
            int midPos = left + (right - left) / 2;

            mergeSortRecurr(input, left, midPos);
            mergeSortRecurr(input, midPos + 1, right);
            merge(input, left, right, midPos);
        }
    }

    public static void merge(int[] input, int left, int right, int midPos) {
        //mid pos does not check unlike the left and right
        int temp1 = midPos - left + 1;
        int temp2 = right - midPos;

        //temp array and copy
        int[] L = new int[temp1];
        int[] R = new int[temp2];
        for (int i = 0; i < temp1; ++i)
            L[i] = input[left + i];
        for (int j = 0; j < temp2; ++j)
            R[j] = input[midPos + 1 + j];


        int i = 0;
        int j = 0;
        int k = left;

        while (i < temp1 && j < temp2) {
            if (L[i] <= R[j]) {
                input[k] = L[i];
                ++i;
            } else {
                input[k] = R[j];
                ++j;
            }
            ++k;
        }

        while (i < temp1) {
            input[k] = L[i];
            ++i;
            ++k;
        }

        while (j < temp2) {
            input[k] = R[j];
            ++j;
            ++k;
        }
    }

Avg. time complexity

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

Worst time complexity

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

space complexity

$O(n)$

stability

yes

How to calculate

numbers of loop

base recursion for merge: $O(n)$
separated evenly : $O(log\,n)$

Time Complexity

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

Algorithm Study

No Comments

2022년 3월 1일 화요일

what is Insertion Sort algorithm

3월 01, 2022 Eunhan's library

Insertion Sort

Definition

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

Algorithm steps

There are two position. one is for moving the other one is for checking
When you check two values, smaller go to left side
These two positions checking started from original position.
set moving position is original position and checking position is original position-1
These two positions checking getting smaller untill the checking position reached to 0
Repeat 1~6 until all of them sorted.

Java code

    private static int[] insertSort(int[] input) {
        if (input.length < 2) {
            return input;
        }

        for (int originalPosition = 1; originalPosition < input.length; ++originalPosition) {
            int movingPostion = originalPosition;
            int checkingPostion = originalPosition - 1;

            while (checkingPostion > 0) {
                if (input[checkingPostion] > input[movingPostion]) {
                    swap(input, checkingPostion, movingPostion);
                } else {
                    break;
                }
                --checkingPostion;
                --movingPostion;
            }
        }
        return input;
    }

    private static void swap(int[] input, int pos1, int pos2) {
        int temp = input[pos2];
        input[pos2] = input[pos1];
        input[pos1] = temp;
    }

Avg. time complexity

$O(n^2)$

Worst time complexity

$O(n^2)$

space complexity

$O(1)$

stability

Algorithm Study

No Comments

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월 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

tags

Popular Posts

2022년 3월 4일 금요일

Quick Sort

Definition

Technique

Algorithm steps

how to pick pivot

Java code - Lomuto

Avg. time complexity

Worst time complexity

space complexity

stability

How to calculate

numbers of loop

Time Complexity

2022년 3월 3일 목요일

Merge Sort

Definition

Algorithm steps

Java code

Avg. time complexity

Worst time complexity

space complexity

stability

How to calculate

numbers of loop

Time Complexity

2022년 3월 1일 화요일

Insertion Sort

Definition

Algorithm steps

Java code

Avg. time complexity

Worst time complexity

space complexity

stability

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