[c++] 버블정렬

버블 정렬이랑 옆에 있는 값과 비교해서 위치를 바꿔주는 정렬 방법이다.

 

선택 정렬은 제일 작은 값을 찾아서 앞에 가져다 놓는 식으로 전개된다면,

(선택 정렬 설명 링크: c++ 선택 정렬 활용해서 배열 속 숫자들을 오름차순으로 바꾸기 (tistory.com))

 

버블 정렬은 제일 큰 값을 점차 뒤로 유배보내는 식으로 전개된다.

왜냐하면 첫 배열값부터 일관되게 바로 옆(뒤)에 있는 배열값과 비교해서 큰 값은 뒤로 물러나도록 스위치를 반복하기 때문이다. 

 

 

2 6 4 9 8 1 3 5 7 라는 9개의 숫자를 한 배열에 담고 버블 정렬을 활용해 오름차순으로 바꾸는 시뮬레이션을 해보자.

제일 앞 숫자를 0번째 인덱스, 마지막 숫자를 8번째 인덱스라 가정한다.

2 6 4 9 8 1 3 5 7     //2와 6을 비교한다. (2가 더 작음, 그대로)

2 6 4 9 8 1 3 5 7     //6과 4를 비교한다. 

2 4 6 9 8 1 3 5 7     //4가 6보다 작으므로 위치를 바꾼다.

2 4 6 9 8 1 3 5 7     //6과 9를 비교한다. (6이 더 작음, 그대로) : 여기부터 9는 매번 비교대상이 된다. 제일 크기 때문에

2 4 6 9 8 1 3 5 7     //9와 8을 비교한다. 

2 4 6 8 9 1 3 5 7     //8이 9보다 작으므로 위치를 바꾼다.

2 4 6 8 9 1 3 5 7     //9와 1를 비교한다.

2 4 6 8 1 9 3 5 7     //1이 9보다 작으므로 위치를 바꾼다.

2 4 6 8 1 9 3 5 7     //3과 9를 비교한다.

2 4 6 8 1 3 9 5 7     //3이 9보다 작으므로 위치를 바꾼다.

2 4 6 8 1 3 9 5 7     //9와 5를 비교한다.

2 4 6 8 1 3 5 9 7    //5가 8보다 작으므로 위치를 바꾼다.

2 4 6 8 1 3 5 9 7    //9와 7을 비교한다.

2 4 6 8 1 3 5 7 9    //7이 더 작으므로 위치를 바꾼다. 비로소 가장 큰 값인 9가 제일 뒤로<i=0일때, for문(8-i)마무리>

이중 포문 i와 j 포지션은 아래와 같다.

for (int i = 0; i < 8; i++) //앞과 뒤를 비교하는 식이다보니 i를 숫자갯수-1만큼만 돌리면 된다. <8로 해도 충분
{                                    
     for (int j = 0; j < 8 - i; j++) //숫자 9개면 8번만 비교, 마지막 숫자가 2개남으면 1번만 비교하면 OK이므로
     {    

     }

}

---

 

............이어서 8번째 인덱스(9)를 제외하고 7번 비교를 실행해주면 된다..........................<i=1 for문(8-i) 마무리>

결과는

2 4 6 1 3 5 7 8 9 가 될 것이다.

 

............이제 7,8번째 인덱스 제외(8,9)하고 6번 비교를 실행해주면 된다....................<i=2 for문(8-i) 마무리>

결과는

2 4 6 1 3 5 7 8 9 가 될 것이다. 

 

..............이제 6,7,8번째 인덱스를 제외(7,8,9)하고 5번 비교 실행해주면 된다................<i=3 for문(8-i) 마무리>

결과는

2 4 1 3 5 6 7 8 9 가 될 것이다. 

 

 ............이제 5,6,7,8번째 인덱스(6,7,8,9) 제외하고 4번 비교를 실행해주면 된다..............<i=4 for문(8-i) 마무리>

결과는

2 4 1 3 5 6 7 8 9 가 될 것이다. 

 

.............이제 4,5,6,7,8번째 인덱스(5,6,7,8,9) 제외하고 3번 비교를 실행해주면 된다............<i=5 for문(8-i) 마무리>

결과는

2 1 3 4 5 6 7 8 9 가 될 것이다. 

 

..............이제 3,4,5,6,7,8번째 인덱스(4,5,6,7,8,9) 제외하고 2번 비교 실행해주면 된다........<i=6 for문(8-i) 마무리>

결과는

2 1 3 4 5 6 7 8 9 가 될 것이다. 

 

.............이제 2,3,4,5,6,7,8번째 인덱스(3,4,5,6,7,8,9) 제외하고 1번 비교 실행해주면 된다......<i=7 for문(8-i) 마무리>

결과는

1 2 3 4 5 6 7 8 9 가 될 것이다.<끝><더이상 비교할 필요 없다.><i가 0에서 7이 될 때까지... 여덟번째 for문 마무리>

 

핵심: N개의 숫자가 있을 때, 양옆을 비교하는 횟수는 N-1회면 충분하다.

N개 배열에서 버블 정렬을 하려면 

두번째 for문(j)에서 비교연산을 (N-1)번 부터 1번까지 할 수 있도록(갈수록 연산횟수가 줄어들게끔 j-i )

첫번째 for문(i)을 적어도 (N-1)번이 될 때까지 반복시켜야 한다.

N이 3일 경우,

int main()
{
int temp = INT_MAX;
array<int, 3>arr = { 349,568,7};
for (int i = 0; i <2; i++) 
{                                       
for (int j = 0; j < 2 - i; j++)
{
if (arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return 0;
}

버블정렬은 위와 같이 int index나 int min을 초기화 선언하지 않아도

이중 for문과 temp 설정만 잘해주어도 구현 가능하다.

아래는 유튜브를 참고하여 작성한 코드이다.

아래 예시는 배열이 10개이다.

 

#include <iostream>
#include <array>
using namespace std;

int main()
{
     int temp = INT_MAX;
     array<int, 10>arr = { 9,8,7,6,5,4,3,2,1,10 };
     for (int i = 0; i < 9; i++)
     {                                    
     for (int j = 0; j < 9 - i; j++) //배열은 10칸이지만 [j]와 [j+1]번째 배열을 비교하므로 처음에 9번만 비교해도 됨
     {                                     //즉 j 도는 횟수(앞뒤비교)를 9번, 8번, 7번 ~~~ 1번까지만 하려면 i는 8까지만 OK.
          if (arr[j] > arr[j + 1])
         {
               temp = arr[j];
              arr[j] = arr[j + 1];
              arr[j + 1] = temp;
         }
     }
}

for (auto ele : arr)
{
cout << ele << " ";
}
return 0;
}

---

정렬 알고리즘 중에서 구현하기는 가장 쉽지만 가장 비효율적인 알고리즘이다.

선택 정렬과 비교해보자면 시간 복잡도로만 따지자면 n의 제곱으로 똑같을 수 있지만

선택 정렬은 min값이 들어있는 인덱스를 기억해놓았다가

안쪽 for문 밖에서 기억해놓은 인덱스만 앞쪽 인덱스와 temp 교환처리 해주면 되지만

버블 정렬은 안쪽 for문 안에서 양옆으로 매번 temp 교환을 하기 때문에 실제 시간 소요량은 더 길다고 할 수 있다.