삽입정렬(Insertion Sort)
삽입정렬(Insertion Sort)는 이미 정렬되어 있는 i 개 짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개 짜리 배열을 만드는 과정을 반복한다. 선택정렬(Selection Sort)과 버블정렬(Bubble Sort)이 n개짜리 배열로부터 시작하여 그 크기를 하나씩 줄여나가는데 반하여, 삽입정렬은 1개짜리 배열로부터 시작하여 그 크기를 하나씩 늘려가는 정렬이다. 위의 예제를 살펴보면 배열 A[]에서 루프문을 통해 i가 두번째 원소 부터 배열의 끝 원소까지 루프문을 돌면서 A[i]번째의 원소를 자리에 알맞게 넣는다. i가 두번째 원소를 가리킬때 A[2]인 10의 자리는 A[1]인 29와 위치가 바껴야 하므로 자리가 교체된다. i가 세번째 원소를 가르킬때 A[3]인 14의 위치는 A[1]인 10 ..
프로그래밍/자료구조&알고리즘
2014. 4. 22. 21:08