전체 글 (171) 썸네일형 리스트형 [정렬] 각 정렬의 장단점 및 시간 복잡도 장단점 시간 복잡도 출처 [정렬] 삽입 정렬 [Insertion Sort] 삽입 정렬에 대해 알아보자. 사진 출처 개념 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬한다. 특징 버블/선택 정렬은 내부에서 정렬이 거듭될수록 탐색 범위가 줄어든다. 하지만 삽입 정렬은 오히려 정렬 범위가 늘어난다. 복잡도 버블, 선택 정렬과 마찬가지로 별도의 추가 공간을 사용하지 않는다. 주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다. 모든 데이터가 현재 데이터가 되어야 하므로 O(N)이 필요하다. 현재 데이터는 정렬된 데이터들과 비교하기 위해 O(N)이 필요하다. 따라서 시간복잡도는 O(N^2)이다. 구현 def insertion_sort(li): for end in range(1, len(li)): for i in range(en.. [정렬] 선택 정렬 [Selection Sort] 선택 정렬에 대해 알아보자. 사진 출처 개념 정렬되지 않은 부분에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환한다. 이를 모두 정렬될 때까지 반복한다. 복잡도 버블 정렬과 마찬가지로 별도의 추가 공간을 사용하지 않는다. 주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다. 가장 작은 원소를 앞에 계속 쌓아주기 위해 O(N)이 필요하고, 가장 작은 원소를 찾기 위해 O(N)이 필요하다. 따라서 시간복잡도는 O(N^2)이다. 구현 def selection_sort(li): l = len(li) for i in range(l - 1): min_idx = i for j in range(i + 1, l): if li[j] < li[min_idx]: min_idx = j li[i],.. 이전 1 ··· 8 9 10 11 12 13 14 ··· 57 다음
