[Data Structures] 챕터1. 기본개념

std::swap

 

선택정렬

---

전체 배열에서 가장 작은 값을 찾는다.

나머지 값에서 두 번째로 작은 값을 찾는다.

...

 

함수의 매개변수를 포인터로 정의하고 인수가 배열일 때 배열의 범위 밖 데이터를 불러올 수 있다.

void OutOfRange(int* arr, int size)
{
    cout << arr[size+1] << endl; // -858993460
}

int main()
{
    int arr[5] = {0, 1, 2, 3, 4};
    OutOfRange(arr, 5);
}

범위 밖 데이터를 사용할 경우 사용자가 인지하지 못하는 버그를 발생시킨다.

 

선택정렬의 구현

매 번 swap하면 비효율적이다.

int arr[] = { 8, 3, 2, 5, 1, 1, 2, 5, 8, 9 };
int size = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < size - 1; i++)
{
    for (int j = i+1; j < size; ++j)
    {
        if (arr[j] < arr[i])
            swap(arr[j], arr[i]);
    }
}

 

index만 저장하여 내부의 반복문이 끝난 후 한 번만 swap하면 효율적이다

int arr[] = { 8, 3, 2, 5, 1, 1, 2, 5, 8, 9 };
int size = sizeof(arr) / sizeof(arr[0]);

int min_index;
for (int i = 0; i < size - 1; ++i)
{
    min_index = i;
    for (int j = i+1; j < size; ++j)
    {
        if (arr[j] < arr[min_index])
            min_index = j;
    }
    swap(arr[i], arr[min_index]);
}

 

Google Spreadsheet 활용하기

1. comma로 구분되어있는 값을 google spreadsheet에 붙여넣는다

2. Split text to columns로 열을 구분한다.

3. 차트로 만든다.

 

선택정렬은 안정성(Stability)이 없다

아래의 구조체의 특정 값을 기준으로 정렬했다고 하자.  

struct Element
{
    int key;
    char value;
};

Element arr[] = { {2, 'a'}, {2, 'b'}, {1, 'c'} };
// Sorting ...

key 값을 중심으로 정렬이 된 후에도 구조체의 다른 값의 순서가 정렬 전과 동일하다면 stable 성질을 가진 정렬이다.

다른 값의 순서가 정렬 전과 다르다면 unstable 성질을 가진 정렬이다.

Element arr[] = { {1, 'c'}, {2, 'b'}, {2, 'a'}};

 

버블 정렬

---

- 두 값을 비교하여 큰 값을 오른쪽으로 전달한다.

1. 요소 대부분이 정렬되어 있을 경우 버블 정렬은 효율적이다.

2. 모든 값을 비교하기 때문에 매 번 정렬 여부를 판단할 수 있다.

3. 안정성이 보장된다.

 

버블정렬의 구현

//int arr[] = { 5, 1, 4, 2, 8 }; // 위키피디아 예시
//int arr[] = { 5, 4, 3, 2, 1 }; // Worst Case
int arr[] = { 1, 2, 3, 5, 4 };   // Best Case
int n = sizeof(arr) / sizeof(arr[0]);

for (int start = 0; start < n-1; ++start)
{
    bool isSorted = true;
    for (int i = 0; i < n-1-start; ++i)
    {
        if (arr[i] > arr[i + 1])
        {
            swap(arr[i], arr[i + 1]);
            isSorted = false;
        }
        Print(arr, n);
    }

    if (isSorted)
        break;

    cout << endl;
}

변수 isSorted를 활용하여 조기 종료하고 있다. 비교 회수를 줄일 수 있다.

 

버블정렬은 안정성을 가진다

버블 정렬은 key값이 동일한 경우 순서를 바꾸지 않는다. 따라서 value 값의 순서는 바뀌지 않는다.

 

삽입 정렬

---

구현 방법 소개

1. 전체 배열을 둘로 나눈다.

2. 한 쪽이 정렬된 상태로 유지할 수 있게 최소한으로 작업한다.

3. 새로 삽입되는 값은 정렬된 값에서 큰값부터 비교하여 자리를 찾는다(가장 큰 값 보다 크다면 정렬 되었다고 판단한다) 

4. 큰 값이 비교값보다 여전히 크다면 비교값의 자리로 당겨 자리잡는다.

이 때 메모리를 새로 할당받지는 않으므로 삽입되는 값은 임시로 저장했다가 자리를 찾으면 할당한다. 

 

삽입정렬의 구현 준비

for 반복문 내부의 it-else분기에서 break를 호출할 때 코드를 더 간단하게 표현할 수 있다.

int key = arr[i];

for(int j=i; 0<j; --j)
{
    if (3 < arr[j-1])
    {
        arr[j] = arr[j - 1];
    }
    else
    {
        arr[j] = key;
        break;
    }
}

1. it-else의 분기 조건을 for 반복문의 조건으로 이동

2. 반복문의 index를 외부에서 정의

3. break와 함께 발생하는 구현을 반복문 외부에서 구현 

int key = arr[i];
int j = i;
for (; (0 < j) && (3 < arr[j - 1]); --j)
{
    arr[j] = arr[j - 1];
}

arr[j] = key;

이를 while로 구현하면 더 깔끔하다.

 

삽입정렬의 구현

int arr[] = { 8, 3, 2, 5, 1, 2 };
//int arr[] = { 6, 5, 4, 3, 2, 1 }; // Worst
//int arr[] = { 1, 2, 3, 4, 5, 6 }; // Best

int n = sizeof(arr) / sizeof(arr[0]);

for (int i = 1; i < n; ++i)
{
    int key = arr[i];
    int j = i;
    while (0 < j)
    {
        if (arr[j - 1] <= key)
        {
            break;
        }
        arr[j] = arr[j-1];

        --j;
    }
    arr[j] = key;
}

 

삽입정렬은 안정성을 가진다

while (0 < j && key < arr[j - 1])
{
    arr[j] = arr[j - 1];
    --j;
}
arr[j] = key;

앞에서부터 정렬하는 삽입정력일 때, 삽입할 값은 뒤에 있는 값이다.

삽입할 값이 정렬된 값과 비교했을 때 동일하다면 그 뒤에 위치하므로 순서가 변하지 않는다.

 

삽입 정렬 VS 버블 정렬

버블 정렬은 Swap 때 값을 3번 할당한다(temp 포함)

삽입 정렬은 Shift 하므로 값을 1번 할당한다.

따라서 삽입 정렬이 버블 정렬보다 효율적이다.

 

순차 탐색(선형 탐색)

---

 

정렬 되면 개수를 세거나 탐색하기 쉽다.

int SortedCount(int* arr, int n, int x)
{
    int i = SequentialSearch(arr, n, x);

    if (i >= 0)
        // 일단 하나를 찾았으므로 개수를 늘리고 다음 idx부터 찾는다
        return SortedCountHelper(arr, n, x, i + 1) + 1; 
    else
        return 0;
}

 

문자열 압축 문제

---

'\0' null character는 제외하므로 문자열의 숫자는 -1이 필요하다

char arr[] = "ababcdfdceeedag";
int n = sizeof(arr) - 1; // 마지막 안보이는 '\0' 제외

// 글자가 하나이상이라고 가정
// 글자가 없으면 if로 아예 수행을 안하도록 처리 가능
assert(n >= 1);

참고. std::string.length()은 null character를 제외한 문자열 개수를 출력한다

 

이진 탐색

---

정렬된 배열에서 효율적으로 값을 찾을 수 있다.

이진탐색 구현방법

1. Index 3개를 사용한다. Left, Right, Middle. 이 때 Left 이상, Right 이하의 범위를 사용함이 일반적이다.

2. Middle 값을 Key 값과 비교하여 Left 혹은 Right index를 변경하여 범위를 좁힌다.

    (Left를 Middle값 보다 키우거나 Right를 Middle값 보다 줄인다)

...

3. (1) 값을 찾을 경우

값 하나가 남았을 때 Left와 Right의 index의 중간값을 선택하게 되므로 별도 구현이 필요하지 않다.

3. (2) 값을 찾지 못 했을 경우

Left > Right이 발생했다면 찾지 못한 경우이다.

 

주의사항

1) C++에서 정수/정수 = 정수

int x = 4/3;
cout << x; // 1

 

2) 같은 값이 여러 개 있을 때 이진 탐색의 결과가 가장 앞에 있는 index임을 보장하지 않는다.

값을 찾았을 경우 왼쪽의 여러 값을 확인해준다.

 

참고

올림(Floor)과 버림(Ceil) 연산 기호 https://en.wikipedia.org/wiki/Floor_and_ceiling_functions

https://github.com/HongLabInc/HongLabDataStructures/blob/main/Ex0107_BinarySearch/Ex0107_BinarySearch.cpp

 

성능측정

---

알고리즘의 성능

- 배열의 크기가 커졌을 때 연산시간이 어느 정도 비율로 늘어나는지 측정한다

- 배열의 크기가 커질 때 증가하는 추세가 완만해지는 알고리즘은 뛰어나다

 

컴파일러의 최적화

예) 반환 값이 있지만 사용하지 않을 경우 컴파일러가 해당 명령어를 무시하여 최적화한다.

 

이진탐색 vs 선형탐색 비교하기

없는 값을 찾았을 때 가장 오래걸리는 시간을 확인할 수 있다.

0~n-1을 가진 n개의 배열에서 없는 값 n을 찾아보자

예) 10개 짜리 배열에서 11번째 값을 찾는다. 모든 값을 탐색하고 예외 상황을 처리해야 한다.

for (int n = 1; n <= kNumTest; n += int(pow(2, 10)))
{
    int* x_table = new int[n + 1];

    for (int i = 0; i < n; i++) {
        x_table[i] = i;
    }

    x_table[n] = n; // 못 찾을 값

    ShuffleArray(x_table, n + 1); // 찾는 수를 임의로 섞는다
    
    ...
    
    for (int x = 0; x < n + 1; x++)  // 못 찾는 경우를 하나 마지막에 추가
    {
        int x_find = x_table[x]; // 찾을 값(못 찾는 경우가 섞여 있음)

        // Sequential Search
        {
            int* arr = new int[n];
            for (int i = 0; i < n; i++) // 정렬된 0~(n-1) 값 중 하나를 찾는다
                arr[i] = i;

            result_seq = SequentialSearch(arr, n, x_find); // TEST 1
            ...
            delete[] arr;
        }
        
        ...
        
        // Binary Search
        {
            int* arr = new int[n];
            for (int i = 0; i < n; i++) // 정렬된 0~(n-1) 값 중 하나를 찾는다
                arr[i] = i;

            result_bi = BinarySearch(arr, n, x_find); // TEST 1
            ...
            delete[] arr;
        }
    }
}

 

https://github.com/HongLabInc/HongLabDataStructures/blob/main/Ex0108_PerformanceMeasurement/Ex0108_PerformanceMeasurement.cpp

선형 탐색 vs 이진 탐색 (평균)

 

 

이진탐색 VS 선형탐색 최악의 경우 비교하기

배열에 존재하지 않는 값을 찾을 때 평균값 확인하기

result_seq = SequentialSearch(arr, n, n + rand() % 1000); // TEST 2

선형 탐색 vs 이진 탐색 (최악)

 

시간복잡도

---

- 알고리즘의 이론적인 성능(속도)를 복잡도로 표현한다.

- 평균의 경우를 계산할 필요는 없다(넘어가도 됨)

순차 탐색의 시간복잡도

최선의 경우 : 1번

최악의 경우 : n번

평균의 경우 : (n+1)/2번

 

점근 표기법(Big-O)

배열의 크기가 아주 클 때 알고리즘 대강의 성능

순차 탐색의 시간복잡도

최선의 경우 : 1번    = O(1)

최악의 경우 : n번    = O(n) 배열과 비례하여 오래걸린다.

평균의 경우 : (n+1)/2번 = O(n/2 + 1/2) = O(n)

 

이진 탐색의 시간 복잡도

최선의 경우 : 1번                 = O(1)

최악의 경우 : Log2(N) + 1    = O( log2(N) )

참고) 배열에 없는 값을 찾는 경우를 확인해야하므로 마지막에 1을 더한다

평균의 경우 : 

(1번 만에 찾는 경우 : 1), (2번 만에 찾는 경우 : 2), (3번 만에 찾는 경우 : 4), (4번 만에 찾는 경우 : 1)

(1번 * 1개 + 2번 * 2개 + 3번 * 4개 + 4번 * 1개 ) / 8 = (1+4+12+4)/8 = 21/8 = O( Log2(N) )

https://www.geeksforgeeks.org/complexity-analysis-of-binary-search/

https://sceweb.uhcl.edu/yang/teaching/csci3333fall2011/Average%20case%20analysis%20of%20binary%20search.pdf

https://www.knowledgehut.com/blog/programming/time-complexity-of-binary-search

 

참고) 배열의 크기가 2배 늘어나도 1번만 더 비교하면 된다

 

 

공간 복잡도

---

메모리 공간을 얼마나 사용하는가

 

선형탐색의 공간복잡도

O(1) , int i

배열의 크기와 공간복잡도는 상관이 없다

int SequentialSearch(int* arr, int n, int x)
{
    int i;
    for (i = 0; i < n && arr[i] != x; i++);
    if (i == n) return -1;
    else return i;
}

 

이진탐색의 공간복잡도

O(1), int left, int right, int middle

배열의 크기와 공간복잡도는 상관이 없다

int BinarySearch(int* arr, int n, int x)
{
    int left = 0;
    int right = n - 1;

    while (left <= right)
    {
        int middle = (left + right) / 2; // 정수 나누기 (버림)

        if (x < arr[middle])
            right = middle - 1;
        else if (x > arr[middle])
            left = middle + 1;
        else
            return middle;
    }

    return -1; // Not found
}

 

선택정렬

시간복잡도

1) 계산하기

int arr[] = { 8, 3, 2, 5 };
int size = sizeof(arr) / sizeof(arr[0]);

int min_index;
for (int i = 0; i < size - 1; ++i)
{
    min_index = i;
    // (8 3 2 5)에서 가장 작은 값
    // 2 (3 8 5)에서 가장 작은 값
    // 2 3 (8 5)에서 가장 작은 값
    // 2 3 5 (8)에서 가장 작은 값
    // Outer loop는 n-1 번
    // Inner Loop는 
    // n-1, n-2, n-3, ..., 1
    
    for (int j = i+1; j < size; ++j)
    {
        if (arr[j] < arr[min_index])
            min_index = j;
    }
    swap(arr[i], arr[min_index]);
}

(n-1) + (n-2) + ... + 1 = ( N(N-1) ) / 2 = O(N^2/2 - n/2) 이 때 n 값이 커질 때 n^2에 비해 n 값은 작으므로 무시한다.

따라서 O(n^2)

 

2) 직관적으로 예측하기

바깥 Loop와 내부 Loop가 n번씩 반복하므로 O(n^2)

 

공간복잡도

Swap을 사용하므로 O(1)

 

	최선	최악	평균	공간
선택	O(n^2)	O(n^2)	O(n^2)	O(1)
버블	O(n)	O(n^2)	O(n^2)	O(1)
삽입	O(n)	O(n^2)		O(1)

 

버블 정렬의 최선이 O(n)인 이유

OuterLoop의 첫 시행때 Inner Loop가 isSorted일 경우 break 한다.

이 때 n-1 반복하였으므로 O(n)이다

for (int start = 0; start < n-1; ++start)
{
    bool isSorted = true;
    for (int i = 0; i < n-1-start; ++i)
    {
        if (arr[i] > arr[i + 1])
        {
            swap(arr[i], arr[i + 1]);
            isSorted = false;
        }
    }

    if (isSorted)
        break;
}

 

삽입 정렬의 최선이 O(n)인 이유

 

지나간 index는 항상 정렬되어 있다. Inner Loop는 정렬되어있을 때 생략하므로 최선의 경우 Outer Loop만 진행하면 된다.

for (int i = 1; i < n; ++i)
{
    int key = arr[i];
    int j = i;
    while (0 < j)
    {
        if (arr[j - 1] <= key)
        {
            break;
        }
        arr[j] = arr[j-1];

        --j;
    }

    arr[j] = key;
}

 

참고) 선택정렬 시간 복잡도 표

https://www.geeksforgeeks.org/time-and-space-complexity-analysis-of-selection-sort/