sort2 단순 삽입 정렬 이번에 소개할 정렬 방식은 단순 삽입 정렬입니다. 단순 삽입 정렬은 셔틀 정렬이라고 부르기도 합니다. 1. 단순 삽입 정렬 단순 삽입 정렬은 선택한 요소를 선택한 요소 앞쪽의 알맞은 위치에 삽입하는 정렬입니다. 단순 삽입 정렬의 시간 복잡도도 O(n^2)로 단순 선택 정렬, 버블 정렬과 같습니다. 선택 정렬과 마찬가지로 정렬된 부분과 정렬되지 않은 부분으로 나누어서 이용합니다. 자세한 삽입 정렬법은 그림으로 소개해드리겠습니다. 위와 같은 배열이 있다고 할 때 단순 삽입 정렬은 0번째가 아닌 1번째 인덱스 부터 정렬을 시작합니다. 그리고 첫번째 요소인 0번 인덱스는 정렬된 부분이라고 두고 시작합니다. 1번째 인덱스 요소인 7과 왼쪽요소를 비교합니다. 이때 왼쪽 요소는 정렬된 부분의 가장 마지막 요소입니다... 2021. 10. 12. 버블 정렬 Bubble Sort 처음으로 소개드릴 알고리즘은 정렬 중에서도 버블 정렬입니다. 버블이라는 어원은 컵에 액체를 따르면 액체 보다 가벼운 공기 방울(버블)이 컵위로 떠오른다는 점에서 착안하여 버블 정렬이라는 이름이 붙게 되었습니다. 1. 버블 정렬 버블 정렬은 인접한 두 요소의 대소 관계를 비교해서 정렬합니다. 버블 정렬은 가장 간단한 형태의 정렬이며 시간복잡도는 O(n^2)로 요소가 많아질수록 느립니다. 다음과 같은 배열을 오름차순 버블 정렬해보겠습니다. 이렇게 양옆의 요소들끼리 비교하여 요소의 크기가 작으면 앞으로 보내고, 크기가 크면 뒤로 보냅니다. 이 경우에는 배열을 1회 순회하는 동안 버블정렬이 완료되었지만 1회 순회 했음에도 정렬되지 않는 경우가 있습니다. 다음 배열을 보면 1회 수행했음에도 완벽하게 정렬되지 않습.. 2021. 10. 11. 이전 1 다음 300x250
