C++ 기초 : 버블 정렬

---

버블 정렬(Bubble Sort)이란,

서로 인접한 두 개의 값을 비교하여 필요 시

교환을 수행하고 이를 전체 자료에 걸쳐 반복하는 것입니다.

 

Bubble Sort 알고리즘을 통해

값을 오름차순 또는 내림차순으로 정렬할 수 있습니다.

 

 

---

 

 

 

Bubble Sort를 수행하는 함수를 만들어

가변 배열의 수를 정렬하도록 하겠습니다.

 

 

우선은 가변 배열에 랜덤한 값을 대입하도록 하죠.

 

랜덤 함수를 이용할 것인데

 

랜덤 함수를 이용하기 위해 "time.h" 파일을 포함시켜 줍니다.

 

rand 함수를 통해 랜덤한 수를 얻을 수 있긴 하지만,

그냥 사용하면 다시 실행해도 계속 같은 수가 나오게 됩니다.

 

우리가 무작위로 숫자를 종이에 적었다고 합시다.

근데 항상 그 종이만 보고 값을 나열한다면

랜덤하더라도 결국 똑같은 수만 나오게 되겠죠.

 

 

그래서 15번째 줄에서 볼 수 있듯이

srand를 통해 Seed(시드) 값을 넣어주는 겁니다.

보통 시간을 시드값으로 넣습니다. 시간은 항상 변하기 때문에

실행할 때마다 랜덤한 다른 값을 얻어낼 수 있죠.

 

 

18번째 줄에 있는 for문을 이용하여 10개의 랜덤한 값을

얻어내어 동적 할당된 배열에 하나씩 대입합니다.

 

 

20번째 줄에서 rand 함수로 값을 얻어내고 100으로 나눈 뒤

1을 더한다는 것은 1 ~ 100의 값을 얻겠다는 의미입니다.

rand 함수로 얻을 수 있는 값은 범위가 정해져 있지 않습니다.

그래서 아주 큰 수가 나올 수도 있죠. 이를 100으로 나누면

나머지는 0 ~ 99가 나오겠죠? 여기에 1을 더했기 때문에 

1 ~ 100의 값이 변수 iRand에 대입될 것입니다.

(디버깅을 통해 무작위로 나온 값을

편하게 확인하기 위해 변수에 넣어 주었습니다.)

 

만약 50 ~ 100의 값을 얻고 싶다고 한다면

50으로 나눈 뒤 50을 더해 주면 되겠죠?

 

 

21번째 줄에서 rand 함수를 통해

얻은 값을 동적 할당된 배열에 넣습니다.

 

 

---

 

 

 

이후 BubbleSort.h 파일을 만들어 BubbleSort 함수를 선언하고,

BubbleSort.cpp 파일에는 BubbleSort 함수를 정의합니다.

 

 

 BubbleSort.h에

 

BubbleSort 함수를 선언하였습니다.

 

해당 함수로 동적 할당된 배열에 접근해야 하므로

구조체로 만든 가변 배열을 위한 자료형을 인자로 받습니다.

 

이를 위해 tArr형 구조체가 선언되어 있는 Arr.h 파일을 포함해야 하죠.

 

 

BubbleSort.cpp에는 

 

BubbleSort 함수를 정의하였습니다.

 

5

먼저 예외 처리부터 하였습니다.

 

만약 해당 객체가 동적 할당하고 있는 공간에 

데이터가 없거나 1개만 있다면 굳이 정렬할 필요가 없죠.

그래서 가변 배열이 가지고 있는 데이터의 개수를 나타내는

iCount의 값이 1과 같거나 작으면, 즉 0이나 1이면

BubbleSort 함수를 빠져나갑니다.

 

 

12

먼저 12번째 줄부터 보시죠.

 

이제 for문을 통해 앞에서부터 두 개씩 수를 비교하며 

정렬을 할 것입니다. 이러한 비교를 위한 for문을 얼마나

반복해야 할까요? 만약 4개의 데이터가 있다면 3번만 비교하면

될 것입니다.(수식으로 나타내면 n - 1번 반복) 그래서 for문의

반복 횟수를 정할 변수 iLoop에는 iCount에서 -1한 값을 대입합니다.

가변 배열에 들어있는 데이터의 개수에서 하나를 뺀 만큼

반복하도록 하는 것이죠.

 

 

16 ~ 27

동적 할당된 가변 배열에 접근하여

데이터 두 개씩 비교를 시작합니다.

 

만약 오른쪽에 있는 수보다 왼쪽에 있는 수가 더 크면

if문으로 들어가겠죠. 그리고 오른쪽에 있는 값을 왼쪽에,

왼쪽에 있는 값을 오른쪽에 넣습니다. 여기서 변수 temp에

왼쪽에 있는 값을 미리 대입한 뒤, 오른쪽에 대입할 때

이 값을 대입하는 이유는 값이 동시에 교환되지 않기 때문입니다.

 

만약 오른쪽에 있는 3을 왼쪽에 넣는다고 하였을 때,

3을 왼쪽에 넣는 순간, 왼쪽에 있는 값이 3이 됩니다.

이를 다시 오른쪽에 넣게 되므로 둘 다 3이 되어 버리죠.

 

이를 방지하고자 왼쪽 값을 다른 변수에 값을 저장하고

이 값을 오른쪽에 대입하는 것이죠.

 

 

근데 이 과정을 모두 거쳤다고 해서 완벽하게 정렬이 될까요?

현시점에서, 위의 for문을 통해 가장 큰 수가 가장 오른쪽에

배치된 것은 맞지만 그 외의 값들은 정렬되어 있지 않을 겁니다.

 

그래서 완벽하게 정렬이 될 때까지 

14 ~ 28번째 줄에 있는 for문을 다시 반복해 주어야 합니다.

 

이러한 이유로 while문으로 for문을 감싸 주는 것이죠.

 

 

8 ~ 32

일단 while문이 계속 반복하도록 설정하고

탈출 조건을 만들어 탈출할 수 있도록 하겠습니다.

 

어떻게 해야 정렬이 다 되었다고 인식하고 while문을

빠져나갈까요? 잘 생각해 보면 17번째 줄에 있는 if문이

동작한다는 것은 왼쪽에 있는 값이 오른쪽에 있는 값보다

컸다는 의미죠. 반대로 이 if문이 동작하지 않았다는 것은

왼쪽에 있는 값과 오른쪽에 있는 값이 같거나 오른쪽에 있는

값이 더 커서 정렬할 필요가 없었다는 의미겠죠?

 

그래서 10번째 줄에서 bool형 변수 bFinish를 선언하여 

일단 true를 대입하고 if문이 동작하는 순간 false를 대입합니다.

 

그리고 30번째 줄에서 while문을 탈출하는 조건으로

bFinish의 값이 true라면 break를 통해 탈출하도록 했습니다.

정렬이 필요하여 if문에 들어가면 bFinish의 값이 false가 되므로

탈출하지 않고 다시 while문을 반복합니다. 이때 다시 bFinish의 값이

true가 됩니다. 정렬이 필요하여 if문에 다시 들어간다면 bFinish의 값이

false가 되므로 다시 while문을 반복할 것이고, 정렬이 필요하지 않아

if문에 들어가지 않는다면 bFinish의 값이 그대로 true이므로

while문을 탈출하며 정렬이 종료될 것입니다.

 

 

---

 

 

위에서 만든 BubbleSort 함수를 이용하여 

객체 s가 가리키고 있는 가변 배열의 데이터를

오름차순으로 정렬하였습니다.

 

 

버블 정렬 전 가변 배열에 있는 값들을 출력하고

 

버블 정렬 후에 가변 배열에 있는

값들을 출력하여 비교할 수 있도록 하였는데,

오름차순으로 정렬이 잘 진행된 것을 확인할 수 있습니다.

 

 

 

 

강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB

---