버블정렬 이해하기

#include <iostream>

using namespace std;

 

void bubble(int *, int);

void swap(int&, int&);

int main() {     // int main() 이 표준입니다.

  int temp[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

  bubble(temp, (sizeof(temp)/sizeof(temp[0])));

  return 0;

}

void bubble(int *arr, int count) {

  int i, j;

  for(i=0;i<count;i++) {

    cout<<arr[i]<<" ";

  }

  cout<<endl;

  // 버블 정렬 시작

  for(i=1;i<count;i++) {

    for(j=0;j<count-i;j++) {

      if(arr[j]>arr[j+1]) {

        swap(arr[j], arr[j+1]);

      }

    }

  }

  for(i=0;i<count;i++) {

    cout<<arr[i]<<" ";

  }

  cout<<endl;

}

void swap(int& a, int& b) {

  int temp;

  temp = a;

  a = b;

  b = temp;

}

먼저 swap을 보겠습니다.

변수 a, b에 들어 있는 값들을 바꾸어 줍니다.

가령 

tempa=a;tempb=b; 

a=tempb; b=tempa; 

와 같이 했다면 분명히 알아 볼수 있을 것입니다.

이를

temp=a; a=b; b=temp; 라고 한 것입니다.

int& 형과 같은 참조형은 call by reference 입니다.

인자가 값으로 넘어 가는 것이 아니라 참조를 할수 있는것이 넘어 갑니다.

그렇다고 해서 c언어처럼 int *a 와 같이 포인터로 받는 것이 아닙니다.

포인터로 받았다면

temp=*a; *a=*b; *b=temp; 와 같은 방식으로 사용해야 하지만 번거러움이 있읍니다.

버블 정렬을 보겠습니다. 

정렬을 보다 분명히 이해하기 위해서 코드를 조금 고쳤습니다.

// 버블 정렬 시작 - 부터 보겠습니다.

  // 버블 정렬 시작

  for(i=1;i<count;i++) {   // count - 1 번을 돕니다. count가 2라면 1번만 돌면 됩니다.

............................. 한번만 순서를 바꾸어 준다면 정렬이 되기 때문입니다.

............................. 또 count가 3이라면 2번만 돌면 됩니다.

    for(j=0;j<count-i;j++) {  // 배열의 마지막 index가 count-1입니다.

................................ j는 count-2까지 변합니다.

................................ 밑에서 arr[j+1]이 나오기 때문에

................................ 이 경우에도 j+1은 count-1 이 되어서 한계를 넘지 않습니다.

      if(arr[j]>arr[j+1]) {   // 만약 앞의 값이 뒤의 값보다 크다면 

        swap(arr[j], arr[j+1]); // 서로 바꾸어 줍니다. 처음에는 10과 9가 바뀝니다.

................................... 그 다음에는 10과 8이 바뀝니다.

................................... 그 다음에는 10과 7이 바뀝니다.

................................... 그 다음에는 10과 6이 바뀝니다.

................................... 그 다음에는 10과 5가 바뀝니다.

................................... 그 다음에는 10과 4가 바뀝니다.

................................... 그 다음에는 10과 3이 바뀝니다.

................................... 그 다음에는 10과 2가 바뀝니다.

................................... 그 다음에는 10과 1이 바뀝니다.

      }............................ 그 결과로 배열은 9,8,7,6,5,4,3,2,1,10 이 됩니다.

................................... 안쪽의 for문을 끝내고 나면 끝위치에 가장 큰원소인 10이 오는 것을

    }.............................. 알수 있습니다.

..........................다음번에는 i의 값이 2가 됩니다.

  }.......................   .. arr[8]에 가장큰 값이 9가 오게 됩니다. (10은 쳐다보지도 않으니까 무시)

..........................이렇게 반복해서 정렬이 됩니다.