과제 : 21,22,23,24

04-5 병합 정렬

21번 문제 (1517번 문제)

수행시간 : 1초

N(수의 개수) : 500000

버블 정렬은 시간 복잡도가 O(n^2)이기 때문에 버블 정렬을 사용하면 수행 시간을 초과 하게 된다.

따라서 버블 소트가 아닌 O(nlogn)의 시간 복잡도를 가진 병합 정렬을 사용 해야 한다.

index1 → 앞쪽 그룹 시작점

index2 → 뒤쪽 그룹 시작점

k는 A배열을 하나씩 따라가기 위한 변수

맨처음에 A배열을 tmp에 복사한 뒤

tmp을 쪼개서 정렬한 내용을 A배열에 넣고, 다시 그 정렬된 A배열을 tmp배열에 복사하고를 반복해서 최종적으로 정렬된 A배열이 나온다.

04-6 기수 정렬

기수 정렬은 값을 비교하지 않는 특이한 정렬이다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다. 기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말한다.

22번 문제 (10989번 문제)

수행시간 : 3초