배열

배열이란?

배열은 같은 자료형만 묶여 놓여진 집합이다.

메모리에 연속적으로 저장해놓고 사용하는 방법으로.

이를 배열이라고 부른다.

 

 

puls + 비슷한 기능이지만 서로 다른 개념!

구조체란?

구조체란 서로 다른 자료형을 묶을 수 있는 집합이다.

기본 타입만으로는 나타낼 수 없었던 복잡한 데이터를 표현하기 유용하다. 

 

 

 

 

---

 

1. 배열의 선언 방법

배열도 그간 이용했던 자료형처럼 선언을 통해서 저장 공간을 확보해야 한다.

다만,

기존에 자료형의 선언과 달리,

하나의 이름으로 한번에 확보하여야 한다.

 

<  예      시  >

int ary [ 5 ] ;

 

1. int 는 자료형을 선언한 것이고

2. ary는 배열의 이름의 예시이다.

3. 대괄호 [] <- 안에 있는 숫자는 요소의 개수이다.

 

배열은 특별한 경우가 아니면 arr 혹은 ary로 작성하는데,

 

이는 배열의 영어 이름이 'array' 이기 때문이다.

 

배열명은 적절하게 변수명을 짓는 규칙에 따라 짓는 것이 좋다.

 

 

 

2. 배열의 사용

배열을 선언할 때와 배열의 요소를 사용할 시 대괄호([ ]) 안의 숫자는 의미가 다르다.

배열의 첨자이자 인덱스(index)는 0부터 시작하여 최대 '배열 요소 개수 - 1'까지만 사용한다.

이후에 더 문자를 넣어 배열을 선언하면 오류가 생겨 실행할 수 없게 된다. 

 

※인덱스(index)는 0부터 시작하여 최대 '배열 요소 개수 - 1'까지만 사용하지 않는 다면?

 

(첨자와 인덱스는 같은 뜻이다. 즉, 한국어냐 영어의 차이)

인덱스(index)는 각 배열의 공간을 분리하여 구분하는 인지 번호이다.

 

만약, 인덱스가 배열의 요소 개수 -1이 초과하게끔 입력한다면,

배열은 오류가 생겨 사용할 수 없게 된다.

이때 생기는 오류 코드는 E0146 과 C2078로 각각

이니셜라이저 값이 너무 많고, 이니셜 라이저가 너무 많아서 생기는 오류이다.

 

 

만약, 인덱스가 배열 요소 개수보다 부족하다면

오류는 생기지 않으나 출력 시에 부족한 인덱스 번호는 NULL값 처리 된다.

즉, 인덱스가 부족하더라도 초기화가 가능하다.

printf 출력시 예시와 같이 출력된다.

 

<  예      시  >

visual studio c 언어 입력값 예시

#include <stdio.h> int main(void) { int a[5] = { 1,2 }; for (int i = 0; i < 5; i++) { printf("%d ", a[i]); } return 0; }

디버그 콘솔창 출력 예시

1 2 0 0 0

 

2차원 배열

앞서 말한 내용은 1차원 배열이며 우리 내 시공간이 단순한 1차원이 아닌 것 처럼

배열도 1차원, 2차원, 3차원으로 겹겹이 쌓아 올려나갈 수 있다.

 

대표적인 예로 2차원 배열을 위주로 설명하겠다.

 

다음 예시는,

2차원 배열을 선언과 초기화하는 예시이다.

 

<  예      시  >

visual studio c 언어 입력값 예시

#include <stdio.h> int main(void) {      int arr[3][4] = {      {1, 2, 3, 4},      {5, 6, 7, 8},      {9, 10, 11, 12},      };      return 0; }

이러한 2차 배열은 이론적으로는 {1, 2, 3, 4} 한 열이 하나의 인덱스이지만,

실질적 용도는 실제 데이터를 저장하는 부분배열의 요소를 말한다.

 

2차원 배열 ary의 이론적인 배열 요소의 개수는 3개이며

2차원 배열 ary의 실질적인 배열 요소의 개수는 12개이다.

 

 

다음과 같이 주소에 정수 연산을 하느냐 배열의 정수 연산을 하느냐에 따라

sizeof의 값이 변동 될 수 있다. 배열에 sizeof 값을 구하는 방법을 잘 안다면Quick Sort나 Bubble Sort를 잘 활용 할 수 있다.

 

이에 대한 sizeof에 대한 예시로

 

arr[12]; 

 

가 정의 되었다고 가정해보자.

 

배열의 정수 연산

arr + 1  => 685478 + ( 1 * sizeof(Ary[0])) => 685478  + ( 1 * 4 ) => 685482 ( + 4가 되었다)

 

배열의 주소에 정수 연산

&arr + 1 => 685478 + ( 1 * sizeof(ary)) => 685478 + ( 1 * 20 ) => 685490 (+ 12이 되었다)

 

둘의 차이는 배열의 정수를 연산할 때 +1을 하면

배열의 요소 중 하나의 크기 4바이트 (= int 1개의 바이트)가 + 1 되어 연산 되는 것이고,

배열의 주소에 정수 연산을 하는 것은 +1을 할 때는,배열의 전체 크기인 12바이트가 +1 되어 연산된다.

 

이러한 이유는 배열의 정수 연산과 배열의 주소 연산의 초기 주소 출력 값이 같은 이유는

배열의 주소는 첫번째 인덱스의 주소를 가지고 있기 때문이다. 

 

하지만 그럼에도 불구하고 연산 결과가 다른 이유는

 

배열의 정수 연산에서 같은 주소라 할지라도,

첫번째 인덱스 주소를 가진 인덱스의 크기만큼 +1을 한것이고,

배열의 주소에 정수 연산은 배열의 전체 주소를 뜻하기에 배열 전체 크기만큼 +1을 하였기 때문이다.

 

그럼 sizeof 를 활용하여,

 

무작위의 수의 크기로 선언된 배열을 간단하게 정렬하는

알고리즘 두가지를 말하겠다.

 

1. 퀵소트 (Quick Sort)

퀵소트는 다른 정렬 알고리즘 (ex. 버블 소트) 와 다르게

퀵소트 또한 버블과 같이 인접한 레코드를 비교하긴 하나,

비교를 줄여나가며 진행되는 분할정복 알고리즘이다.

 

 

기본적인 틀은 간단하게, 특정한 기준인 피벗 ( Pivot )을 잡고,

피벗 ( Pivot )을 기준으로 왼쪽 이동 혹은 오른쪽 이동으로

오름차순과 내림차순으로 배열을 정렬하는 것이다.

 

대 소를 구분하는 Swap하는 과정으로 진행되어,

피벗 ( Pivot )으로 인한 비교연산으로 인해 큰수들은 섞을 필요가 없어지기에

연산 속도가 현저히 줄어든다는 장점이 있다.

 

이에 대한 자세한 예시로

만약 버블정렬로 arr[9]를 나타낸다면 9*9 = 81번을 연산해야 하지만,

퀵소트는 절반이상의 연산을 하기에 연산 속도의 이점을 준다.

 

때문에  피벗 ( Pivot )은 가장 중간값을 설정하는 것이 이점이 된다.

 

1. 버블 소트 (Bubble Sort)

버블 소트는 인접한 2개의 레코드를 비교하여 검사하는 알고리즘으로,

선택 정렬과 기본 개념이 유사하다.

 

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로

2회전에서는 맨 끝에 있는 자료는 정렬에서 제외됨을 반복하여

1회씩 증가될 때 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해

배열의 모든 다른 요소들과 교환된다.

 

일반적으로 자료의 교환 작업인 스왑(SWAP)이 자료의 이동 작업인 (MOVE)보다

더욱 복잡하기 때문에

버블 소트의 단순성은 높지만

실상 거의 쓰이지는 않는다.

 

하지만 알고리즘을 입문할 시 이해하기 좋은 단편적인 예시로,

버블 소트의 이해는 알고리즘의 이해를 돕는다.

 

" 버블 소트와 퀵 소트의 차이점 "

 

버블 소트의 시간의 복잡도는

비교 횟수의 최상, 평균, 최악 모두 일정하나,

퀵 소트의 시간의 복잡도는

비교 횟수의 (피벗이 얼마나 중간값이냐에 따라 결정된다)

최상, 평균, 최악으로 나뉜다.

 

 

아래는 정렬 알고리즘의 시간의 복잡도를 비교한 표이다.

이를 참고하면 버블 정렬(= 소트)와 퀵 소트(= 정렬)의 차이를

가시성 높게 이해할 수 있다.

 

Name	Best	Avg	Worst	Run-time (정수 60,000개) 단위 : sec
삽입 정렬	n	n²	n²	7.438
선택 정렬	n²	n²	n²	10.842
버블 정렬	n²	n²	n²	22.894
셸 정렬	n	n½	n²	0.056
퀵 정렬	nlog₂	nlog₂n	n²	0.014
힙 정렬	nlog₂n	nlog₂n	nlog₂n	0.034
병합 정렬	nlog₂n	nlog₂n	nlog₂n	0.026

단순하게 구현할 수 있지만 비효율적인 방법으로는

삽입 정렬, 선택 정렬, 버블 정렬이 있으며,

 

복잡하지만 효율적인 방법으로는

퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬이 있다.

 

 

퀵 정렬과 버블 정렬의 용례는 다음 문제를 통해 알아보자.

 

자료 정리 참고 출저

https://sark95.tistory.com/ ( 퀵소트 )

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html ( 버블 정렬 )