삽입 정렬,합병정렬

삽입정렬

 

삽입 정렬은 이미 정렬된 수열에 대해서 새로운 원소를 삽입하는 정렬이다.즉,두 번째 인덱스부터 시작해서 다음 인덱스로 이동하고 해당 인덱스와 비교하면서 옳바른 자리에 삽입한다.이를 그림으로 나타내면 다음과 같다.

삽입 정렬 예시

그리고 이를 의사 코드로 나타내면 다음과 같다.

삽입 정렬 의사코드

 

시간 복잡도는 $O(n^2)$이다.이는 삽입된 원소가 역순일 경우로 최선의 경우에서는 O(n)이 된다.

합병정렬

이 정렬은 이미 공부했기에 링크만 올려둔다.

https://kshdevstory.tistory.com/119