1년되기 직전에 돌아온 블로그 작성
계절학기에 들어가면서 2주차로 C언어 프로그래밍 응용을 시작했다.
수업 마지막 중 과제에서 배열에서 입력을 받아 내림차순으로 정렬하는 것이었는데 문제를 보자마자 버블정렬을 사용하려고 했는데 구조를 까먹어서 이렇게 블로그에 옮긴다.
버블정렬? - Bubble Sort
정렬 알고리즘 중 하나이며, 시간 복잡도가 느리지만 코드가 단순하여 간단한 정렬에는 이 버블정렬을 사용하곤 한다.
버블이라는 이름이 붙는 이유는 원소의 이동이 거품이 수면위로 올라가는 듯한 모습을 가졌다고 지어졌다.
알고리즘
기본적으로 배열의 두 수를(x, y)를 선택한 후 비교하여, 만약 그 수가 정렬이 되었다면 놔두고 그게 아니라면 두 수를 교환하는 방식으로 진행된다. 오름차순일 때는 (x < y), 내림차순일 때는 (x > y) 으로 진행해야 정렬이 된 것으로 판단한다. 이를 배열의 처음부터 끝까지 반복한다.
코드
#incldue <stdio.h>
#define NUM 5
int main(void) {
int data[NUM];
int temp = 0;
for(int i=0; i<NUM; i++) {
scanf("%d", &data[i]);
}
// 오름차순
for(int i=0; i<NUM-1; i++) {
for(int j=0; j<NUM-1-i; j++) {
if(data[j] > data[j+1]) {
temp = data[j];
data[j] = data[j+1];
data[j+1= temp;
}
}
}
// 내림차순
for(int i=0; i<NUM-1; i++) {
for(int j=0; j<NUM-1-i; j++) {
if(data[j] < data[j+1]) {
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
for(int i=0; i<NUM; i++) {
printf("%d", data[i]);
}
return 0;
}
코드 해석:
#define 상수를 사용하여 배열의 길이를 정해준다. => 배열의 인덱스[0, 1, 2, 3, 4]
첫 번째 for문은 배열의 길이에 맞게 입력을 받으며 배열의 인덱스 0부터 저장된다.
이 후 이중 for문에서 바깥에 있는 반복문은 배열의 길이만큼 다시 반복시키는 반복문이고 중심적으로 봐야하는 반복문은 안쪽에 있는 반복문이다. 안쪽 반복문의 조건식을 잘 살펴보면 j<NUM-1-i 인데 이는 반복문을 진행하며 다음 인덱스 번호로 넘어가기 위해 이러한 조건식이 구성되어 있다고 보면 된다.
=== 오름차순 기준 ===
조건문을 확인하면 아까 알고리즘에서 본 (x, y)를 비교하는 식이 나온다. 이를 현재 코드로 가져와서 확인하면 j[0] > j[0 + 1] 형식으로 진행이 되며 조건문의 증감식에 의해 j가 증가하는 것을 볼 수 있다.
만약 조건식에 해당이 된다면 data[j]가 더 크기 때문에 배열값을 잠시 저장해 줄 temp 변수에 보관을 하고 그 후 현재 원래 인덱스인 data[j]에 값이 더 작았던 data[j+1]을 대입한다. 그 후 좀 더 컸었던 수인 temp를 다음 인덱스인 data[j+1]에 대입하여 반복문을 돌아갑니다.
그 후 마지막 반복문은 정렬이 완료된 배열을 출력하는 코드입니다.
뭔가 이렇게 보면 이해가 안가니 노트나 태블릿에 원소를 하나씩 그려가며 코드를 작성하는 것이 좀 더 빠르게 이해될 것 입니다.