[알고리즘] 기수정렬의 개념과 원리 - Rowen Jobs

기수정령의 개념과 원리 _ by.하루코딩,copy RowenJobs

값을 비교하지 않는 특이한 정렬이고 자릿수를 정한 다음 해당 자릿수만 비교한다. 

시간 복잡도는 kn 이고 k 는 자릿수 시간복잡도가 가장 짧은 정렬이다.

큐를 만들어 넣는 부분이 좀 어려워질수 있다. 

 

기수정렬은 10개의 큐를 이용 한자릿수에 올 수 있는 자릿수는 0 ~ 9 라 10개의 큐를 이용

 

일의 자리를 정렬을 하고 ~ N 의 자리까지 큐에 넣어 정렬을 한다. 

아래는 강의 예시를 참고해서 확인하면 된다.

 

첫번째 이미지는 일의 자릿수에 대해 큐에 넣고 순서대로 정렬한 이미지 이고

두번째 이미지는 1차적으로 정렬한 배열의 각 십의자리에 대해 큐에 넣고 그대로 정렬을 한 이미지 이다. 

 

큐는 선입선출의 규칙을 가지고 있어 먼저 들어온 데이터가 나가 위오 같이 진행이 된다.

2023.07.27 - [코딩테스트/Study] - [알고리즘] 스택과 큐에 대한 개념정리

[알고리즘] 스택과 큐에 대한 개념정리

위 게시글을 보면 이해하는데 도움이 될거라 예상한다(개발자는 그림판이지..)

 

기수정렬에 대한 핵심과 원리에 대해 정리하였고 참고한 강의는 아래와 같다.