C언어 | 버블정렬(Bubble Sort) 과 선형검색 (Linear Search) | 동적 메모리 할당
버블정렬은 기본적인 정렬 방법이다. 인접한 두 배열의 값을 비교하면서 왼쪽의 값이 오른쪽의 값보다 크면 교체한다.
정렬중에 가장 쉽다고 하는데 막상 C언어로 표현하려면 헷갈리기 쉽다.
쉬운 알고리즘은 별로 없다. 알고리즘을 다루는 실력이 없으면 소프트웨어 개발도 쉽지 않다.
어떤 프로그램을 짜건 그것이 유용한 프로그램이 되려면 좋은 알고리즘이 필요하다.
알고리즘을 잘 하기 위해서는 머리가 좋아야 한다고 하는데, 그건 인생 전반에 관련된 이야기고...
C언어를 잘하려면 코드를 진지하게 대하는 태도가 필요하다.
*버블정렬
*다음은 버블 정렬의 예시다. 코드는 조금씩 다를 수도 있다. for 문이 아니라 while 문을 사용해도 되고 매크로를 써도 된다.
함수를 볼 때 우선 원형부터 본다. 원형의 선언은 보통 소스코드의 main 함수 위쪽에다 하니까... 이것을 보고 사용방법을 추론해야 한다. 실제 상세한 사항은 세부 코드를 보기 전까지는 알 수가 없다.
정수형 배열을 받고, 배열의 사이즈(요소의 개수)를 받는다. 배열을 받지만 실제는 int *arr 의 포인터로 받는다. 함수 내부에서 sizeof(arr) 연산자를 사용할 수 없는 것은 배열이 아니라 포인터기 때문이다.
버블 소트는 for 문을 두번 돌림으로써 완료한다. 내부 for 문을 돌때마다 적어도 하나의 숫자의 위치는 확정 될 것이다.
배열이 10개 있다면 10x10 의 루프를 돌면 모든 비교를 다할 것이다. 거기서 좀 잘라본다. 먼저 10-1이 된다. 두개를 비교하기 때문에 비교는 9번 한다. 코드에서는 size-1 로 표현된다. 그리고 한번의 내부 루프를 돌때마다 하나의 숫자는 확정되기 때문에 루프 숫자를 하나씩 줄일 수 있다. 9, 8, 7, 6 회... 이런 식으로 줄인다. 마지막 두개의 숫자 비교가 끝나면 루프는 종료할 것이다.
swap 은 매크로 함수를 사용하는게 좋을 것이다. 함수와 다르게 타입도 변환할 수 있다. 나중에 float 나 double 로 바꿔도 사용할 수 있다.
위 코드는 끝에서부터 두개씩 비교하며 내려온다. 짧은 코드지만 몇번 돌려봐야 제대로 돌아가는지 알 수 있다.
사용 코드는 아래와 같다. (LINE, DOUBLE_LINE)는 선을 그리는 매크로다.
*선형검색
선형검색은 크게 어렵지 않다. for 루프를 끝까지 돌아서 찾아낸 키값을 반환한다. 못찾았으면 -1 을 리턴한다.
인덱스는 0부터 시작하므로 11이면 실제로는 12번째 요소다.
동적 메모리할당을 했으니 배열의 사용이 끝났으면 free(배열) 메서드로 메모리를 해제해준다. 아래 소스코드에서 보면 int *array 포인터의 메모리를 해제한 후 다시 메모리를 할당해서 사용했다. 만약 사용한 중간에 해제하지 않으면 그만큼 메모리를 낭비한다. 예제 정도의 몇 바이트라면 문제가 안될지 모르지만 1메가짜리 이미지를 1000개 복사해야 한다면 어떻게 할 것인가? 상업용 프로그램에서 이런 일은 흔히 일어날 수 있는 일이다. 바로 바로 메모리를 해제하는 습관을 갖는게 좋다.
컴퓨터의 메모리가 계속 늘어나고 있지만 프로그램의 덩치도 커지고 있다. 특히 요새의 데이터는 일단 예전에 비해 양이 많다. 여전히 메모리 관리는 중요하다. free(배열) 사용하는 것 항상 주의한다.
알고리즘은 온라인에 수많은 자료들이 퍼져 있는데 어떤 문제들은 몇시간이나 하루가 걸리는 문제도 있고 사람들이 풀지 못하는 문제도 있다. 처음부터 너무 무리하지 말고 자신에게 적당한 교재나 사이트를 활용하는 것을 추천한다. 외국에서도 온라인에서 가장 핫한게 알고리즘 학습사이트인데 GAFA (구글, 애플, 페이스북, 아마존) 입사를 꿈꾸는 사람들에게 각광을 받고 있다. 소위 신의 직장이라는 곳이니까 이해가 간다.
그런 만큼 커뮤니티와 자료는 많이 있다. 잘 활용하면 좋을 것이다.
* 소스코드
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LINE printf("---------------------------------------------\n")
#define DOUBLE_LINE printf("\n=============================================\n\n")
#define swap(type, x, y) { type t = x; x = y; y = t; }
void bubbleSort(int a[], int size);
void fillArrayRandom(int arr[], int count, int range);
void showArray(int arr[], int count);
int linearSearch(const int arr[], int count, int key);
int main(int argc, char const *argv[])
{
DOUBLE_LINE;
srand(time(NULL));
// 버블정렬
int count = 10; // 배열 요소의 개수
int *array;
array = calloc(count, sizeof(int)); // count * 4 바이트 배열 동적할당
printf("[배열 정렬 전]\n");
fillArrayRandom(array, count, 100); // 1~ 100의 난수를 배열에 채운다
showArray(array, count);
LINE;
printf("[버블정렬 후 - 오름차순]\n");
bubbleSort(array, count);
showArray(array, count);
free(array);
DOUBLE_LINE;
// 선형검색
count = 15; // 배열의 개수
array = calloc(count, sizeof(int)); // count * 4 바이트 배열 동적할당
int key = 15; // 검색할 값
printf("[배열 생성]\n");
fillArrayRandom(array, count, 100); // 1~ 100의 난수를 배열에 채운다
showArray(array, count);
LINE;
int result = linearSearch(array, count, key);
(result == -1) ? printf("찾는 요소 %d가 배열에 없습니다...\n", key) :
printf("요소를 찾았습니다. 인덱스 (%d) 값 = %d\n", result, key);
free(array);
return 0;
}
int linearSearch(const int arr[], int count, int key)
{
printf("searching index : ");
for (int i = 0; i < count; i++)
{
printf("%d.. ", i);
if (arr[i] == key){
printf("MATCH FOUND!\n");
return i;
}
}
printf("\n");
return -1;
}
void bubbleSort(int arr[], int size)
{
int i, j;
for (i = 0; i < size-1; i++)
{
for (int j = size-1; j > i; j--)
{
if(arr[j-1] > arr[j])
swap(int, arr[j-1], arr[j]);
}
}
}
void showArray(int arr[], int count)
{
printf("[");
for (int i = 0; i < count; i++)
{
printf("%d, ",arr[i]);
}
printf("]\n");
}
void fillArrayRandom(int arr[], int count, int range)
{
for (int i = 0; i < count; i++)
{
arr[i] = rand() % range + 1;
}
}
