네이버 블로그에서
개발글만 연동됩니다. blog.naver.com/rage147-owo

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

  • C

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

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

정렬 (sorting)

오름차순 (ascending order)

내림차순 (descending order)

​

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

​

선택 정렬의 순서는

  1. 배열 중 최소값을 찾는다.

  2. 최소값을 배열의 첫번째에 위치시킨다.

  3. 첫번째를 제외한 배열에서 최소값을 찾는다

​

예시로 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리턴
}

​

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

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

업데이트: