버블정렬1 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. 이전 1 다음
