알고리즘 - Bubble Sort (버블 소트)를 코딩해보자! (1)

 

 

알고리즘의 첫시작으로 하기에 좋은 정렬방법인 Bubble Sort.

지난번 포스팅에선 이 알고리즘의 개념에 대해서 포스팅을 했었다.

 

https://shineild-security.tistory.com/17

알고리즘 - Bubble Sort 개념 (버블 솔트)

 

 

오늘은 배운 개념을 토대로 코딩을 해보려고 한다.

 

주의:  예시를 보고 작성한 것이 아니라 순전히 필자의 생각대로 코딩을 한 것이기 때문에 절대 효율적인 코드가 아닐 것이다.

추후의 모범적인 효율적 코드는 나중에 나만의 코드를 완성하고 나서 찾아보고 포스팅 하도록 할 것입니다.

 

 

<순전히 필자의 의식의 흐름을 그저 정리해 둔 글이므로 심심풀이 땅콩으로 읽어주시면 감사한 대목입니다.>

 

우선 전의 배운 개념들을 기억해 보며 알고리즘을 구성하는데 필요한 요소들에 대해서 생각해 보도록 하자.

 

크게보면 두가지를 우선 생각 할 수 있다.

 

1. 여러개의 데이터

2. 저울

 

 

그리고 여기서 이제 가지를 쳐나가보도록 하자.

 

1. 여러개의 데이터

일단 단순히 인트형 배열을 사용해도 괜찮을 수도 있다.

굳이 구조체를 구성하고 데이터와 주소값을 저장하여 연결형 구성을 해야할지 고민이 된다.

그러므로 일단은 인트형 배열로 데이터 구조를 구성해서 진행하기로 결정했다.

하지만 데이터를 입력받을 때 데이터의 개수는 정해져있지 않고 그때마다 달라져야 한다.

그럼으로 동적할당을 통해서 배열을 받아야 할 것이다.

 

2. 저울

 저울을 구성함에 있어서 필요한 요소들은 무엇이 있을까
나는 이 고민을 하면서 1번에서의 나의 오류를 발견하고 말았다.

저울은 일종의 top처럼 데이터의 주소값을 가리켜야 할 것이다.

그렇게 하기위해서 데이터를 단순한 인트형 배열로 만들고 진행해도 가능은 하지만 꽤나 복잡해질 것 같다는 생각이 들었다.

그래서 다시 나는 1번의 논제로 돌아와서 1번의 계획을 수정 할 수 밖에 없었다.

 

-------------------------------

 

 

1. 여러개의 데이터

저울을 통해서 주소를 가리키고 유기적으로 변경하기 위해선 데이터의 값들을 선형 구조로 만들 필요를 느꼈다.

데이터의 구조는 이렇게 될 것이다.

(1) 자신의 왼쪽 값을 갖은 구조체의 주소값

(2) 데이터 값

(3) 자신의 오른쪽 값을 갖은 구조체의 주소값

 

그리고 입력받아야할 값은 2개,

데이터의 개수와 개수에 맞는 데이터들이다.

 

 

2. 저울

다시 저울을 생각해보자.

일단은 두개의 데이터 값을 가리키고 있어야 할 것이다.

그리고 데이터의 위치를 서로 바꾸어야 할 때 바꿀 데이터를 임시로 저장할 공간 2개가 필요하다.

또한 이 알고리즘은 while문을 이용하기 보다는 한바퀴 돌 때마다 가장 작은 값은 무조건 정렬이 이루어 진다는 특징을 이용하여 볼 때 for문을 사용하여 최대 데이터의 갯수만큼만 동작하도록 작성하고 한바퀴를 돌 때마다 저울의 이동범위를 좁혀 가도록 코딩하면 효율적일 것이다.

그리고 한바퀴 돌때 바뀐 값이 없다면 그것은 정렬이 완료된 것으로 봐도 됨으로 카운트를 이용하여 브레이크를 걸어 탈출문을 작성하면 될 것이다.

 

 

 

코딩은 C로 진행하였다.

이유는 간단하다.

포인터를 사용할 수 있고 바로바로 디버깅을 통해서 분석하기 쉽기 때문이다.

 

그럼 구상해본 내용을 토대로 작성을 해보고 오겠습니다.

 

------------------------------------------------------------------------------

 

.

.

.

 

#include <stdio.h>
#include <stdlib.h>
typedef struct bubble{
    struct bubble * front;
    int data;
    struct bubble * rear;
}b;
/*
typedef struct scale{
    struct bubble * left;
    struct bubble * right;
    int cnt;
}s;

typedef struct tmp{
    struct bubble * big;
    struct bubble * small;
}t;
*/
void input_bubble(b ** sort, int num);
void input(b ** head);
//b search(b ** sort);
void print_bubble(b ** sort);
b * getNode(void);

int main(int argc, const char * argv[]) {
    b * sort = getNode();
    input(&sort);
    //* sort = search(&sort);
    print_bubble(&sort);
    return 0;
}

b * getNode(){
    b * tmp = (b *)malloc(sizeof(b));
    tmp->front = NULL;
    tmp->rear = NULL;
    return tmp;
}

void input(b ** head){
    int num;
    printf("데이터 개수 입력 : ");
    scanf("%d", &num);
    input_bubble(head, num);
}

void input_bubble(b ** sort, int num){
    int data;
    printf("데이터 입력 : ");
    scanf("%d", &data);
    (*sort)->data = data;
    if (num == 1){
        return;
    }
    b * next = getNode();
    (*sort)->rear = next;
    next->front = * sort;
    input_bubble(&next, num-1);
}

/*
b search(b ** sort){
    if ((*sort)->front == NULL){
        return ** sort;
    }
    else{
        search(&(*sort)->front);
    }
    return ** sort;
}
*/

void print_bubble(b ** sort){
    printf("값 : %d\n",(*sort)->data);
    if ( (*sort)->rear == NULL ){
        return;
    }
    else{
        print_bubble(&(*sort)->rear);
    }
}

 

우선 데이터 입력을 받고 데이터들을 정렬하고 프린트 할 수 있도록 뼈대를 짜보았다.

짜면서도 많이 고민하고 오류와 싸우며 진행하였다.

중간중간 주석처리가 많은데 기능추가를 위한 구조체와 함수들은 일단은 주석처리를 하였다.

 

한가지 애먹었던 부분은 동적할당인데 크기가 정해져있으니 동적할당이 필요없다고 생각한 나의 안일함 덕분에 약 2시간을 에러와 삽질하였었다.

print_bubble함수 실행과정에서 sort의 값들이 일부 날라가버리는 현상이 있었는데 곰곰히 생각해보니 stack 영역에 저장이 이루어져서 데이터 입력 당시에는 디버그로 확인해도 정상적으로 들어갔으나 print_bubble을 호출하면서 스택이 정리되며 데이터가 날라간 것으로 보인다.

그래서 첫번째 sort값은 정상적으로 입력되어 있지만 print_bubble을 재귀함수로 들어가면 나머지 값들은 이미 stack영역이 한번 정리되서 쓰레기 값으로 채워져 있어서 오류가 뜨는 것이라고 추측이 되었다.

그래서 malloc함수를 이용하여 heap영역에 저장되도록 동적할당을 해주어서 진행하니까 놀랍게도 성공이였다.

(이러한 알고리즘을 구성하는 연습을 할 때는 malloc등의 함수를 애용해야겠다.)

 

괜히 예전에 자료구조 공부할 때 말록함수를 쓴게 아니였던 것이다.

그때 짤때 써놓고 기억못하는 필자는 금붕어가 틀림이 없다.

 

이상태로 실행하게되면 대충 이런 결과값이 나온다.

 

데이터 개수 입력 : 3

데이터 입력 : 1

데이터 입력 : 2

데이터 입력 : 3

1

2

3

 

그럼 이제 bubble sort 기능을 구현하면 완성이다.

저울을 구현하여서 정렬을 할 수 있도록 나머지 함수들을 완성하였다.

 

#include <stdio.h>
#include <stdlib.h>

typedef struct bubble{
    struct bubble * front;
    int data;
    struct bubble * rear;
}b;

typedef struct scale{
    struct bubble * left;
    struct bubble * right;
    int cnt;
}s;

typedef struct tmp{
    int big;
    int small;
}t;

b * getNode(void);
b * r_search(b ** sort);
s * bubbleSort(s **point);

void input_bubble(b ** sort, int num);
void print_bubble(b ** sort);
void set_Scale(s ** point, b ** right, b ** left, int num);

int main(int argc, const char * argv[]) {
    b * sort = getNode();
    s * point = (s *)malloc(sizeof(s));
    point->cnt = 0;
    int num;
    printf("데이터 개수 입력 : ");
    scanf("%d", &num);
    input_bubble(&sort, num);
    b * r = r_search(&sort);
    b * l = r->front;
    point->right = r;
    point->left = l;
    set_Scale(&point, &r, &l, num);
    print_bubble(&sort);
    return 0;
}

b * getNode(){
    b * tmp = (b *)malloc(sizeof(b));
    tmp->front = NULL;
    tmp->rear = NULL;
    return tmp;
}

b * r_search(b ** sort){
    if ((*sort)->rear == NULL){
        return * sort;
    }
    return r_search(&(*sort)->rear);
}

s * bubbleSort(s ** point){
    t tmp;
    if ((*point)->left->data > (*point)->right->data){
        tmp.big = (*point)->left->data;
        tmp.small = (*point)->right->data;
        (*point)->left->data = tmp.small;
        (*point)->right->data = tmp.big;
        (*point)->cnt++;
    }
    (*point)->right = (*point)->left;
    (*point)->left = (*point)->left->front;
    return *point;
}

void input_bubble(b ** sort, int num){
    int data;
    printf("데이터 입력 : ");
    scanf("%d", &data);
    (*sort)->data = data;
    if (num == 1){
        return;
    }
    b * next = getNode();
    (*sort)->rear = next;
    next->front = * sort;
    input_bubble(&next, num-1);
}

void print_bubble(b ** sort){
    printf("값 : %d\n",(*sort)->data);
    if ( (*sort)->rear == NULL ){
        return;
    }
    else{
        print_bubble(&(*sort)->rear);
    }
}

void set_Scale(s ** point, b ** right, b ** left, int num){
    for (int i = 0; i <= (num-2); i++){
        *point = bubbleSort(&(*point));
            }
    if ((*point)->cnt == 0) {
        return ;
    }
    (*point)->cnt = 0;
    (*point)->right = *right;
    (*point)->left = *left;
    set_Scale(point, right, left, (num-1));
}

 

 

실행 결과 값

 

 

 

저울을 추가하고 bubble sort를 실제로 구현하도록 하면서 많은 수정이 이루어 졌다.

search는 오른쪽 끝에로 이동하도록 만들어야 한다는 것을 깨닫고 수정하였으며 데이터를 한번 입력시 수정 및 삭제, 선택 조회의 기능을 구현하지 않았음으로 프린트 편리성을 위한 왼쪽 정렬을 위한 search함수는 삭제하였다.

 

그리고 사전에 계획했던대로 정렬을 진행함에 있어서 미리 데이터의 개수를 파악하여 for문을 작성하였고 그 이유는 서두에도 말했었지만

if문을 걸어서 (*sort)->front == NULL일때 멈추고 재귀함수로 들어가는 방식을 사용하게 되면 이미 한번 정리됨으로 고정된 최소값 데이터까지 조회를 더 하게되는 번거로움이 생기기 때문에 for문을 사용한 것이다.

그럼으로 데이터의 개수가 5개면 처음엔 5번 실행되고 그다음엔 재귀함수로 값을 줄여 4번, 3번, ... 총 5번의 실행이 진행되게 되며 중간에 정렬이 완료되면 point의 cnt가 0이므로 그 때는 for문을 탈출 할 수 있도록 만들어 놓았다.

나름 효율적인 방식이라고 생각하고 만들었는데 이 코드는 절대 타인의 코드를 미리 보고 짠 것이 아닌 필자의 창작물로 당연히 어느정도 비효율적이고 쓸데없이 긴 코딩이 많고 군더더기가 많을 수 있다.

그래도 남의 것을 처음부터 보고 배끼는 것보다는 내가 스스로 알고리즘의 원리를 파악하고 생각하여 직접 만드는 것이 먼저라고 판단되어서 이렇게 진행하게 되었다.

 

 

극초반에 말했듯이 이 포스팅은 거의 일기와 다름없을 정도로 의식의 흐름을 그대로 나타내준 포스팅으로 시간적으로 비효율적인 공부방법일 수 있으나 예전부터 답지보는 걸 싫어했던 나에겐 딱 맞는 삽질 공부법인듯 하다.

 

확실히 C언어로 짜니까 오류가 났을때 어느부분이 오류가 났는지 디버깅으로 확인이 용이하며 주소값 확인이 편하여서 좋은 것 같다.

 

하얗게 불태웠다....