삽입 정렬
위키백과 ― 우리 모두의 백과사전.
삽입 정렬은 자료 리스트의 모든 요소를 하나씩 차례로 정렬된 리스트의 부분과 비교하여, 자신의 위치를 찾아 삽입하므로써 정렬을 완성하는 알고리즘이다. 리스트가 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.
목차 |
[편집] 예제
다음의 주어진 리스트의 삽입정렬은 다음과같다.
31 25 12 22 11 //값 31은 나머지 자료값과 비교 11 25 12 22 31 //값 31은 최대값이므로 맨뒤에 위치 11 12 25 22 31 //다음값 25는 12보다 크므로 교환 11 12 22 25 31 //값 25는 22크고 31작으므로 값22와 교환
[편집] C++로 짠 삽입정렬
void insert(const Element e,Element *list,int i) { while(e.getKey()<list[i].getKey()) { list[i+1]=list[i] i--; } list[i+1]=e; }
[편집] JAVA로 짠 삽입정렬
[편집] 복잡도
최악의 경우 i+1번의 비교를 하게되고 이때의 시간복잡도는 이 된다.