C언어 - (8) 배열, 정렬

- 배열

 

배열을 사용하면 한 번에 여러 개의 변수를 생성할 수 있다.

배열은 메모리의 연속적인 공간에 저장된다.

 

자료형 배열이름 [요소의 개수];
EX) int scores[10];

 

인덱스 : 배열 원소의 번호

​

배열의 가장 큰 장점은 반복문을 사용해서 배열의 원소를 간편하게 처리할 수 있다.

EX)
for(i=0; i<SIZE;i++)
     score[i]=0;

 

 

- 배열의 초기화

초기값의 개수가 요소들의 개수보다 적은 경우에는 앞에 있는 요소들만 초기화된다.

나머지 배열 요소들은 모두 0을 초기화된다.

 

int scores[5]={1,2,3,4,5};

 

 

- 배열의 비교

배열 a와 b를 a==b로 하면 같지 false값이 나온다.

배열은 요소의 값을 비교해야 한다.

​

- 배열과 함수

배열의 경우에는 사본이 아닌 원본이 전달된다.

 

average(scores);
int average(int scores[])
{
~
}

함수에서 원본 배열의 변경을 금지하기 위해서는

const int scores[]를 사용하면 된다.

​

- 2차원 배열

int s[1][2] 이런 식으로 표현한다.

앞의 값은 행 뒤의 값은 열을 의미한다.

 

- 정렬

 

- 선택 정렬

정렬이 안 된 숫자들 중에서 최소값을 선택하여 배열의 첫번째 요소와 교환한다.

 

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]; 
     list[i] = list[least];
     list[least] = temp;
}

 

- 순차 탐색

배열의 원소를 순서대로 하나씩 꺼내서 탐색키와 비교하여 원하는 값을 찾아가는 방법이다.

원하는 값이 초반에 있다면 좋겠지만, 후반에 있다면 매우 비효율적인 코드가 된다.

 

for(i = 0; i < SIZE; i++)
     if(list[i] == key)
          pass;

 

- 이진 탐색

정렬된 배열의 중앙에 위치한 원소와 비교하는 것을 되풀이한다.

순차 탐색의 단점을 보완한 형태이다. 백준에서도 자주 나오는 알고리즘이다.

 

int low, high, middle;
low = 0;
high = n-1;
while( low <= high ){ 
       printf("[%d %d]\n", low, high); 
       middle = (low + high)/2;
       if( key == list[middle] ) 
            return middle;
       else if( key > list[middle] ) 
            low = middle + 1;
       else
            high = middle - 1; 
}