Algorithm/Study
2021. 9. 8.
정렬 알고리즘 : 삽입 정렬 (Python)
삽입 정렬 개념 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다. 즉 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다. 삽입 정렬은 두 번째 데이터부터 시작한다. (첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.) 두 번째 요소 1은 3의 왼쪽이나 오른쪽으로 들어가는 2가지 경우가 있다. 오름차순이므로 3의 왼쪽에 1을 삽입합한다. 2는 1의 왼쪽, 1과 3의 사이, 3의 오른쪽에 들어갈 수 있다. 2의 바로 왼쪽에 있는 3과 비교했을 때 작으므로 왼쪽으로 이동하고, 1보다 크기 때문에 이동을 멈추고 삽입된다. 즉, 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도착할 때 까지 반복한다. 이런 식으로 마지막 요소 4까지 ..
