삽입정렬1 cpp) 삽입 정렬, insertion sort - 삽입정렬 배열의 각 요소를, 앞에서부터 하나씩 자신의 자리를 찾아 삽입 - 절차(오름차 기준) i) 배열의 1번 요소를 0번째 원소와 비교. 더 작다면 0번째 요소를 뒤로 옮기고, 그 앞에 1번 요소를 삽입 ii) 배열의 2번 요소를, 1번부터 0번 원소를 비교해 자리 설정 iii) 배열의 n번 요소를, n-1번부터 0번 원소와 비교해 자리 설정 - 시간복잡도 최악의 경우 = 모든 원소가 역순으로 정렬되어 있는 경우 외부 루프를 N-1번 도는 동안 비교연산은 1, 2, ... , (N-1)번 수행된다. T(n) = 1+2+...+(N-1) = (N-1)*N/2 O(n) = n^2 - 특징 정렬에 사용하는 외부 메모리 X 이를 In-place sort라고 한다. #include using namespa.. 2024. 3. 1. 이전 1 다음
