정렬

=배열을 효과적으로 이용하기위한 사용법
=데이터를 특정 기준에 따라 정리정돈
=데이터가 많을때 컨트롤하기 용이하게 하기위해서
(도서관 서고 생각 - 분야 및 책시리얼넘버)

• 이전까지는 데이터를 배열에 집어넣어서 저장하는것까지했다고하면 이제는 이걸 꺼내서 사용 및 값 변경하는 것을 학습하는것

• 종류는 내림차순(큰 수 -> 작은 수 순),오름차순(작은 수 -> 큰 수 순)등 여러가지 기준이 있음(숫자 크기의 변환 방향으로 생각하자)

• 정렬은 무조건 해야된다(x) 정렬은 필요한 경우에는 하는게 좋다(o)

• 정렬의 대상은 데이터 값이다.(인덱스는 0부터 오름차순으로 정렬이 고정되어있음)

정렬의 종류

1.선택정렬(오름차순 가정하에)
개념: 선택정렬은 일단 첫번째 값을 시작으로 배열의 나머지 값과 하나씩 다 비교하여 최소값과 교환을 하고 고정을 한 이후에 다시 다음 데이터를 기준으로 그 외 나머지 숫자들을 앞과 같이 비교하는식으로 반복하는 정렬임
(앞에서부터 완성해나간다고 보면됨)

-> 선택정렬도 결국 함수이며, 조건식과 반복문의 조합이 함수 내용인걸 짐작할 수 있다.
또한 값을 건드린다는건 주소값을 인자로 써야겠다는 것도 생각할 수 있음.

• 주소값을 넘겨주면 함수가 무조건 값을 바꿔준다(x)
  -> 함수가 주소값을 써도 값이 변하지않게할 수도 있음.근데 안해주면 값을 바꿀려면 for문 써서 일일히 바꿔줘야하기에 번거로우니 주소값 넘겨줘서 일괄 처리하는게 나음

코드 예시
#include <stdio.h>
#define SIZE 10

void selection_sort(int list[], int n);
void print_list(int list[], int n);

int main(void)
{
int grade[SIZE] = { 3, 2, 9, 7, 1, 4, 8, 0, 6, 5 };

//원래의 배열 출력
printf("원래의 배열\n");
print_list(grade, SIZE);

selection_sort(grade, SIZE);

// 정렬된 배열 출력
printf("정렬된 배열\n");
print list(grade, SIZE);

return 0;
}

void print_list(int list[], int n)
{
int i;
for(i = 0;i < n; i++)
printf("%d ", list[i]);
printf("\n");
}

void selection_sort(int list[], int n)
{
int i,j,temp,min;

for(i=0; i<n-1; i++)
{
min = i;

for(j = i + 1; j < n; j++) // 최소값 탐색
{
if(list[j] < list[min])
min = j;
}

// i번째 원소와 min 위치의 원소를 교환
temp = list[i];
list[i] = list[min];
list[min] = temp;
}

}

이 코드에선 크게 원래 배열을 출력하고 그리고 정렬된 배열을 출력하는 구조인데, selection_sort(grade, SIZE);은 인자로 배열을 받아 함수를 작동시키고있다. 선택정렬을 출력해주는 함수로 짠 이 코드는 인덱스를 반복시키면서 최소값을 탐색시키고 최소값이 나오면 그걸 교환하는 코드로 for문 중첩을 사용하고있다.

먼저 최소값을 배열 인덱스의 0번째 원소로 잡고, 인덱스 0부터 9까지 반복하는데 어떤 내용을 반복하냐면 앞서 말했던 하나를 고정하고 나머지를 다 비교하니 이 부분 때문에 반복문이 하나 더 들어가는것이며 그 안에서 최소값이 나오면 기존 최소값을 temp에 임시 저장시켜놓고, 새 최소값을 현재 최소값에 저장시키고,임시 저장했던걸 새 최소값이 있던 인덱스에 저장시키는 구조로 돌아간다.

예로 들어 인덱스 0부터 돌아간다고하면,0안에 들어있는 값 3이 min으로 선언이 되고, j가 1이 되고 if(list[1] < list[0])를 거치는데 list의 min번째가 더 크면 j가 최소값이 되는것이다.여기서 2<3으로 참이기에 min = 1;이 된다.그리고나서 j가 1씩 증가하면서 돌리는데 조건식이 거짓이면 스킵한다.현재 2보다 작은숫자는 인덱스 4와 7의 원소이므로,돌면 min이 7로 반복문이 끝난다.

그리고나서 밑에 코드가 돌아가는데 temp = list[0]; -> list[0] = list[7]; -> list[7] = temp;을 거치면서 list[0]에 비로소 '0'이 들어가게되고 list[7]에는'3'이들어가게된다.그럼 이제 min=1; 이 상태에서 j가 9될때까지 다시 반복되는거임([0]은 고정이니 제외)

2.버블정렬
= 선택정렬과 반대로 끝에서부터 값이 고정되면서 정렬이 완성되는 방식
기준값과 바로 옆에 있는 값만 비교를 하는데 만약 기준값보다 오른쪽 옆의 값이 작으면 위치를 바꾸고,아니면 기준값이 바로옆으로 넘어가고 그 다음 옆의 값과 비교를 하게된다.
그렇게 끝까지가게되면 기준값은 이 배열에서 가장 높은 데이터값이 되어 끝자리에 위치한다.

1회차 스캔이 이렇게 완료가 되고,2회차 스캔이 다시 시작된다.가장높은숫자-1의 숫자가 계속 뒤로 가게됨.

코드 예시
void bubble_sort(int list[], int n)
{
int i, scan, temp;

// 스캔 회수를 제어하기 위한 루프
for(scan=0; scan < n-1; scan++)
{
// 인접값 비교 회수를 제어하기 위한 루프
for(i = 0; i < n-1; i++)
{
// 인접값 비교 및 교환
if( list[i] > list[i+1] )
{
temp = list[i];
list[i] = list[i+1];
list[i+1] = temp;
}
}
}
}

이것도 선택정렬 함수 코드와 비슷한데 list[i]가 list[i+1]보다 크냐는 조건식을 이용하면된다.크다면 위치를 바꿔주면 되고,아니면 그 자리에 놔두면된다.

여기서 주의할 점은 i의 범위인데 i < n-1인 이유는 위 선택정렬 배열 기준으로 볼때 사이즈는 10이고 우리는 36바이트 즉 9칸의 int형 바이트로 정렬을 하고있다는점에서 i가 8이면 list[8]과 list[9]를 비교하게되는데 만약 n이 9라면 list[10]이 되고 범위 밖의 값이기에 오류가 난다.

##2차원 배열
데이터를 효율적으로 관리하기위해 서고나 창고처럼 배열이 행과 열로 되어있는것(수학 행렬과 유사)

int s[3][10] = 배열s[10]이 3세트있는것과 같다.

int s[10] = 1차원 배열
int s[3][10] = 2차원 배열
int s[5][3][10] = 3차원 배열

사용 예시) 게임 캐릭터 능력치
int c [3][10]

[3]은 플레이어의 수를 의미(플레이어1,플레이어2,플레이어3..)
[10]은 플레이어의 능력치를 의미(힘,민첩,지능,방어 등등 10개...)