210118(월)

순차 정렬(Sequntial Sort)

한 자리씩 순차적으로 정렬한다고 해서 순차 정렬.

내부 순환문이 한번 다 돌면 그 자리는 최솟값이 확정되고 다음 자리로 넘어간다.

 

▼ 개념

for (i = 0 > n-1)
    for (j = i+1 > n)
        if (Compare(arr[i], arr[j]) > 0)
            Swap(arr[i], arr[j]);

 

▼ 코드

#include <cstdio>

int  Compare(int lhs, int rhs);
void Swap(int* lhs, int* rhs);

int main()
{
    const int arrMax = 5;
    int iArr[5] = { 0,3,4,2,1 };

    printf("> BEFORE\n");
    for (int i = 0; i < arrMax; i++)
    {
        printf("iArr[%d] = %d\n", i, iArr[i]);
    }
    printf("\n");

    for (int i = 0; i < arrMax - 1; i++)
    {
        for (int j = i + 1; j < arrMax; j++)
        {
            if (Compare(iArr[i], iArr[j]) > 0)
            {
                Swap(&iArr[i], &iArr[j]);
            }
        }
    }

    printf("> AFTER\n");
    for (int i = 0; i < arrMax; i++)
    {
        printf("iArr[%d] = %d\n", i, iArr[i]);
    }

    return (0);
}

int  Compare(int lhs, int rhs)
{
    return (lhs - rhs);
}

void Swap(int* lhs, int* rhs)
{
    int _temp = *lhs;
    *lhs = *rhs;
    *rhs = _temp;
}

가장 흥미로웠던 점은 Compare() 함수의 개념이었다.

 

비교하는 함수야 금방 떠올릴 수 있었지만 return (lhs > rhs)가 아니라

return (lhs - rhs)도 가능하다는 것을 새삼 깨달았다.

 

bool에 비해서 ( -, 0, + )로 대소유무 뿐 아니라 동일 여부도 구분할 수 있기 때문에 더 쓰임새가 많다.

(역시 좋은 코드를 봐야 한다.)

거품 정렬(Bubble Sort)

▼ 개념

for (i = n > 1)
    for (j = 1 < i)
        if (Compare(arr[j-1], arr[j]) > 0)
            Swap(arr[j-1], arr[j]);

 

▼ 코드

#include <cstdio>

int	 Compare(int lhs, int rhs);
void Swap(int* lhs, int* rhs);

int main()
{
    const int arrMax = 10;
    int iArr[arrMax] = { 9,3,4,2,1,0,8,7,6,5};

    printf("{ ");
    for (int i = 0; i < arrMax; i++)
    {
        printf("%d ", iArr[i]);
    }
    printf("}\n");

#if 1
    // 교수님이 알려주신 방법
    // 오름차순
    for (int i = arrMax; i > 1; i--)
    {
        for (int j = 1; j < i; j++)
        {
            if (Compare(iArr[j - 1], iArr[j]) > 0)
            {
                Swap(&iArr[j - 1], &iArr[j]);
            }

            printf("{ ");
            for (int i = 0; i < arrMax; i++)
            {
                printf("%d ", iArr[i]);
            }
            printf("}\n");
        }
    }

#else
    // 거꾸로도 될 꺼 같아서 해본 방법..
    // 내림차순
    for (int i = 0; i < arrMax; i++)
    {
        for (int j = 0; j < arrMax - i - 1; j++)
        {
            if (Compare(iArr[j], iArr[j + 1]) > 0)
            {
                Swap(&iArr[j], &iArr[j + 1]);
            }

            printf("{ ");
            for (int i = 0; i < arrMax; i++)
            {
                printf("%d ", iArr[i]);
            }
            printf("}\n");
        }
    }
#endif

    return (0);
}

int	 Compare(int lhs, int rhs)
{
    return (lhs - rhs);
}

void Swap(int* lhs, int* rhs)
{
    int _temp = *lhs;
    *lhs = *rhs;
    *rhs = _temp;
}

앞의 순차 정렬을 하고 난 다음에 바로 거품 정렬에 들어가서 그렇게 어려운 부분은 없었다.

 

구현하고 나서 시간이 좀 남아서 반대로도 되지 않을까 생각해서 추가 코드를 작성했다.

교수님이 알려주신 방법은 왼쪽<-오른쪽으로 진행하는 방법이었으니

for문을 뒤집어서 왼쪽->오른쪽으로 진행하게 해 보았다.