버블 정렬법

배열을 정렬하는 알고리즘은 아주 많은데, 그 중 가장 먼저 배우게 되는 기초적인 알고리즘이 바로 버블정렬(거품정렬)이다. 사실 이 버블정렬 방식의 원리는 무식하기

 

그지없다. 버블정렬의 원리와 소스를 설명해 보도록 하겠다.

 

arr[10]이라는 배열이 있다. 이 배열의 원소는 아래와 같다.

 

8 1 4 14 2 17 48 2 13 48

 

왼쪽부터 차례로 arr[0], arr[1], arr[2], … , arr[9] 이다. 버블정렬을 통해 이 배열을 오름차순으로 정렬하게 되면 프로그램은 연산을 시작한다.

 

우선 arr[0]과 arr[1]을 비교한다. arr[0]은 8, arr[1]은 1으로, arr[0]이 arr[1]보다 더 크다. 앞의 원소가 뒤의 원소보다 크므로 이 둘을 서로 바꾸어 준다. 그럼 다시

 

배열은 아래와 같아질 것이다.

 

1 8 4 14 2 17 48 2 13 48

 

이번에는 arr[1]과 arr[2]를 비교한다. arr[1]과 arr[2]는 각각 8과 4로, 이번에도 앞의 원소가 뒤의 원소보다 크다. 그러므로 이 둘을 서로 바꾸어 준다. 배열은 아래와

 

같은 순서를 가지게 된다.

 

4 8 14 2 17 48 2 13 48

 

이젠 규칙을 알 것 같은가 ? 이번에는 arr[2]와 arr[3]을 비교한다. 하지만 이미 arr[2]는 arr[3]보다 작으므로, 이 부분에서는 두 수를 서로 바꾸어주지 않는다.

 

1 4 8 14 2 17 48 2 13 48

 

다음은 arr[3]과 arr[4]를 비교한다. 14와 2 중 앞의 14가 더 크므로, 두 원소를 서로 바꾸어준다. 그럼 아래와 같은 순서가 된다.

 

1 4 8 2 14 17 48 2 13 48

 

이번에는 arr[4]와 arr[5]를 비교할 차례이다. 하지만 여기서 의문이 들 것이다.

 

“지금 arr[3]에 있는 2는 arr[2]의 8, arr[1]의 4보다 작으니 arr[1]로 가야하는데, 이대로 arr[4]와 arr[5]를 비교하게 되면 2를 그냥 지나쳐 버리지 않나 ? “

 

확실히 이대로 arr[9]에서 루프가 끝나면 2를 포함한 다른 많은 원소들을 완전히 배열하지 못하게 된다. 하지만 버블정렬은 그래서 버블정렬인 것이다. 루프는 1회가

 

아닌 9회를 돈다. 즉, 배열의 원소 수만큼 도는 것이다. 위에서 설명한 방식대로 arr[0]부터 arr[9]까지 모든 원소들을 한 번 루프하면 아래와 같은 결과가 된다.

 

1 4 8 2 14 17 2 13 48 48

 

그럼 여기서 또 같은 루프를 한 번 더 돈다. 다시 처음의 arr[0]과 arr[1]부터 비교하는 것이다. 루프를 한 번씩 더 돌 때마다 배열은 아래와 같이 바뀌어간다.

 

루프 1회 :: 1 4 8 2 14 17 2 13 48 48

루프 2회 :: 1 4 2 8 14 2 13 17 48 48

루프 3회 :: 1 2 4 8 2 13 14 17 48 48

루프 4회 :: 1 2 4 2 8 13 14 17 48 48

루프 5회 :: 1 2 2 4 8 13 14 17 48 48   <== 정렬 완료

루프 6회 :: 1 2 2 4 8 13 14 17 48 48

루프 9회 :: 1 2 2 4 8 13 14 17 48 48

 

이제 어째서 루프를 배열의 원소 수만큼 도는지 알 것이다. 이렇게 하지 않으면 완전히 정렬되지 않는 배열도 있기 때문이다. 그 예로 아래와 같은 배열이 있다.

 

285 112 102 100 58 41 32 13 12 9

 

이 배열을 위에서 한 것과 같이 루프 횟수에 따라 변화시켜 보면 아래와 같아진다.

 

루프 1회 :: 112 102 100 58 41 32 13 12 9 285

루프 2회 :: 102 100 58 41 32 13 12 9 112 285

루프 3회 :: 100 58 41 32 13 12 9 102 112 285

루프 4회 :: 58 41 32 13 12 9 100 102 112 285

루프 5회 :: 41 32 13 12 9 58 100 102 112 285

루프 6회 :: 32 13 12 9 41 58 100 102 112 285

루프 7회 :: 13 12 9 32 41 58 100 102 112 285

루프 8회 :: 12 9 13 32 41 58 100 102 112 285

루프 9회 :: 9 12 13 32 41 58 100 102 112 285

 

최악의 경우 위와 같이 9회째 루프에서 정렬이 완료될 수도 있기 때문에 쓸데없더라도 꼭 끝까지 루프를 실행한다. 그렇기 때문에 버블정렬은 많은 시간을 잡아먹는다.

 

중간에 이미 정렬이 다 된 것을 확인하기 위해 플래그를 넣어서 무의미한 루프를 빠져나오는 것도 좋은 방법이다. 그렇다면 이제 버블정렬을 사용하는 코드를 작성해

 

보겠다. 길이가 N인 배열 arr을 오름차순 정렬하기 위한 코드를 작성해 보자.

int i=0, j=0;        // 먼저 변수 i와 j를 선언한다.

 

for(i=0; i<N-1; i++)

for(j=0; j<N-i-1; j++)

if(arr[j]>arr[j+1])        // 만약 arr[j]가 arr[j+1]보다 큰 경우 아래 연산을 진행한다.

{

int t=arr[j];        // t라는 변수를 선언하고, arr[j]를 변수 t에 대입한다.

arr[j]=arr[j+1];        // arr[j]에 arr[j+1]을 대입한다.

arr[j+1]=t;        // arr[j+1]에 t를 대입한다. 앞서 변수 t에는 arr[j]가 대입되어 있으므로 결과적으로 arr[j+1]에 초기의 arr[j]가 오는 셈이다.

}

버블정렬은 무조건적으로 N개의 배열을 정렬하기 위해 N(N-1)/2 만큼의 연산을 진행하기 때문에, 배열의 크기가 큰 경우에는 쓰지 않는 게 바람직하다. 배열의 크기가

 

클 때 빠른 정렬을 하기 위해서는 지난번에 포스팅했던 퀵정렬을 쓰길 권장한다.

연산자

우리는 전시간까지 ‘변수’를 ‘자료형’으로 선언하고, 여기에 ‘값(상수)’을 넣어봤습니다. 이제 이렇게 넣은 값을 계산하는 방법에 대해 알아봅시다. C언어에는 다음과 같은 연산자를 사용합니다.

 구분  연산자
 대입 연산자  =
 산술 연산자  +, -, *, /, &, ++, —
 관계 연산자  <, >, <=, >=, ==, !=
 논리 연산자  &&, ||, !
 할당 연산자  +=, -=, *=, /=, %= 등…
 삼항 연산자  ?
 비트 연산자  &, |, ~, ^, <<, >>

◆ 대입 연산자
전시간에 변수에 값을 넣을때 사용했떤 ‘=’ 연산자를 ‘대입 연산자’ 라고 합니다. 이는 다음과 같이
a = 1;
이라고 했을때, 오른쪽의 ‘값’인 ‘1’을 왼쪽의 ‘a’라는 변수에 넣습니다. 이와같이 대입 연산자 ‘=’은 오른쪽을 왼쪽에 대입하는 역할을 합니다.

◆ 산술 연산자
우리가 산수에서 사용하는 연산자와 유사합니다. 두 값을 더하고 빼는 등 계산하는 역할을 합니다. 좀 더 자세히 알아보면

 연산자  기능
 +  더하기
 –  빼기
 *  곱하기
 /  나누기
 %  나머지
 ++  1을 증가시킨다.
 —  1을 감소시킨다.

 

이와 같습니다. 예를 들어보면

 

a = 5 + 2;    5와 2를 더해 a에 넣는다. a = 5 – 2;    5에서 2를 빼 a에 넣는다.

a = 5 * 2;    5와 2를 곱해 a에 넣는다.

a = 5 / 2;    5를 2로 나눈 몫을 a에 넣는다.

a = 5 % 2;   5를 2로 나눈  나머지를 a에 넣는다.

 

다음과 같습니다. 나누기 ‘/’의 경우 위의 예에서는 ‘5’를 ‘2’로 나눈 몫인 ‘2’가 a에 들어가고 나머지는 버립니다. 반대로 나머지 연산자 ‘%’의 경우에는 ‘5’를 ‘2’로 나눈 몫은 버리고, 나머지 ‘1’이 a에 들어가게 됩니다.

 

a++, a–++a, –a;

 

이런 형태를 따로 ‘증감 연산자’ 라고도 하는데, 변수에 ‘++’을 붙이게 되면 ‘1’을 증가시키고, ‘–‘를 붙이면 ‘1’을 감소 시킵니다. 이 ‘증감 연산자’가 변수 앞에 붙을때와 뒤에 붙을때의 차이점이 존재하는데, 다음을 봅시다.

 

int a = 1, b = 0;

일때

 

b = a++;    // b = 1, a = 2

b = a–;    // b = 1, a = 0

 

b = ++a;    // b = 2, a = 2

b = –a;    // b = 0, a = 0;

 

이와 같이 앞에 증감 연산자가 붙을 경우는 증감 연산자를 먼저 계산하고 그 값을 대입하는 반면, 뒤에 붙을 경우엔 대입이 먼저 되고 그 값은 마지막에 증가 혹은 감소 하는것을 알 수 있습니다. 정확히는 증감연산자가 앞에 붙을 경우 (전위형이라고 함) 먼저 증감연산자를 처리하고 그 행이 계산되고 대입되며, 뒤에 붙을 경우 (후위형이라고 함) 계산 및 대입 등이 모두 끝나고 그 행이 다음행으로 넘어가기 직전에 증감연산자가 처리됩니다. 처리속도는 앞에 붙이는 전위형이 후위형에 비해 아주 약간이지만 빠르기 때문에 둘중 어떤것을 써도 관계없는 상황에서는 전위형을 써주는게 여러모로 좋습니다.

 

 ◆ 관계 연산자

두 값의 크기를 비교하는 연산을 합니다.

 

 

예를 들어봅시다.

 

int a = 3, b = 5, c = 0;

일때

 

c = a < b;    // c = 1

c = a > b;    // c = 0

c = a == b;    // c = 0

c = a != b;    // c = 1

 

이와 같습니다. ‘<=’ 나 ‘>=’의 경우도 이해하는데 딱히 어렵지는 않을 것으로 생각됩니다. 여기서 값이 1이 되는 경우를 ‘참 (True)’ 이라 하고, 0이 되는 경우를 ‘거짓 (False)’ 이라 합니다. 이러한 관계 연산자는 위의 예와 같은 형식으로 사용되기 보다는 뒤에 나올 ‘조건문’이나 ‘반복문’에 사용되는 경우가 많습니다. 자세한건 그때 다시한번 설명하겠습니다.

 

 ◆ 논리 연산자

두 값을 해당하는 논리로 연산합니다. 공대생이라면 이해가 빠르실겁니다.

 

 연산자  논리  기능
 &&  AND  양쪽이 모두 참이면 참
 ||  OR  양쪽 중 하나이상이 참이면 참
 !  NOT  참이면 거짓, 거짓이면 참

 

예를들어

 

int a = 3, b = 1, c = 0;

일때

 

c = (a > b) && (b == 1);    // c = 1

c = (a > b) && (b < 1);    // c = 0

c = (a > b) || (b == 1);    // c = 1

c = (a > b) || (b < 1);    // c = 1

c = !(a > b);                  // c = 0

c = !(b < 0);                  // c = 1

 

이런식으로 AND 연산은 양쪽 결과가 ‘참’ 일 경우 ‘1’이고, 어느한쪽이라도 ‘거짓’이면 ‘0’이 됩니다. 반면에 OR 연산은 양쪽 중 하나라도 ‘참’이면 ‘1’이 되고, 양쪽 모두 ‘거짓’이라면 ‘0’이 됩니다. NOT 연산은 ‘거짓’ 이라면 ‘1’, ‘참’ 이라면 ‘0’ 이 됩니다. 그런데 다음 예처럼

 

c = 100 && -10;    // c = 1

c = -20 || -10;    // c = 1

c = !123;            // c = 0

 

‘1’ 도 아니고 ‘0’도 아닌 값들을 넣어봤습니다. 여기서 알 수 있는건 C언어에서는 ‘0’이 아닌 모든 값을 ‘참 (True)’으로 처리하고 있다는 겁니다. ‘1’만이 ‘참’은 아니라는것이죠. 뒤에 나올 ‘조건문’과 ‘반복문’ 등에서 자주 쓰이니 반드시 기억해둡시다.

 

 ◆ 할당 연산자

대입연산과 산술연산을 줄여서 같이 쓰는 경우입니다.

 

 

다음의 예를 봅시다.

 

int a = 10;

일때

 

a += 5;    // a = 15

a -= 5;    // a = 5

a *= 5;    // a = 50

a /= 5;    // a = 2

a %= 5;    // a = 0

 

간단하게 위의 식은 다음의 식을 줄인 것입니다.

 

a = a + 5;a = a – 5;

a = a * 5;

a = a / 5;

a = a % 5;

 

이렇게 풀어놓고 보면 값이 왜 저렇게 나오는지 쉽게 알 수 있을 겁니다. 프로그래밍을 하다 보면 모든 언어를 통털어 위와 같이 자신에 어떤 값을 계산하여 다시 자신에게 넣는 상황이 매우 빈번하게 발생합니다. 그래서 C언어에서는 할당 연산자를 만들어 사용하게 된 것입니다.

 

 ◆ 삼항 연산자

지금까지 알아본 연산자들은 ‘왼쪽’, ‘오른쪽’으로 2개의 ‘항’이 있는 ‘이항 연산자’였습니다. 이것만으로도 대부분의 계산을 할 수 있지만 3개의 항을 가지는 ‘삼항 연산자’를 사용하면 매우 간결하게 코드를 작성할 수 있습니다.

 

조건 ? 참일때의 값 : 거짓일때의 값;

 

이런 형식이며, 예를들어

 

int a = 0, b = 1, c = 0;

일때

 

c = (a > b) ?  10 : 20;    // c = 20

c = (a == 0) ? 10 : 20;    // c = 10

c = a ? a : b;                // c = 1

 

이와같이 ‘?’ 왼쪽의 조건이 ‘참’ 이면 ‘:’의 왼쪽 값을, 거짓이면 ‘:’의 오른쪽 값을 반환합니다. 나중에 나올 ‘조건문’을 쓰는 것보다 어떤 경우에는 더 간단하게 표현할 수 있기 때문에 종종 사용되곤 합니다.

 

 ◆ 비트 연산자

컴퓨터에서 모든 수는 2진수이고 한자리는 1비트입니다. 비트 연산자는 이 비트 단위로 특정한 연산을 수행합니다.

 

 연산자  기능
 &  비트단위 AND 연산
 |  비트단위 OR 연산
 ~  비트단위 NOT 연산
 ^  비트단위 XOR 연산
 <<  왼쪽으로 비트 이동
 >>  오른쪽으로 비트 이동

 

논리 연산자를 설명할때 어느정도 설명을 했었으므로 이번에는 예를 들어보겠습니다.

 

a = 1010 0101, b = 1001 1001일때

c = a & b;    // c = 1000 0001

c = a | b;    // c = 1011 1101

c = ~a;       // c = 0101 1010

c = a^b;      // c = 0011 1100

 

논리 연산자를 설명할때 ‘AND’, ‘OR’, ‘NOT’을 설명하였습니다. 이것을 비트로 옮겨 계산한 것뿐입니다. ‘XOR’의 경우는 두 값이 서로 다르면 ‘1’, 같으면 ‘0’ 이 됩니다.

 

a = 0011 1010; 일때

c = a << 1;    // c = 0111 0100

c = a << 2;    // c = 1110 1000

 

c = a >> 1;    // c = 0001 1101

c = a >> 2;    // c = 0000 1110

 

이 ‘<<‘, ‘>>’를 흔히 ‘쉬프트 연산자’ 라고도 합니다. 말뜻 그대로 비트를 오른쪽의 수만큼 이동시키는 역할을 하며, 2진수의 특성상 왼쪽으로 1비트 이동하면 2를 곱한것과 같은 값이 되고, 2비트 이동하면 2²인 4를 곱한 것과 같은 값이 됩니다. 반대로 오른쪽으로 1비트 이동하면 2로 나눈 값이 되고, 2비트 이동하면 2²인 4로 나눈 값이 됩니다. 이러한 비트 이동은 산술 연산자로 곱하고 나눈 것보다 처리속도가 빠른 장점이 있기 때문에 속도에 민감한 프로그램들이 값을 계산하는데 자주 사용합니다. 정리하면

 

int a = 12;

일때

 

c = a << 1;    // c = 24 (= a * 2)

c = a << 3;    // c = 96 (= a * 8)

 

c = a >> 1;    // c = 6 (= a / 2)

c = a >> 2;    // c = 3 (= a / 4)

 

이렇게 됨을 기억하시기 바랍니다. 또한 비트 연산자도  ‘&=’, ‘|=’, ‘^=’와 같이 할당 연산자로도 쓸 수 있씁니다.

 

 

 2. 연산자의 우선 순위

 

지금까지 알아본 연산자는 하나의 식에 모두 섞어 쓸 수 있는 것들입니다. 이것들이 복합적으로 섞여있을때는 산수에서 사용하는것처럼 기본적으로는 왼쪽에서 오른쪽으로 계산이 되고, ‘*’, ‘/’ 가 ‘+’, ‘-‘ 보다 우선순위가 높습니다. 괄호로 묶어줄 경우엔 괄호안을 먼저 계산하는것까진 동일합니다. 다만 C언어에서는 중괄호 {} 나 대괄호 []를 계산식에 사용할 수 없고 오로지 소괄호 () 만을 사용할 수가 있습니다.  원래 소괄호만 사용하면 복잡한 식에서는 햇갈리기 때문에 중괄호, 대괄호가 생겨났던건데, 컴퓨터는 햇갈릴 일이 없기도 하고, 다른 용도로 사용중이기 때문에 소괄호만 중첩하여 사용합니다.

 

c = 1 + ((1 + 2) * (3 / 1));        // 결과는 10

 

이런 식입니다. 그밖의 연산자까지 모두 정리해보면

 

단항 연산자 (++, –, ! 등…)곱하기, 나누기 (*, /)

더하기, 빼기 (+, -)

쉬프트 연산 (<<, >>)

관계 연산자 (>, <, >=, <=)

관계 연산자 (==, !=)비트 연산자 AND (&)

비트 연산자 XOR (^)

비트 연산자 OR (|)

논리 연산자 AND (&&)

논리 연산자 OR (||)

삼항 연산자 (?)

대입 및 할당 연산자 (=, +=, -=, *=, /= 등…)

 

나열해보니 많습니다만 중요한 것은 이걸 외울것까진 없다는 겁니다. 괄호만 잘 사용하고 식을 나누어 쓰면 훨씬 알아보기 쉽고 신경 쓸 일이 덜해집니다. 코드의 줄 수를 늘리더라도 알아보기 쉽게 하는 것이 중요합니다.