알고리즘에 대한 참고 사항

나는 CS50: Introduction to Computer Science에서 edx.org을 하고 있다. 메모를 작성하고 다시 작성하고 공유하여 배운 내용을 복습할 수 있는 좋은 방법입니다.

참고: Big O 표기법은 "순서대로"일 수 있으며 알고리즘의 실행 시간을 나타냅니다. C 예제에서 n 은 JavaScript에서 sizeof(arr)/sizeof(arr[0]) 으로 변환되는 arr.length 과 같습니다.

3주는 알고리즘에 관한 것입니다. 😺

목차


  • Linear Search
  • Binary Search
  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Recursion
  • Merge Sort

  • 선형 검색

    To iterate across the array from left to right searching for a target element.

    Pseudocode example #1:

    Repeat, starting at the first element:
        If the element is the target element, stop
        Else, move to the next element
    

    Pseudocode example #2:

    For i from 0 to n–1
        If i'th element is target_element
            Return true
    Return false
    

    C example:

    bool linearSearch(int arr[], int n, int target) 
    { 
        for (int i = 0; i < n; i++) 
            if (arr[i] == target) return true;
        return false; 
    } 
    

    JavaScript example:

    linearSearch = (arr, target) => {
        for (let i = 0; i < arr.length; i++)
            if (arr[i] === target) return true;
        return false;
    }
    

    Linear Search algorithm's

    • Worst case scenario:
      Having to look through the entire array of n elements in the case where the target element is the last one or it is not in the array.
      In Big O notation, it translates to O(n).

    • Best case scenario:
      The target element is the 1st element.
      In Big O notation, it translates to Ω(1).

    이진 검색

    To find the target element by reducing the search area by half each time. Make sure the array on which the binary search algorithm is used on is sorted, else it's impossible to make assumptions about its content.

    Pseudocode example #1:

    Repeat until the (sub)array is of size 0:
        Calculate the middle point of the current (sub)array
        If the target element is the middle element, stop
        Else if it's less than the middle: 
            End point is now just to the left of the current middle, repeat
        Else if it's greater than the middle: 
            Start point is now just to the right of the current middle, repeat
    

    Pseudocode example #2:

    If no items
        Return false
    If middle item is target_element
        Return true
    Else if target_element < middle item
        Update end point
        Search left half
    Else if target_element > middle item
        Update start point
        Search right half
    

    C example (recursive):

    int binarySearch(int arr[], int target, int start, int end) 
    { 
        if (end >= start) { 
            // instead of (start+end)/2 to avoid overflow
            int mid = start+(end-start)/2; 
            if (arr[mid] == target) return mid; 
            else if (arr[mid] > target) return binarySearch(arr, target, start, mid-1); 
            else return binarySearch(arr, target, mid+1, end); 
        } 
        return -1; 
    }
    

    JavaScript example (recursive):

    binarySearch = (arr, target, start, end) => {   
        if (end >= start) {
            let mid = Math.floor((start+end)/2);
            if (arr[mid] === target) return mid;
            else if(arr[mid] > target) return binarySearch(arr, target, start, mid-1); 
            else return binarySearch(arr, target, mid+1, end); 
        }
        return false;
    } 
    

    Binary Search algorithm's

    • Worst case scenario:
      Having to divide a list of n elements in half repeatedly to find the target element because the target is found at the end of the last division or it is not in the array.
      In Big O notation, it translates to O(log n).

    • Best case scenario:
      The target element is at midpoint of the array, so we can stop searching immediately after we start.
      In Big O notation, it translates to Ω(1).

    버블 정렬

    To sort in a bubbling way: move higher values towards the right of the array and lower values, towards the left.

    Pseudocode example #1:

    Set swap counter to a non-zero value
    Repeat until the swap counter is equal to 0:
        Reset swap counter to 0
        Look at each adjacent pair:
            If two adjacent elements are not in order:
                Swap them
                Add one to the swap counter
    

    Pseudocode example #2:

    Repeat until no swaps
        For i from 0 to n–2
            If i'th and i+1'th elements out of order
                Swap them
    

    C example:

    void bubbleSort(int arr[], int n) 
    { 
        for (int i = 0; i < n-1; i++)
            for (int j = 0; j < n-i-1; j++)
                if (arr[j] > arr[j+1])
                {
                    int temp = arr[j]; 
                    arr[j] = arr[j+1]; 
                    arr[j+1] = temp;
                }
    } 
    

    JavaScript example:

    bubbleSort = arr => {
        for (let i = 0; i < arr.length-1; i++)
            for (let j = 0; j < arr.length-i-1; j++)
                if (arr[j] > arr[j+1]) {
                    let temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
        return arr;
    }
    

    Because comparing the i th and i+1 th element, the sorting only needs to go up to n-2 for i before swapping the two elements if they're out of order. Knowing the largest n-1 elements will have bubbled to the right, the sorting can stop after n-1 passes.
    When re-going through the array, only consider the unsorted elements.
    When the swap counter remains at 0 , there is nothing else to swap.

    Bubble sort algorithm's

    • Worst case scenario:
      Having to bubble each of the elements all the way across the array because the array is in reverse order. Since it's only possible to fully bubble one element into its sorted position per pass, the sorting must happen n times.
      In Big O notation, it translates to O(n²).

    • Best case scenario:
      The array is already perfectly sorted, resulting in no swapping on the first pass.
      In Big O notation, it translates to Ω(n).

    선택 정렬

    To find the smallest unsorted element and add it to the end of the sorted list.

    Pseudocode example #1:

    Repeat until there is no unsorted elements remaining:
        Search unsorted part of data to find the smallest value
        Swap the found value with the first element of the unsorted part
    

    Pseudocode example #2:

    For i from 0 to n–1
        Find smallest item between i'th item and last item
        Swap smallest item with i'th item
    

    C example:

    void selectionSort(int arr[], int n) 
    { 
        for (int i = 0; i < n-1; i++)
        {
            int min = i; 
            for (int j = i+1; j < n; j++) 
                if (arr[j] < arr[min]) min = j;
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
    

    JavaScript example:

    selectionSort = arr => { 
        for (let i = 0; i < arr.length-1; i++) {
            let min = i; 
            for (let j = i+1; j < arr.length; j++)
                if (arr[j] < arr[min]) min = j;
            let temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
        return arr;
    }
    

    Selection sort algorithm's

    • Worst case scenario:
      Having to repeat the sorting process n times to iterate each of the n elements of the array to find the smallest unsorted element and sort it. Only one element gets sorted on each pass.
      In Big O notation, it translates to O(n²).

    • Best case scenario:
      The same as the worst case scenario as there is no way to guarantee the array is sorted until the sorting process iterates over all of the elements of the array.
      In Big O notation, it translates to Ω(n²).

    삽입 정렬

    To build a sorted array in place; shifting elements out of the way to make room if necessary as the array is being built.

    Pseudocode example #1:

    Call the first element of the array sorted
    Repeat until all elements are sorted:
        Insert next unsorted item into sorted part shifting the required number of items
    

    Pseudocode example #2:

    For i from 1 to n–1
        Insert next unsorted item into sorted part shifting i items
    

    C example:

    void insertionSort(int arr[], int n) 
    { 
        for (int i = 1; i < n; i++) { 
            int key = arr[i]; 
            int j = i-1; 
            while (j >= 0 && arr[j] > key) { 
                arr[j+1] = arr[j]; 
                j = j-1; 
            } 
            arr[j+1] = key; 
        } 
    } 
    

    JavaScript example:

    insertionSort = arr => { 
        for (let i = 1; i < arr.length; i++) { 
            let key = arr[i]; 
            let j = i-1; 
            while (j >= 0 && arr[j] > key) { 
                arr[j+1] = arr[j]; 
                j = j-1; 
            } 
            arr[j+1] = key; 
        } 
        return arr;
    } 
    

    Insertion sort algorithm's

    • Worst case scenario:
      Having to shift each of the n elements from n positions each time to make an insertion because the array is in reverse order.
      In Big O notation, it translates to O(n²).

    • Best case scenario:
      The array is already sorted. Only gotta keep moving between unsorted and sorted elements as we iterate over each of them.
      In Big O notation, it translates to Ω(n).

    재귀

    To code elegantly. 🌹

    Recursion is related to how an algorithm or a function is implemented, it isn't an algorithm itself.

    A recursive function invokes itself as part of its execution.

    Detailed example using the factorial function:

    • n! is defined over all positive integers
    • n! equals all of the positive integers less than or equal to n, multiplied together
    • n! as fact(n) :

    Pseudocode example #1:

    fact(1) = 1
    fact(2) = 2 * 1
    fact(3) = 3 * 2 * 1
    …
    

    Pseudocode example #2:

    fact(1) = 1
    fact(2) = 2 * fact(1)
    fact(3) = 3 * fact(2)
    …
    

    The basis for a recursive definition of the factorial function:

    fact(n) = n * fact(n-1)
    

    Recursive function has two cases that can apply given any input:

    • Base case: terminates the recursive process when triggered
    • Recursive case: where the recursion happens
    int fact(int n) 
    {
        // base case
        if (n == 1)
            return 1;
        // recursive case
        else
            return n * fact(n-1);
    }
    

    There can be multiple base cases.
    Example the fibonacci number sequence where:

    • 1st element is 0
    • 2nd element is 1
    • n th element is the sum of (n-1)+(n-2)

    There can be multiple recursive cases.
    Example the collatz conjecture.

    The next C and JavaScript examples define a collatz function that calculates how many steps it takes to get "back to 1":

    C example:

    int collatz(int steps) 
    {
        // base case
        if (steps == 1) return 0;
        // recursive case: even numbers
        else if ((steps % 2) == 0) return 1+collatz(steps/2);
        // recursive case: odd numbers
        else return 1+collatz(3*steps+1);
    }
    

    JavaScript example:

    collatz = steps => {
        // base case
        if (steps == 1) return 0;
        // recursive case: even numbers
        else if ((steps % 2) == 0) return 1+collatz(steps/2);
        // recursive case: odd numbers
        else return 1+collatz(3*steps+1);
    }
    

    병합 정렬

    To divide an array into smaller arrays to sort and then, combine those sorted arrays back together in sorted order.

    Pseudocode example #1:

    If only one element
      Return
    Else
        Sort left half of elements
        Sort right half of elements
        Merge sorted halves
    

    Pseudocode example #2:

    Sort the left half of the array (assuming n > 1)
    Sort right half of the array (assuming n > 1)
    Merge the two halves together
    

    C example (recursive):

    // merges two subarrays of arr[]
    void merge(int arr[], int leftIndex, int mid, int rightIndex) 
    { 
        int n1 = mid-leftIndex+1; 
        int n2 =  rightIndex-mid; 
    
        // temp arrays
        int Left[n1], Right[n2]; 
    
        // copy data to temp arrays
        for (int i = 0; i < n1; i++) 
            Left[i] = arr[leftIndex+i]; 
        for (int j = 0; j < n2; j++) 
            Right[j] = arr[mid+1+j]; 
    
        // merge the temp arrays back into arr[]
        int i = 0; // init index of 1st subarray 
        int j = 0; // init index of 2nd subarray 
        int k = leftIndex; // init index of merged subarray 
        while (i < n1 && j < n2) 
        { 
            if (Left[i] <= Right[j]) 
            { 
                arr[k] = Left[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = Right[j]; 
                j++; 
            } 
            k++; 
        } 
    
        // copy the remaining elements of Left[], if any
        while (i < n1) 
        { 
            arr[k] = Left[i]; 
            i++; 
            k++; 
        } 
    
        // copy the remaining elements of Right[], if any
        while (j < n2) 
        { 
            arr[k] = Right[j]; 
            j++; 
            k++; 
        } 
    } 
    
    void mergeSort(int arr[], int leftIndex, int rightIndex) 
    {   
        if (leftIndex < rightIndex) 
        { 
            // instead of (l+r)/2 to avoid overflow
            int mid = leftIndex+(rightIndex-leftIndex)/2; 
            // sort first and second halves 
            mergeSort(arr, leftIndex, mid); 
            mergeSort(arr, mid+1, rightIndex); 
            // merge them back together
            merge(arr, leftIndex, mid, rightIndex); 
        } 
    } 
    

    JavaScript example (recursive):

    // to merge left subarray and right subarray
    merge = (left, right) => {
        let resultArray = [], leftIndex = 0, rightIndex = 0;
    
        // concat values into the resultArray in order
        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] < right[rightIndex]) {
                resultArray.push(left[leftIndex]);
                leftIndex++;
            } else {
                resultArray.push(right[rightIndex]);
                rightIndex++;
            }
        }
    
        // concat remaining element from either left OR right
        return resultArray
            .concat(left.slice(leftIndex))
            .concat(right.slice(rightIndex));
    }
    
    mergeSort = arr => {
        // if array has one element or is empty, no need to sort
        if (arr.length <= 1) return arr;
    
        const mid = Math.floor(arr.length/2);
        // divide the array into left and right
        const left = arr.slice(0, mid);
        const right = arr.slice(mid);
    
        // merge back together using recursion
        return merge(mergeSort(left), mergeSort(right));
    }
    

    Merge sort algorithm's

    • Worst case scenario:
      Having to split n elements up before recombining them effectively, doubling the sorted sub-arrays as they are built.
      In Big O notation, it translates to O(n log n).

    • Best case scenario:
      The array is already sorted, but still gotta be split and recombined back together to know it is sorted.
      In Big O notation, it translates to Ω(n log n).

    Resources:

  • Comparison Sorting Algorithms (visualization)
  • Sorting Algorithms on brilliant.org
  • Sorting Algorithms on geeksforgeeks.org
  • Sorting Algorithms Visualized
  • 좋은 웹페이지 즐겨찾기