C++[sort알고리즘]

sort 알고리즘이란?

C++에서 제공하는 STL에 있는std::sort라는 명령어로 사용하는 오름차순 정렬 알고리즘이다.

1. 배열 정렬

int n = sizeof(arr) / sizeof(arr[0]);

sizeof(arr)

sizeof는 주어진 변수의 바이트 크기를 반환합니다. 만약 변수가 int형 배열이라면, sizeof는 전체 크기를 바이트 단위로 반환합니다. 위의 예시에서는 arr배열의 원소 개수가 5이고 각 int가 4바이트라면 5*4 = 20 이라는 숫자를 반환합니다

sizeof(arr[0])

arr[0]는 배열의 첫번째 요소를 참조하는기 때문에 sizeof(arr[0])은  arr의 첫번째 요소가 int형이고 위에서 4바이트로 계산을 했기 때문에 똑같이 계산을 하게된다면 sizeof(arr[0]) = 4가 되겠죠

int n = sizeof(arr) / sizeof(arr[0]); 해석

int형 n이라는 변수의 값을 arr의 전체 크기/하나의 크기로 해줘~ = 즉 이 배열의 원소 개수를 구해줘~ 라는것이다. 이걸 굳이 쓰는 이유는 같은 요소들이 모여있는 배열들은 전부 다 이걸로 원소의 개수를 셀 수 있기 때문에 확장성을 위해 넣어봤습니다.

※주의

이 방식은 정적 배열에만 적용이되고 동적배열이나 STL컨테이너 즉 백터에는 사용되지 않습니다.

sort(arr, arr+n)

sort(x,y)

오름차순 정렬 함수, x는 시작위치를 가리키며, y는 끝 위치를 가리킨다.

arr

arr은 배열의 이름이기도 하며 배열의 첫번째를 가리킨다. 배열 이름은 해당 배열의 시작 주소를 나타내는 포인터로 사용됨.

arr+n

arr은 arr[0]의 주소를 나타내고 arr+n 은 arr[5]의 주소를 나타낸다. 하지만 arr[n]과는 엄연히 다른게 arr[n]은 배열의 인덱스 접근을 의미하며 직접참조를 합니다.  한마디로 arr+n은 주소를, arr[n]은 값을 나타낸다고 보면 됩니다

그리고 arr 배열은arr[4]까지 있는데 왜 arr[5]값을 마지막으로 하냐면 arr[5]가 배열의 끝을 의미하기 때문이다. arr+n-1을 하면 전체 정렬이 안된다.... (이것땜에 20분 헤맴....)

sort(arr, arr+n)해석

배열의 시작부터 배열의 마지막까지 오름차순 정렬해줘~

 

2. 백터 정렬

begin()

백터의 첫 번째 요소를 가리키는 이터레이터(*)를 반환합니다. 첫번째를 가리키는 포인터같은 녀석이라고 보면 된다. 

end()

백터의 마지막 요소를 가리키는 이터레이터를 반환한다.

3. 클래스의 정렬

여기에는 처음보는 함수인 compare가 있는데 이걸 설명드리겠습니다.

bool compare(const Item &a, const Item &b) 설명 및 해석까지

sort함수에서 사용될 비교함수다. 두 개의 Item 객체 a와 b를 받고 a의 값이 b의 값보다 작은 경우 true를 반환함.

& 레퍼런스를 붙힌 이유는 안에서 두개의 값을 변화시킬 일이 없는 함수이기 때문에 안전하게 a와 b의 값을 보호하기 위함

 

sort(items.begin(), items.end(), compare);

처음보는 친구가 하나 껴있는데 저렇게 뒤에 붙은 경우 정렬 기준을 제공하는 비교함수라고 보시면 됩니다.

크고 작음을 판단하는 기준은 아마 앞에 값을 먼저 비교하고, 그 다음에는 뒤의 값을 비교하는 식인거같습니다.