정렬2 cpp) 버블정렬, Bubble Sort - 버블정렬 배열의 앞에서부터, 인접한 두 요소끼리 비교하여 자리를 교체하는 방식 이를 반복하다보면 배열의 마지막 자리에 가장 큰 요소가 위치하며 정렬되는데, 이것이 거품이 올라오는 듯 하다해서 '버블' 정렬 - 절차(오름차 기준) 길이 n의 배열의 0번부터 n-1번까지, 인접 요소끼리 비교, 자리를 적절히 교체 -> 가장 큰 요소가 마지막에 위치 0번부터 n-2번까지 인접 요소 비교, 교체 0번부터 n-3...반복 배열의 요소가 하나(0번)만 남을때 까지 수행한다. - 시간복잡도 최악,최선, 평균 모두 사이클 당 비교 횟수가 n-1번,n-2번... T(n) = (n-1)+(n-2)...2+1 = (n-1)*n/2 O(n) = n^2 - 특징 정렬에 사용하는 외부 메모리 X 이를 In-place sort.. 2024. 3. 2. 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 다음
