728x90 counting sort1 [Algo]-Counting Sort 요약 핵심 아이디어 카운팅 정렬(계수 정렬)은 입력을 반복하고 각 항복이 발생하는 횟수를 새로운 배열에 카운트한다. 카운트한 배열을 사용해 정렬한다. 장점 시간복잡도는 O(n) 으로 엄청난 성능을 보여주는 알고리즘이다. 대표적인 빠른 정렬 알고리즘보다 성능이 좋다. 큌 정렬, 힙 정렬, 합병 정렬 등의 시간복잡도는 O(nlogn) 으로 빠른 성능을 가지고 있다. 단점 입력값의 범위를 미리 알고 있을때만 사용하는게 좋다. 정렬을 하기 위해 새로운 배열을 선언해주어야 한다. 즉, 입력값의 범위가 커지면 메모리 낭비가 된다. ex) 5개의 원소를 정렬하고 하는데, 수의 범위가 0~5000 이라면 새로운 배열의 사이즈는 5000이 된다. 작동 애니메이션 URL https://www.cs.miami.edu/hom.. 2022. 10. 14. 이전 1 다음 728x90