행복한 연어의 이야기

안녕하세요. 오늘은 삽입 정렬과 간접 삽입 정렬에 대해서 알아보도록 하겠습니다. 1. 삽입 정렬(Insert Sort)이란? 이미 정렬된 부분에 키를 삽입하는 동작을 반복하는 정렬입니다. 배열이 있다고 했을때 루프문을 돌수록 왼쪽에 있는 값들은 1 2 7 8 이런식으로 정렬이 되고 5 라는 값이 나왔을때 1 2 5 7 8 이런식으로 정렬되어 있는 값 사이에 삽입 된다 하여 붙여진 이름입니다. 2. 삽입 정렬의 특징 적은 비교, 많은 교환 안정성 O O(N²) 의 시간복잡도 많은 교환을 하기 때문에 큰 자료형일수록 부담이 크다. (간접 정렬을 고려해볼만 하다.) 정렬되어 있을수록 빠르고 역순일 경우 상대적으로 느리다. 역순일 경우 느리다는 단점을 보완한 쉘 정렬 - 안정성 X, O(n^1.5)이 있디. 선..