합병 정렬의 문제점정렬한 레코드 수에 비례하여 저장 공간이 추가로 필요최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성입력 리스트 : (26, 5, 77, 1, 61, 11, 5
두개의 정렬된 리스트를 하나의 정렬된 리스트로 합병입력 리스트를 길이가 1인 n개의 정렬된 서브리스트로 간주반복 합병 정렬 단계첫번째 합병 단계 : 리스트들을 쌍으로 합병하여 크기가 2인 n/2개의 리스트를 얻는다n이 홀수면 리스트 하나는 크기가 1두번째 합병 단계 :
평균 성능이 가장 좋은 정렬 방법입력 리스트 : (5, 3, 8, 4, 9, 1, 6, 2, 7)image 1) 정렬할 레코드 중 피벗(pivot) 레코드를 선택 2) 정렬할 레코드들을 다시 정돈 \- 피벗의 왼쪽 : 피벗의 키보다 작거나 같은 레코드들을 위치
앞에서부터 해당 원소가 위치 할 곳을 탐색하고 해당 위치에 삽입입력 리스트 : (7, 3, 2, 8, 9, 4, 6, 1, 5)image현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 타겟은 두 번째 원소부터 시작한다.)타겟이 되는 숫자가 이전
어떤 기수 r을 이용하여 정렬 키를 몇 개의 숫자로 분해r=10 : 키를 십진수로 분할r=2 : 키를 이진수로 분할기수-r 정렬에서는 r개의 빈(bin)이 필요정렬되어야 하는 레코드가 R1,,,Rn일 때, 레코드의 키는 기수-r을 이용하여 분할 -> 0~(r-1) 사이
데이터의 집합에서 원하는 값을 가진 요소를 찾아내는 것특정 항목(key)에 주목key는 데이터의 일부Key를 찾는 조건은 하나만 지정하기도 하지만 논리곱/논리합을 사용하여 복합 지정 가능데이터 집합에 대해 검색만 하는 경우 계산 시간이 짧은 것을 선택검색 뿐 아니라 데
검색할 문자열을 패턴, 문자열 원본을 텍스트라 명명함단순법, 소박법이라고도 불림첫번째 문자열부터 하나씩 비교해가며 일치하지 않을 시, 한칸 이동 후 반복모든 경우의 수를 일일이 탐색하여 정답을 찾아내기 때문에 가장 비효율적ex)검색 결과를 기억해 중간 검사 결과를 효율
크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 즉, 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다.노드 = 정점 = 도시: 그래프에서 동그라미에 해당하는 부분간선 = 거리 = 비용: 그래프에서 선에 해당하는 부분