배열과 정렬

1차원 배열과 정렬

정렬함수 Sort()

sort 함수 : 퀵(기본) → 힙(재귀 깊을 때) → 삽입(데이터 적을 때) $\leftarrow$ $nlog(n)$의 시간복잡도

    _CONSTEXPR20 void sort(const _RanIt _First, const _RanIt _Last) {
        _STD sort(_First, _Last, less<>{});

params

• 순회 첫번째 주소 : RanIt_First
• 순회 두번째 주소 : RanIt_Last
• 비교 함수

# include <algorithm> 				 // sort 함수 라이브러리
sort(arr, arr+len);                  // 오름차순 (default: less<>)
sort(arr, arr+len, greater<type>());  // 내림차순

배열의 길이 구하기

배열 변수 arr 이고, 원소의 개수를 len이라 하였을 때 아래와 같다.

sizeof()는 자료형의 크기를 Byte단위로 반환한다. (type(Byte) * len)
고로 sizeof(arr)는 전체 배열의 길이를 Byte 단위로 반환한다.
원소의 개수를 구하려면 타입의 크기(Byte)로 나눈다.

/*
배열의 원소를 인덱싱하고 이를 sizeof 함수에 parse 하여 구할 수도 있으나,
자료형을 명시적으로 sizeof 함수에 parse 하여도 됨
*/
int arr[5] = {0};
len = sizeof(arr)/sizeof(arr[0]);  //	배열 전체 Byte 길이 / 타입의 크기
len = sizeof(arr)/sizeof(int);

구조체와 정렬

구조체(struct) 는 서로 다른 타입의 변수들을 하나로 묶는 사용자 정의 자료형이다. 기본 자료형(int, double 등)과 달리 비교 기준이 없으므로, sort() 사용 시 비교 함수를 직접 정의해야 한다.

사용자 정의 비교 함수(구조체의 경우)

bool compare(const Score& a, const Score& b) {
    if (a.english != b.english) return a.english > b.english;
    return a.math > b.math; // 동점 처리
}

• const Score& : 읽기 전용 참조 → 값 변경 방지 + 메모리 절약

구조체 내부 연산자 오버로딩

bool operator<(const Score& other) const {
    return math > other.math; // '<' 재정의로 내림차순 동작
}

• sort()는 기본적으로 < 기준 → operator< 재정의로 정렬 기준 커스터마이징
• 연산자 오버로딩 operator에 대해선 씹어먹는 C++ 참고 : https://modoocode.com/202

계수 정렬(CountSorting)

• 예) 1~1,000 범위의 자연수 10^10개의 정렬 문제
• 범위가 제한된 자연수에 특화 → 시간복잡도 O(N+K), K = 최댓값
• 자연수 인덱스 마다, 해당되는 값을 만날 때에 incremental 연산

int count[1001] = {0};
int N; cin >> N;             
for (int i = 0; i < N; i++)
	int ele;
    cin >> ele;
    cout[ele] = count++; // 출현 횟수 카운팅