Algorithm

알고리즘은 어떤문제를 해결하고자하는 절차이며 컴퓨터 언어에서는 이 알고리즘은 굉장히 중요하며 유용하다.
하지만 알고리즘을 이해하려면 컴퓨터적 사고방식(Computational Thinking)은 필수이다.
우리의 언어, 생각 등을 컴퓨터가 이해할 수 있는 방식으로 전달해야 하는데 이를 위해서는 컴퓨터 언어의 이해가 필수이며, 이를 통해 문제를 단순화하여 컴퓨터에게 전달한다.
가령 앞으로 걷는다라는 명제는 사람에게는 굉장히 당연하고 단순한 것이지만 이를 컴퓨터에게 이해시키려면

1. 왼쪽 발의 위치가 오른쪽 발 앞에 있는지 ? --> yes or no
2. yes라면 오른쪽 발을 전진시킨다. --> 1.로 돌아가 반복 수행한다.
3. no라면 왼쪽 발을 전진시킨다. --> 1.로 돌아가 반복 수행한다.

단순화해도 이런식의 과정이 필요할 것이다.
반대로 2 ** 50을 계산하라고 사람에게 시키면 이를 쉽게 계산하는 이는 거의 없을 것이다.
허나, 컴퓨터는 이를 순식간에 계산할 수 있다.

이처럼 사람과 컴퓨터는 각각의 사고과정이 다르기 때문에 우리는 끊임없이 컴퓨터적 사고방식(Computational Thinking)을 길러야 한다.

1. Selection Sort(선택정렬)

선택정렬의 정렬방식

어떠한 수들의 배열(array)이 있을 때 이를 정렬하는 방식은 수도 없이 많을 것이다.
기 증에 우리가 알아볼 첫번째 정렬방식은 선택정렬(selection sort)이다.
선택정렬은 어떠한 수들의 배열(array)이 있을 때 이들 중 가장 작은 값을 앞으로 보내어 정렬하는 방식이다.

여기서 앞으로 보낸다는 뜻은 앞에 있던 원래의 값과 자리를 바꾼다는 것을 의미한다.

예를들어

arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9]라는 배열이 있다면 10(=== arr[0])부터 9(=== arr[9])까지 배열의 값들을 하나하나씩 살펴본 후 그 중 가장 작은 값을 선택한다.
그리고 그 중 가장 작은 값인 1(=== arr[1])을 index 0부터 9중에 0의 자리(arr[0])에 배치한다.

이 과정을 통해 arr[1]부터 arr[9]까지의 값들 중 arr[0]보다 작은 값은 이제 없다.
그러면 arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]이 된다.
그러면 이번엔 10(=== arr[1])부터 9(=== arr[9]까지 배열의 값들을 하나하나씩 살펴본 후 그 중 가장 작은 값을 선택한다.
그리고 그 중 가장 작은 값인 2(=== arr[8])을 index 1부터 9중에 1의 자리(arr[1])에 배치한다.
이 과정을 통해 arr[2]부터 arr[9]까지의 값들 중 arr[1]보다 작은 값은 이제 없다.
그러면 arr = [1, 2, 5, 8, 7, 6, 4, 3, 10, 9]이 된다.
이러한 과정을 총 10번 반복하게 되면 정렬된 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 될 것이다.

선택정렬의 코드화

위에서 정리한 내용을 토대로 선택정렬을 코드화 해보도록 하자.

{
    let arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9];
}

처음으로는 정렬해야 될 변수 arr를 선언하고 이 변수에 array를 할당해보자.

ECMAscript(ES6, 2015) 이후 부터는 기본적인 변수는 letkeyword를 통해 선언하는 것이 일반적이다.(Block Level Scope)

그 후 for문을 작성하고, 이 정렬해야 될 배열의 값들 보다 절대적으로 큰 값을 하나 정의한다.

이는 초기의 가장 작은 값을 찾는 역할을 한다.

{
    let arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9];
    for (let i = 0; i < 10; i++) {
        let min = 9999;
    }
}

처음 선택정렬에 대해 설명했을 때 가장 중요한 것은 가장 작은 값을 앞으로 보내어 정렬하는 방식이라는 것이다.
이는 다른 말로 앞으로 보내진 값은 이제 무시하고 정렬을 수행해도 된다는 말이다.
왜냐하면 arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9]라는 배열이 한번 정렬되어 arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]이 된다면
그 어떤 값도 arr[0]보다는 작은 값을 가질 수 없으므로 다음 사이클에는 우리는 arr[0]을 제외한 arr = [1, //// 10, 5, 8, 7, 6, 4, 3, 2, 9] 부분에서 가장 작은 값을 찾으면 되는 것이다.
이는 for문안에 for문을 작성하여 구현할 수 있다.

{
    let arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9];
    for (let i = 0; i < 10; i++) {
        let min = 9999;
        for (j = i; j < 10; j++) {
            // something
        }
    }
}

이렇게 되면 i = 0일 때 j = 0부터 j = 9까지시행되며, 그 다음은 i = 1이 되어 j = 1부터 j = 9까지시행되고,
이러한 패턴이 반복되 마지막으론 i = 9이 되어 j = 9부터 j = 9까지시행되게 될 것이다.
이 이중 반복문 안에 가장 작은 값을 찾고 이를 앞으로 보낸다는 코드를 //something자리에 넣으면 된다.
이는 if문으로 할 수 있으며 다음과 같다.

{
    let arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9];
    for (let i = 0; i < 10; i++) {
        let min = 9999;
        for (j = i; j < 10; j++) {
            if (min > arr[j]) {
                min = arr[j];
                index = j;
            }
            else {
                continue;
            }
        temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
        }
    }
    console.log(arr);
}

if문을 통해 min과 arr[0](i = 0, j = 0으로 시작하므로)을 비교하여 가장 작은 값을 설정하고 앞의 값과 가장 작은 값을 swapping한다.
swapping을 하기 위해서는 기본적으로 아래와 같은 세줄의 코드가 필요한데

temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;

이 코드가 이해가 안된다면 그림을 통해 좀 더 직관적으로 살펴보고 이해해보자.

feature: assets/img/swapping.jpg

Swapping의 순서는

1. 먼저 자리를 바꿀 두 값을 결정한다.
2. 이 값 중에서 한 값을(통상적으로 앞의 값을) temp라는 변수에 할당한다.
3. temp에 할달되지 않은 변수를 temp에 할당된 변수자리에도 똑같이 할당한다.

   이렇게 하면 같은 값이 2번 할당되게 됨.

4. temp에 할당 된 변수를 위치를 바꿔야 할 곳에 할당한다.

이렇게 4가지 단계를 거치며 이를 Temporary variable swapping이라고 한다.

이렇게 swapping까지 마치면 선택정렬은 끝이나며
console.log(arr)로 출력 시 arr[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 출력되는 것을 볼 수 있다.

선택정렬의 Big O 표기법

Big O notation(빅오표기법)은 굉장히 큰 n의 입력이 들어왔을 때 가장 최악의 복잡도를 갖게 될 경우 몇 번의 연산 과정(O(n))을 거치는지에 관한 표기법이다.
예를 들어 O(n) = n은 n번의 입력이 들어오면 최악의 복잡도를 갖게 되는 경우 n번의 연산 과정을 거쳐야 한다는 말이다.

우리가 오늘 배운 선택정렬에서의 채택한 정렬방법은 모든 값을 살펴본 후 가장 작은 값을 앞으로 보내고,
그 다음 연산에서는 앞으로 보내진 값을 제외하고 다시한번 모든 값을 살펴본 후 가장 작은 값을 앞으로 보내고,
또 다시 앞으로 보내진 값을 제외한 나머지 값들을 모두 살펴보고 가장 작은 값을 앞으로 보내고의 연속이다.

따라서 오늘 우리가 예시로 들었던 n = 10의 경우에는

1. i = 0 일때, 10개의 값을 살펴봄 --> 10회
2. i = 1 일때, 9개의 값을 살펴봄 --> 9회
3. i = 2 일때, 8개의 값을 살펴봄 --> 8회
   ···
4. i = 9 일때, 1개의 값을 살펴봄 --> 1회

즉 입력 n = 10일때, 연산과정은 1회 + 2회 + ··· + 10회 = 55회가 된다.
우리는 고등학교 1학년 때 수열이라는 과목을 배웠다.(혹은 배웠다고 가정하겠다.)
여기서 우리는 n이 1씩 증가하는 수열의 합은 (n+(n+1))/2라고 배운 것을 기억할 수 있다.

즉 O(n) = (n+(n+1))/2임을 알 수 있다. 하지만 앞서 말한 것 처럼 Big O notation의 핵심은 n이 굉장히 클 때이다.

무한한 값(∞)에 1을 더한들 그 값은 여전히 무한한 값이다. 또, 무한한 값을 2로 나눈다 한들 그 값은 여전히 무한한 값이다.
따라서, n이 굉장히 크다면 n에 붙어있는 상수들은 무시한다. (여기서 주의할 점은 차수의 무시가 아닌 상수의 무시다.)

이를 통해 상수들을 모두 제거하면 O(n) = n ** 2 즉, O(n ** 2)힘을 알 수 있다.

Summary

Selection Sort(선택정렬)의 정렬방식은 모든 값을 살펴본 후 그 중 가장 작은 값을 앞으로 보내는 행위의 반복을 통해 정렬하는 방식이다.
앞으로 보내진 값은 모든 값들 중 가장 작인 값이므로 다음 값들을 살펴볼 때에는 이를 제외하고 살펴봐도 무방하다.
앞으로 원소를 보낸다는 것은 두 원소의 자리를 바꾼다는 의미인데 이를 위해 Swapping이라는 기법을 사용하며, 여기서는 Temporal Variable Swapping기법을 사용하였다.
Big O notation(빅오표기법)은 굉장히 큰 n의 입력이 들어왔을 때 가장 최악의 복잡도를 갖게 될 경우 몇 번의 연산 과정(O(n))을 거치는지에 관한 표기법인데
오늘 살펴본 선택정렬의 복잡도는 O(n ** 2)이다.

Reference

• Youtube : Algorithm Programming Tutorial - by Dongbin Na
• 4 Ways to Swap Variables in JavaScript
• Swapping Items in an Array