자료구조8 기수 정렬 기수정렬(radix sort) : 자리수의 값에 따라 정렬을 하는 다단계 정렬. - 기수 : 숫자의 자리수 - 앞의 정렬방식은 레코드를 비교하여 정렬하는 방식, 비교 불가능한 레코드는 정렬할 수 없다. - 추가 메모리가 필요하지만, 속도가 빠르기 때문에 많이 쓰인다. - 단점으로는 정렬할 수 있는 레코드의 타입이 한정된다. 레코드들이 동일한 길이를 가지는 숫자, 문자열로 구성되어있어야 하기 때문. - 별도의 버킷을 만들어 입력 데이터를 각 자리수의 값에 따라 넣고 왼쪽부터 순차적으로 버킷의 데이터를 읽어온다. - 비교연산이 사용되지 않는다. - 먼저 들어간 숫자는 먼저 나와야 하기 때문에, 버킷은 큐(queue)로 구성(숫자를 넣고 빼는 연산은 큐의 삽입삭제). - 2진법 정렬시 2개의 버킷, 알파벳은 .. 2018. 1. 29. 퀵 정렬 퀵 정렬- 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방식- 병합정렬처럼 분할 정복법 사용 - 피봇(pivot)을 요소로 선택, 피봇보다 작은 요소는 피봇의 왼쪽, 큰 요소는 오른쪽으로 이동- 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하면 완료 1. 피봇 = 인덱스(처음 + 마지막)/2 왼쪽 : L 오른쪽 : R 피봇 : P L 은 L >= P 값을 찾게되고 R은 R < P 값을 찾는다2. 탐색을 하면서 같은 자리의 인덱스에서 만나기전에 두 값을 찾으면 L과 R을 SWAP 해준다3. L과 R중 하나만 값을 찾고 L과 R이 만날경우 만난 값과 피봇 값을 SWAP 해준다4. SWAP된 값을 제외한 나머지 부분을 다시 1~4 과정을 반복한다5. 피벗을 기준으로 왼쪽과 오른쪽 SWAP할 값이 .. 2018. 1. 29. 이전 1 2 다음