[Sort] 삽입정렬 - Insertion Sort
앞에 있는 array들이 정렬되어있고 현재 위치의 값을 앞 정렬된 array 중, 알맞은 곳에 삽입하는 방법 -> 코드화 하면 삽입보다는 뒤에서 앞으로 하나씩 검사(현재 위치의 값과 비교)해서 SWAP해나가는 방식 머릿속에서는 삽입이지만 사실 뒤에서부터 앞방향으로 검사 & SWAP 해서 자리 찾아가는 방식 시간복잡도 For문이 2번 중첩되어 최악의 경우 뒤에서 앞으로 모든 검사를 다하며 찾아가서 선택정렬과 O(n^2)으로 비슷하겠지만 데이터가 정렬이 거의 되어 있는 상태라면 각 idx에 대해서 검사시간이 줄어들어 빠르게 동작한다 import sys input = sys.stdin.readline arr = [4, 2, 6, 1, 9, 23, 45, 21, 28, 19] def insertionSort(a..
2021. 9. 12.
[Sort] 선택정렬 - Selection Sort
무작위로 데이터들이 있을 때, 가장 작은 수를 맨 앞에 있는 것과 바꾸고 나머지 것들에 대해 또 다시 같은 과정을 반복 가장 작은 것은 맨 앞으로! 시간복잡도 for 문을 두번 돌면서 n개의 위치에 대해 제일 작은 것을 찾기 위해 n, n-1, n-2 ... 1번 탐색을 진행한다. n(n-1)/2로 O(n^2)의 시간복잡도를 가진다 import sys input = sys.stdin.readline INF = int(1e9) arr = [4, 2, 6, 1, 9, 23, 45, 21, 28, 19] def selectSort(arr): for i in range(0, len(arr)-1): min_val = INF min_idx = -1 for j in range(i, len(arr)): if min_v..
2021. 9. 12.