컴퓨터 알고리즘 초급 #7 ( 계수정렬, 기수정렬 ) 선형 정렬 알고리즘
비교를 이용하는 정렬 지금까지 소개한 모든 정렬들은 비교연산으로 정렬 하였다. 비교 연산이란 둘중 누가더 큰지를 비교하여 연산하는 것이다. - 비교정렬의 하한값 : 비교연산으로 정렬하는 방법은 아무리 빨라도 오메가(n lg n)보다 느리다. 1. 계수 정렬 - 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. 0이 몇갠지 세고, 1이 몇갠지 세서 3개의 0을 앞에두고 5개의 1을 뒤에 둔다. 입력된 배열 A에 가장 작은 숫자가 무엇이고, 가장 큰 숫자가 무엇인지를 확인해 보고, 그 배열안에 0이 몇개 1이 몇개 2가 몇개 3이 몇개 를 세야한다. A에서 가장 작은값이 0이고, 가장 큰 값이 5 이므로 6개의 cell 을 가지는 배열을 만들어서, 각 숫자가 몇개인지 세어 배열에 넣어준다. 이런식으로..
Study/소프트웨어
2020. 7. 6. 17:51