[CS50X] Week3 번외편(Sort 구현 - Selection, Bubble, Merge, 비트연산자 )

번외편을 따로 만든 이유는 3주차 Algorithms 에서 

Selection, Bubble, Merge Sort가 나오는데

바로 구현하기 내용이 어려운 것과 정렬한 결과를 Array 로 return 하는 것이 자연스러운데

C에서 return Array 이런식으로 동작하지 않기 때문에 포인터 개념을 알고 있어야 했다.

그래서 4주차 Memory 에서 포인터에 대해 배운 덕분에 구현 할 수 있게 되었다.

추가적으로 비트 연산자 관련 내용도 같이 다루려 한다.

 

Selection Sort - O(n^2),  Ω(n^2)

#include <stdio.h>

int SelectionSort(int numbers[], int length);
int Swap(int *a, int *b);
int main(void)
{
    int numbers[10] = {7, 3, 1, 9, 5, 8, 2, 6, 0, 4};
    SelectionSort(numbers, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
}

int SelectionSort(int numbers[], int length)
{
    for (int i = 0; i < length; i++)
    {
        int smaller = 10;
        int smallindex;
        for (int j = i; j < length; j++)
        {
            if (numbers[j] < smaller)
            {
                smaller = numbers[j];
                smallindex = j;
            }
        }
        Swap(&numbers[i], &numbers[smallindex]);
    }
    return 0;
}

int Swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return 0;
}

 

 

 

 

 

Bubble Sort - O(n^2),  Ω(n)

#include <stdio.h>

int BubbleSort(int numbers[], int length);
int Swap(int *a, int *b);
int main(void)
{
    int numbers[10] = {7, 3, 1, 9, 5, 8, 2, 6, 0, 4};
    BubbleSort(numbers, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
}

int BubbleSort(int numbers[], int length)
{
    int counter;
    do
    {
        counter = 0;
        for (int i = 0; i < length-1; i++)
        {
            if (numbers[i] > numbers[i+1])
            {
                Swap(&numbers[i], &numbers[i+1]);
                counter++;
            }
        }
    }
    while (counter != 0);
    return 0;
}

int Swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return 0;
}

 

 

 

 

 

 

Merge Sort - O(n log n),  Ω(n log n)

#include <stdio.h>

int MergeSort(int numbers[], int start, int end);
int main(void)
{
    int numbers[10] = {7, 3, 1, 9, 5, 8, 2, 6, 0, 4};
    MergeSort(numbers, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
}

int MergeSort(int numbers[], int start, int end)
{
    if (start == end)
    {
        return 0;
    }
    else
    {
        int middle = (start+end) / 2;
        // 왼쪽 정렬
        MergeSort(numbers, start, middle);
        // 오르쪽 정렬
        MergeSort(numbers, middle + 1, end);
        // 합치기
        int L[middle-start+1];
        int R[end-middle];
        for (int i = 0; i < middle - start + 1; i++)
        {
            L[i] = numbers[i + start];
        }

        for (int i = 0; i < end - middle; i++)
        {
            R[i] = numbers[i + middle + 1];
        }

        int LS = 0;
        int RS = 0;

        for (int i = start; i < end+1; i++)
        {
            if (LS >= middle-start+1)
            {
                numbers[i] = R[RS];
                RS++;
            }
            else if (RS >= end-middle)
            {
                numbers[i] = L[LS];
                LS++;
            }
            else
            {
                if (L[LS] < R[RS])
                {
                    numbers[i] = L[LS];
                    LS++;
                }
                else
                {
                    numbers[i] = R[RS];
                    RS++;
                }
            }
        }
        return 0;
    }
    return 0;
}

 

 

후기

정렬 알고리즘을 구현해보면서 부족한 점을 많이 느낄 수 있었다.

우선 배열 arr[0] 는 구현될때 arr 포인터로 주소로 이동하여 *(arr+0) 이런식으로 작동한다.

그래서 굳이 배열을 인자로 전달했을때 복사 문제와 return 을 신경쓰지 않아도 됐다.

병합 정렬은 구현하기 생각보다 까다로웠는데 재귀라는 개념 자체가 익숙하지 않은 점과

index 를 꼼꼼하게 통제하는 것이 부족해서 그랬던 것 같다.

 

 

 

 

비트연산자

비트 연산자에 대해 잘 모르다가 ProblemSet4 filter 를 풀다가 알게 되었는데

알아두면 실제 코딩과 알고리즘에서 유용하게 쓰일 것 같아서 따로 정리해보려 한다.

비트 연산자의 경우 C언어에서 성능을 올리고 알고리즘을 간단히 하는 것에 기여하고

타 언어에서도 사용 가능하다.

1. AND 연산자 &: 두 비트 모두 1일 경우에만 1을 반환합니다. 예를 들어, 5 & 3은 0101 & 0011이므로 결과는 0001 (1)입니다.
2. OR 연산자 |: 두 비트 중 하나라도 1이면 1을 반환합니다. 예를 들어, 5 | 3은 0101 | 0011이므로 결과는 0111 (7)입니다.
3. XOR 연산자 ^: 두 비트가 서로 다를 때 1, 같을 때 0을 반환합니다. 예를 들어, 5 ^ 3은 0101 ^ 0011이므로 결과는 0110 (6)입니다.
4. NOT 연산자 ~: 비트를 반전시킵니다. 1은 0으로, 0은 1로 바뀝니다. 예를 들어, ~5는 ~0101이므로, 결과는 특정 시스템에서 1111 1010 (2의 보수 표현에서 -6)일 수 있습니다.
5. 왼쪽 시프트 연산자 <<: 지정된 비트 수만큼 왼쪽으로 이동시키고, 새로 생기는 비트는 0으로 채웁니다. 예를 들어, 5 << 1은 0101을 왼쪽으로 한 비트 이동시켜 1010 (10)이 됩니다.
6. 오른쪽 시프트 연산자 >>: 지정된 비트 수만큼 오른쪽으로 이동시키고, 새로 생기는 비트는 부호 비트(양수면 0, 음수면 1)와 동일하게 채워집니다(부호 있는 정수의 경우). 예를 들어, 5 >> 1은 0101을 오른쪽으로 한 비트 이동시켜 0010 (2)이 됩니다.

정수에서 << 1 은 *2 와 같고 >> 1 은 /2 와 같다. 실수에선 다르다.

비트 연산자를 잘 이해하기 위해선

정수표현 방법, 실수 표현 방법, 정수의 덧셈과 뺄셈(2의 보수 표현)방법에 대한 이해가 필요하다.

4번 예시에서 ~5를 반전시키면 -6이 된다고 나오는데 이것은 2의 보수 표현법을 알아야 이해 가능하다.

2의 보수 표현 방법은 음수를 이진수로 표현하기 위해 사용된 방법으로 정수의 뺄셈에도 사용된다.

컴퓨터에서 정수는 보통 32bit (4bytes) or 64bit 이지만 예시를 위해 8bit로 생각해보자.

5를 이진수로 표현하면 0000 0101 이고 이것을 반전하면 1111 1010 이다. 그렇다면 1111 1010 은 어떻게 표현될까?

가장 앞자리 비트 (최상위 비트)가 1이기 때문에 2의 보수 표현 방법을 사용하면 

1. 모든 비트를 반전시킨다. 0000 0101

2. 1을 더한다. 0000 0110

이렇게 되면 6이라는 정수가 나오는데 가장 앞자리 비트가 1이기 때문에 음수인 -6이 되는 것이다.

 

사실 정수의 뺄셈은 음수를 더한 것과 같다.

5-3 을 연산한다고 하면

-3 의 보수 표현 = 1111 1101

5를 표현한 0000 0101 과 -3 을 표현한 1111 1101 를 더하는 것이다. 

이진수로 두 수를 더해보면, 1 0000 0010 이 된다.

하지만 맨 앞자리 1을 오버플로우로 처리가 되지 않기 때문에 

최종적으로는 0000 0010 이 되는 것이다. 그리고 이것은 2이다.

 

비트 연산자를 잘 활용한 문제가 있어서 가져와봤다.

위 문제는 어떤 배열을 탐색해서 1번만 등장한 수를 찾는 문제이다.

구현 할 수 있는 방법은 다양하지만 시간 복잡도는 O(n) 으로 제한되어 있다.

시간 복잡도 O(n)으로 구현하려면 2중 for문과 정렬 알고리즘을 사용하기 힘들다.

비트 연산자로 고민해본다면 xor ^ 연산자는 비트가 같으면 0을 반환하기 때문에

2 ^ 2 를 하면 0이 된다. 이를 통해 효과적으로 중복을 제거 할 수 있다.

#include <stdio.h>

int main(void)
{
    int nums[5] = {4,1,2,1,2};
    int result = 0;
    for (int i = 0; i < 5; i++)
    {
        result^=nums[i];
    }
    printf("%i\n", result);
}

 

 

실수 표현 방법을 이해하기 위해선 부동소수점에 대해 알아야한다.

이 내용은 새로운 포스팅에서 다루는게 적절할 것 같다.