#001_자료구조와 알고리즘_프리뷰 + 정렬(버블 정렬, 선택 정렬)

안녕하세요 삽잡이입니다.

이번 시간부터는 자료구조와 알고리즘에 대해여 정리를 해보려고 합니다...

엄청난 삽질을 하는 스스로의 모습이 벌써부터 떠오릅니다...

하지만... 의미 없는 삽질은 없다! 오늘도 달려갑니다~!

우선 자료구조란, '자료를 보관하는 구조'를 나타낸 것입니다.

예를 들어 앞으로 배우게 될 것이지만 간략하게 소개를 통해 이해를 해보자면...

선형... 한줄로 자료가 보관 되어있는 구조라던지,

비선형... 나무 줄기 처럼 쭉쭉 나가는 모양새던지 원탁의 형태이던지...

아무튼 그와 같이 자료가 보관되어있는 모습을 자료구조라고 할 수 있습니다.

자료들이 보관되어 있는 구조이니까요!

그렇다면 알고리즘은 뭘까요?

인터넷에서 쉽게 검색하면 알 수 있듯이

'문제 해결을 위한 논리의 전개 집합'을 우리는 알고리즘이라고 정의할 수 있습니다.

잠시 알고리즘에 대한 핵심을 말씀드리자면,

알고리즘을 구현하기 위해서는, 문제 해결을 위해 필요한 인자에 대한 명확한 정의와

이 알고리즘을 통해 나올 명확한 결과를 사전에 정해둬야 합니다.

그런 다음에 문제 해결을 위한 Loop 문이 수행될때 Loop를 수행하는 횟수와 상관 없이

해당 Loop문의 변하는 성질(변성)과 변하지 않는 성질(불변성)를 가지고

결함이 없는지 해당 알고리즘을 증명하게 되는 것이지요...

너무 당연한 말을 어렵게 쓴 것일까요?

아무튼 맞지 않습니까 ㅎㅎ 문제 해결을 위한 논리의 전개 집합이라면,

문제 해결을 위해 필요한 인자들과 그 결과에 대한 예상을 하고 

알고리즘을 작성해야하는 것이 당연할터이니 말입니다...

아무튼...

프로그램 코드를 구현하다보면,

데이터를 어떻게 보관할 것인지... 문제를 어떻게 해결할 것인지에 대해 고민할 필요가 생깁니다...

이때 자료구조와 알고리즘이 필요하게 되는 것이지요!

자료구조와 알고리즘은 이미 수많은 검증을 통해 전해온(?) 기술들이죠...

음... 미리 제공되 있는 기술들이란 말입니다 하하...

아무튼, 우리는 무엇인가 창조하는 것이 아닌, 기존에 있는 기술들을 사용하는 것이기 때문에

눈이 아닌, 몸으로 익히는 소중한 시간을 가져봅시다~!

이번 시간은 간단하게 맛보기로

버블 정렬과 선택 정렬에 대한 코드 예시를 소개한 뒤 마치도록 하겠습니다.

우선 위의 두 정렬에 대해 소개하기 전에 배열에 대해 잠깐 정리하도록 하겠습니다.

배열이란 같은 종류의 데이터를 연속적인 메모리에 보관하는 자료구조입니다.

우리는 C/C++ 시간에 인덱스([]) 연산자를 사용하여 접근을 하였죠...

이 또한 연속되는 메모리에 접근하는 의미는 같았습니다.

C/C++ 시간에 배운 배열은 자료구조의 관점에서 일부일 뿐이죠...

음... 제가 어떤 말씀을 드리는 것이냐면,

C/C++ 시간에는 int arr[10]; 이라는 것은 

'int형 메모리공간을 연속적으로 10개 잡혀있는 arr이라는 이름의 시작주소' 라고 정의할 수 있습니다.

마찬가지로 해당 정의를 아래와 같은 코드로도 나타낼수 있습니다.

int *base = (int*)malloc(sizeof(int)*10);

즉, C/C++에서는 전자의 경우에 배열이라고 생각하지만,

자료구조 관점에서는 후자의 경우를 포함하여 둘 다 배열로 취급한다는 것입니다.

왜냐, 의미는 같으니까요~!

음... 프로그램에서 말하는 배열은 C/C++ 에서 말하는 배열을 포함한 더욱 포괄적인 개념입니다.

앞으로는 우리 조금은 더 성장했다는 의미로,

배열이란 뭐냐고 한다면 C/C++ 시간에 배운 대로 생각할 것이 아니라

연속적인 메모리에 같은 종류의 데이터를 관리하는 의미의 모든 것들을

배열이라고 생각해봅시다~!

음... 헛소리가 길어졌습니다...

빨리 버블 정렬과 선택 정렬만 살펴보고 끝내도록 하지요...

참고로 버블 정렬은, 탄산 음료를 흔들어서 거품들이 막 생기지만

시간이 흐르며 거품이 사라지는 현상과 비슷하여 그런 이름을 지었다고 하네요...

믿거나 말거나...

두 정렬을 위하여 이미 인터넷 상에서는 많은 알고리즘들이 떠돌아 다니고 있습니다.

다른 떠돌아 다니는 버블 정렬, 선택 정렬은

범위를 넓혀 가면서 정렬을 시행하고 있습니다.

하지만 제가 소개해드릴 정렬 방법은

범위를 순차적으로 좁혀가며 정렬을 진행하는 코드임을 참고 하시길 바랍니다.

우선 헤더입니다.

//header
#pragma once
 
template <typename Element, typename Compare>
void selection_sort(Element *base, int n,Compare compare)
{    
    for(int i = n; i>1; i--)
    {
        int max_index = 0;
        for(int j=1; j<i; j++)
        {
            if(compare(base[max_index],base[j])<0)
            {
                max_index = j;
            }
        }
        Element temp = base[i-1];
        base[i-1] = base[max_index];
        base[max_index] = temp;
    }
}
 
template <typename Element, typename Compare>
void bubble_sort(Element *base, int n,Compare compare)
{
    for(int i = n; i>1; i--) //정렬할 범위를 좁혀나간다.
    {
        for(int j = 1; j<i; j++)
        {
            if(compare(base[j-1], base[j]) >0)
            {
                Element temp = base[j-1];
                base[j-1] = base[j];
                base[j] = temp;
            }
        }
    }
}

다음으로 소스파일입니다...

//소스파일
int CompareInt(int a, int b)
{
    return a - b;
}
void TestBubbleSort()
{
    int *arr = new int[MAX];
    for (int i = 0; i<MAX; i++)
    {
        arr[i] = rand() % 1000;
    }
 
    bubble_sort(arr, MAX, CompareInt);
 
    for(int i = 0; i<MAX; i++)
    {
        cout<<arr[i]<<" ";
        if((i+1)%10==0)
        {
            cout<<endl;
        }
    }
    cout<<"------------"<<endl;
}
void TestSelectionSort()
{
    int *arr = new int[MAX];
    for (int i = 0; i<MAX; i++)
    {
        arr[i] = rand() % 1000;
    }
 
    selection_sort(arr, MAX, CompareInt);
 
    for(int i = 0; i<MAX; i++)
    {
        cout<<arr[i]<<" ";
        if((i+1)%10==0)
        {
            cout<<endl;
        }
    }
    cout<<"------------"<<endl;
}
 
void main()
{
    TestBubbleSort();
    TestSelectionSort();
}

지금까지 삽잡이였습니다~!