Insertion Sort1 삽입 정렬(Insertion sort) 삽입정렬 시간복잡도 공간복잡도 전체 요소를 순회하기 위해 N 검색 범위를 넓혀가며 전체 요소까지 비교하기 위해 N N x N = O(N²) 비교 후 배열 내 스왑을 하기 위해 O(1) 정렬 범위를 한칸씩 확장하여 새로 비교할 값을 이미 정렬된 값과 비교하여 정렬하는 알고리즘 [7, 4/, 5, 1, 3] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 배열은 총 5개의 요소를 가지고 있다. 이 중 맨 앞의 2개 요소만 두고 첫번째 비교를 시작한다. 7과 4중 4가 더 작기 때문에 둘의 위치를 바꿔준다. [4, 7/, 5, 1, 3] 첫번째 순회가 끝났다. 두번째 순회를 시작한다. 이제 검색범위를 넓혀 3번째 요소, 2번 인덱스에 있는 요소를 추가하여 뒤에서부터 비교한다. 7과 5중 5가 더 작기 때문.. 2022. 7. 12. 이전 1 다음