C언어 배열 정렬, 탐색

title: “C언어 배열 정렬, 탐색” categories:

CPermalink

#C언어 배열 정렬, 탐색 : 네이버 블로그

정렬은 크기순으로 오름차순이나 내림차순으로 나열하는 것을 의미한다

정렬 (sorting)

오름차순 (ascending order)

내림차순 (descending order)

다양한 정렬 알고리즘이 있지만 여기서는 기본적이고 이해하기 쉬운 선택 정렬만 설명하겠다.

선택 정렬의 순서는

배열 중 최소값을 찾는다.
최소값을 배열의 첫번째에 위치시킨다.
첫번째를 제외한 배열에서 최소값을 찾는다

예시로 a[3]이라는 배열이 있을 때 a[3] = { 2, 0, 1 } 이라 하자

선택정렬의 순서를 따라가면

2 0 1 중 최소값을 찾는다 (0)

맨 앞으로 위치한다

0 2 1

0을 제외한 배열 중 최소값을 찾는다 (1)

0 1 2

아래는 C 선택정렬 예제 이다.

#include
#define SIZE 10
int main(){
 int list[SIZE] = { 3,2,9,7,1,4,8,0,6,5 }; //list[10] 초기화
 int i, j, temp, least;
 for ( i = 0; i < SIZE-1; i++)
 {
 least = i;
 for ( j = i+1; j < SIZE; j++)
 {
 if (list[j] < list[least]) //최소값을 찾는다
 least = j;
 }
 temp = list[i]; //temp를 이용해 원래 위차한 값과 최소값을 교환시킨다
 list[i] = list[least];
 list[least] = temp;
 }
 for ( i = 0; i < SIZE; i++)
 {
 printf("%d", list[i]);
 }
}

다음은 배열 탐색이다

아래는 순차 탐색 예제이다

#include
#define SIZE 10
int main() {
 int key;
 int list[SIZE] = { 1,2,3,4,5,6,7,8,9,10 };
 printf("탐색할 값을 입력하시오");
 scanf("%d", &key);
 for (int i = 0; i < SIZE; i++) //i를 올리며 list[i]를 1씩 올린 후 입력한 key와 비교
 {
 if (list[i] == key)
 printf("탐색 성공 인덱스 = %d\n", i);
 }
 printf("탐색 종료\n");
}

탐색은 찾아야 하는 정보를 빠르고 쉽게 찾을 수 있게 해준다.

아래는 이진 탐색이다. 이진 탐색은 배열의 중간값과 찾아야 하는 값을 비교해 탐색해 나가는 방식이다.

즉 a{4} = {0,1,2,3} 이 있고 3의 위치를 찾고싶다면

최소값 0 과 최대값 3을 더하고 2로 나눈 값(중간값) 1(정수형이니 소수점 버림)

중간값이 1이니 찾고자 하는 값 3이 중간값보다 큰가 작은가를 비교한다

중간값보다 크니 이제 최소값 1, 최대값 3 이니 중간값은 2이다.

찾고자 하는 값(3)이 2보다 큰지 비교한다.

중간값보다 크니 이제 최소값 2, 최대값 3 이니 중간값은 2이다.

찾고자 하는 값(3)이 2보다 큰지 비교한다.

남은 수는 3이니 3의 배열의 위치를 찾을 수 있다.

이진 정렬은 꼭 크기 순서대로 배열이 되있어야 한다.

아래는 이진 정렬의 예제이다.

#include
#define SIZE 16
int binary\_search(int list[], int n, int key); //이진 탐색 함수
int main() {
 srand(time(NULL)); //랜덤 시드
 int key;
 int sum = 1;
 int grade[SIZE];
 for (int i = 0; i < SIZE; i++) {
 sum = sum + rand() % 100; //순서대로 배열을 1부터 100까지 랜덤으로 더해가며 만든다
 grade[i] = sum;
 printf("%d ", grade[i]);
 }
 printf("탐색할 값을 입력하세요 ");
 scanf("%d", &key);
 printf("탐색 결과 = %d\n", binary\_search(grade, SIZE, key));
}
int binary\_search(int list[], int n, int key) { //배열,배열의크기.찾을키를 입력받는다
 int low = 0, high = n - 1, middle; //최소값의 배열 위치는 0, 최대값 배열위치는 n-1 이다
 while (low <= high) { //최소값이 같아지면 반복이 끝난다
 printf("[%d %d]\n", low, high); //서로 비교하는 값 low high
 middle = (low + high) / 2; //중간배열위치 찾는다
 if (key == list[middle]) //중간배열위치[middle]이 key와 같으면 key 출력
 return middle; //중간값이 계속 변해 key의 값과 같아지면 출력한다
 else if (key > list[middle]) //list[middle]이 큰가 작은가 비교
 low = middle + 1; 
 else
 high = middle - 1;
 }
 return -1; //탐색해도 key가 없으면 -1리턴
}

이번 포스팅은 배열의 정렬과 탐색을 알아보았다.

배열의 데이터를 효율적으로 이용하기 위해서는 정렬과 탐색을 적절히 이용할 수 있어야 한다.

CPermalink