코딩을 하다 보면 무작위로 나온 결과 값들을 정렬을 해야할 때가 있다.
가장 대표적인 예로 로또 번호를 추출하는 프로그램을 만들 때 "20 23 18 5 34 30"과 같은 형식으로 출력할 수 있지만
위와 같이 숫자들을 오름차순(작은 수 -> 큰 수)으로 정렬해서 만들고 싶을 때는 버블 정렬을 사용하면 쉽게 구현할 수 있다!
버블 정렬이란?
버블 정렬은 정렬 알고리즘 중에서 가장 간단한 알고리즘이며 서로 인접한 값들을 비교하여 큰 값을 뒤로 넘기며 정렬하는 알고리즘이다.
아래 코드는 무작위로 값이 저장된 크기가 5인 배열이다. 어떻게 버블 정렬이 실행되는지 과정을 살펴보자.
|
int arr[5] = {5, 3, 1, 4, 2};
|
1. arr[0]의 5와 arr[1]의 3을 비교한다. arr[0]이 arr[1]보다 값이 크므로 arr[0]과 arr[1]의 자리를 바꾼다.
|
int arr[5] = {3, 5, 1, 4, 2};
|
2. arr[1]의 5와 arr[2]의 1을 비교한다. arr[1]이 arr[2]보다 값이 크므로 arr[1]과 arr[2]의 자리를 바꾼다.
|
int arr[5] = {3, 1, 5, 4, 2};
|
3. arr[2]의 5와 arr[3]의 4를 비교한다. arr[2]가 arr[3]보다 값이 크므로 arr[2]와 arr[3]의 자리를 바꾼다.
|
int arr[5] = {3, 1, 4, 5, 2};
|
4. arr[3]의 5와 arr[4]의 2를 비교한다. arr[3]이 arr[4]보다 값이 크므로 arr[3]과 arr[4]의 자리를 바꾼다.
|
int arr[5] = {3, 1, 4, 2, 5};
|
5. 마지막까지 비교를 마쳤으면 처음으로 돌아가서 같은 방법으로 정렬을 반복한다. 설명은 생략하고 정렬 순서만 써놓을테니 자신이 생각한 것과 맞는지 비교해보자.
|
int arr[5] = {1, 3, 4, 2, 5};
|
|
int arr[5] = {1, 3, 4, 2, 5};
// arr[1]의 3과 arr[2]의 4를 비교했을 때 3이 더 작으므로 변화 없음.
|
|
int arr[5] = {1, 3, 2, 4, 5};
|
|
int arr[5] = {1, 2, 3, 4, 5};
// 최종 배열의 상태
|
위 예시는 인접한 두 값을 비교할 때 앞에 놓여있는 값이 더 큰 경우가 한 번밖에 없었지만 데이터가 많을수록 이와 같이 필요 없는 비교를 많이 하기 때문에 다른 정렬에 비해 속도가 느린 편이지만 구현하기 매우 쉽다는 장점을 가지고 있다.
버블 정렬 구현 코드
다음 코드는 무작위로 저장된 10개의 값을 버블 정렬을 사용한 코드이다.
|
#include <stdio.h>
int main() {
int arr[10] = {9, 5, 3, 6, 10, 1, 8, 2, 4, 7};
int len = sizeof(arr) / sizeof(int);
int temp;
printf("Before : ");
for(int i=0; i< len; i++){
printf("%d ", arr[i]);
}
printf("\n");
for(int i = 0 ; i < len - 1 ; i++){
for(int j = 0 ; j < len - 1 ; j++){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
printf("After : ");
for(int i=0; i< len; i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
|
버블 정렬을 하기 위해서 이중 반복문을 사용하였으며 for문의 조건값을 "len-1"로 작성한 이유는 크기가 10인 배열의 마지막 인덱스는 9이다. 버블 정렬의 인접한 두 값을 비교하는 순서는 0과 1번 인덱스, 1과 2번 인덱스, 2와 3과 인덱스, ... , 7과 8번 인덱스, 8과 9번 인덱스이다.
for문이 8번까지 돌면 크기가 10인 배열의 마지막 인덱스인 9까지 비교하는 코드이므로 len이 아닌 len-1로 작성하였다.
이 글을 보고 버블 정렬에 대해서 이해했다고 생각이 들면 코드를 보지 않고 직접 타이핑하여 버블 정렬을 구현해보자.
그리고 이를 응용하여 내림차순(위 -> 아래)으로 정렬하는 코드도 작성해보며 연습해보자. 아래 코드는 내림차순 코드인데 코드를 보지 않고 작성해본 다음 확인해보자.
내림 차순 구현 코드
|
#include <stdio.h>
int main() {
int arr[5] = {5, 3, 1, 4, 2};
int temp;
int len = sizeof(arr) / sizeof(int);
for(int i=0; i< len - 1; i++){
for(int j=0; j<len - 1; j++){
if(arr[j] < arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(int i=0; i<len; i++){
printf("%d ", arr[i]);
}
return 0;
}
|
눈치 빠른 사람은 버블 정렬 코드 if문의 '>' 부등호를 '<' 부등호로 바꿔주면 된다는 것을 알았을 것이다. (눈치 못 채도 상관없다)
'언어 > C언어' 카테고리의 다른 글
| [C언어] Queue 구현하기 (0) | 2020.04.01 |
|---|---|
| [C언어] 공약수 찾는 방법 (0) | 2020.03.23 |
| [C언어] 약수 구하는 방법 (0) | 2020.03.21 |
| [C언어] 문자열 제대로 비교하는 방법 (1) | 2020.03.21 |
| [C언어] 랜덤으로 숫자를 뽑아서 평균 구하는 방법 (feat. sizeof()) (0) | 2020.03.13 |