개구리의 개발 블로그 개구리의 개발 블로그

1. O(n²) 정렬 1.1 선택 정렬 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 선택 1번째 인덱스부터 배열을 탐색하여 1번째로 작은 값을 1번째에 위치 → 2번째 인덱스부터 탐색 & 2번째에 위치 → 3번째부터 탐색 & 3번째에 위치 → … → 총 (n-1)번 반복 추가 공간 없이 주어진 배열에서 위치만 변경한다. O(1)의 공간 복잡도 시간 복잡도 1번째 루프에서 비교 : n-1 2번째 루프에서 비교 : n-2 (n-1)+(n-2)+…+1 = n(n-1)/2 최선, 최악, 평군 모두 O(n²) def selection_sort(L): for i in range(N): #해당 위치 i에 들어갈 원소를 선택 minVal_idx = i for j in range(i+1,N): if L[j] < ..