버블 정렬

정렬은 여러개의 데이터 값을 오름차순이나 내림차순으로 크기에 다라 순서화 시키는 것을 말한다.

이러한 정렬을 위한 여러 가지 알고리즘이 개발되어 있는데, 그중에서 가장 간단하고 이해하기 쉬운 것중 하나가 버블 정렬(bubble sort)이다.

버블정렬은 효율적인 정렬이 아니다.

예를들어 1,2,3,4,5를 내림차순으로 정렬해 보면

첫 번째 반복

→ (1, 2)를 비교하여 1이 작으므로 위치를 바꾼다. (2, 1, 3, 4, 5)

→ (1, 3)를 비교하여 1이 작으므로 위치를 바꾼다. (2, 3, 1, 4, 5)

→ (1, 4)를 비교하여 1이 작으므로 위치를 바꾼다. (2, 3, 4, 1, 5)

→ (1, 5)를 비교하여 1이 작으므로 위치를 바꾼다. (2, 3, 4, 5, 1)

→ (n -1)번의 비교, 즉 4번의 비교로 가장 작은수가 제일 뒤로 갔다.

두 번째 반복

(2, 3)을 비교하여 2가 작으므로 위치를 바꾼다. (3, 2, 4, 5, 1)

(2, 4)을 비교하여 2가 작으므로 위치를 바꾼다. (3, 4, 2, 5, 1)

(2, 5)을 비교하여 2가 작으므로 위치를 바꾼다. (3, 4, 5, 2, 1)

(n -1)번의 비교, 즉 3번의 비교로 가장 작은수가 제일 뒤로 갔다.

세 번째 반복

(3, 4)을 비교하여 3이 작으므로 위치를 바꾼다. (4, 5, 3, 2, 1)

(n -1)번의 비교, 즉 2번의 비교로 가장 작은수가 제일 뒤로 갔다.

네 번째 반복

(4, 5)을 비교하여 4이 작으므로 위치를 바꾼다. (5, 4, 3, 2, 1)

다음의 버블 정렬 프로그램을 보자

#include <stdio.h>

void bubble_sort( int array[], int count)
void swap( int *px, int *py);
void printvector( int v[], int n);


int main()
{
    int vector[5] = {5,4,3,2,1,};
    bubble_sort(vector,5);
    return 0;
}

void bubble_sort ( int array[], int count)
{
   int i;
   int j;
   
   for( i = 0; i < count-1; i ++)
   {
       for( j = 0; j < count-1-i ; ++ j)
        {
           swap(&array[j], &array[j+1];
           printvector ( array, 5);
       }
       ptinf("\n");
   }
}


void swap( int *px, int *py)
{
   int temp;
   temp = *px;
   *px = *py;
   *py = temp;
}

void printvector ( int v[], int n)
{
   int i;
   for ( i = 0; i  <n; i++)
   {
       prntf("%5d",v[i]);
   }
   printf("\n");
}

⇒ void bubble_sort(int array[], int count)

→ 여기서 첫 번째 인수 int array[]는 int *array로 명시할 수 있다. 인수가 배열일 때 내부적으로 int *array로 처리되기 때문에 배열식으로 표현할 경우에도 색인을 명시할 필요가 없다.

⇒ 각 함수의 인자로 되어있는 배열들의 주소 확인

→ 각 주소를 보면 vector[0], array[0], V[0]는 같다. 여기서 세 번째의 &array를 보면 주소가 다르며 주소값이 작은 것을 볼 수 있다. 이것으로 보아 &array는 array의 주소 값과 다른 것을 알 수 있으며 즉, 배열이 아니라는 것이다.

→ 실질적으로 함수의 인자로 들어가는 것은 배열이 아니라 주소이며 인자는 주소를 받는 변수이다.(포인터)