삽입 정렬(Insertion Sort) (C++)

삽입 정렬은 적절한 위치에 삽입는 정렬이다.

앞에서부터 두 숫자를 비교하면서 정렬하고 정렬된 숫자에서 알맞는 자리를 찾아 숫자를 삽입하는 정렬이다. 자리를 찾아가는 방법은 바로 앞 숫자와 비교하여 자기보다 작은 숫자가 나올때까지 자리를 바꿔가는 것이다.

 

조심해야할 것은 j가 0보다 작아지지않게 j-1 과 j가 아니라  j 와 j+1을 비교하는 것이고,

while 문 안에서 j>=0조건을 달아주고 j--를 하는 것은 생각해내기 쉽지 않았을 것 같다.

#include <iostream>

using namespace std;

int main(){
    int i, j,tmp;
    int array[10]={1,10,5,8,7,6,4,3,2,9};
    
    for(int i=0;i<9;i++){
       j=i;
       while(j>=0 && array[j]>array[j+1]){
           tmp=array[j];
           array[j]=array[j+1];
           array[j+1]=tmp;
           j--;
       }
    }
   
    for(int i=0;i<10;i++){
        cout<<array[i]<<" ";
    }
    return 0;
}

 

<참조>

blog.naver.com/ndb796/221226806398

4. 삽입 정렬(Insertion Sort)