기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.
1) 자릿수를 기준으로 차례대로 데이터를 정렬하는 정렬 알고리즘
2) 각 데이터를 자릿수를 기준으로 분류하므로, 가장 큰 자릿수를 D라고 했을 때 0(DN)
의 시간 복잡도를 가진다
3) 자릿수의 개수만큼 반복
1) 자릿수: 1의 자리
2) 계수 정렬과 비슷하지만, 차이점은 누적값을 가진다. 누적값을 구하는 이유는 결과배열을 만들기 위해서이다.
3) 결과배열은 원소의 뒤에서 부터 확인한다.
4) 34를 처리했으니 -1을 처리해서 3이 되었다
5) 그 다음 원소도 동일한 방법으로 처리한다
6) 1의 자리까지 정렬 완료!
7) 자릿수: 10의 자리
8) 자릿수: 100의 자리
9) 정렬 완료
𝑂(ㅇ𝑁)
인 정렬 알고리즘이다
그림들 덕분에 이해가 잘되어 도움이 많이 됐습니다 :)