티스토리 뷰
삽입 정렬(Insertion Sort) - C언어/자료구조
Prosto 2016.10.19 23:59
'맞는 위치에 삽입시켜가며 정렬하는 삽입정렬'
삽입정렬은 Insertion Sort라고도 부르며 데이터 정렬 방법 중 하나입니다.
키(key) 값을 가지고 정렬시키는 삽입 정렬은 두 번째 자료부터 시작하여
그 앞의 자료들과 비교하여 알맞은 위치로 삽입하는 형태의 정렬입니다.
(배열로 보는 경우 삽입이라면 뒤의 자료들은 한 칸씩 밀리는 형태가 되겠죠?)
(아래 데이터 이동 그림을 보시면 이해하시기 더 좋을 것이라 생각됩니다.)
여러 회전을 반복하여 정렬하는 방법입니다.
첫 번째 회전에서는
두 번째 자료를 키 값으로 가지고 앞의 자료들을 하나씩 비교합니다.
두 번째 자료의 앞 자료는 첫 번째 자료 하나밖에 없으니 하나만 확인하면 됩니다.
첫 번째 자료가 키 값보다 크다면 두 번째 자료를 첫 번째 자료로 바꿔줍니다.
(작다면 바꿀 필요 없이 그대로 두면 되겠죠?)
더 이상 비교할 대상이 없으니 첫 번째 자료 위치에 키 값을 넣어줍니다.
두 번째 회전에서는
세 번째 자료를 키 값으로 가지고 앞의 자료들을 하나씩 비교합니다.
세 번째 자료의 앞 자료는 두 번째, 첫 번째 자료 두 개가 있죠?
두 번째 자료가 키 값보다 크다면 세 번째 자료를 두 번째 자료로 바꿔줍니다.
(작다면 바꿀 필요 없이 그대로 검사를 종료하고 그대로 위치합니다.)
다음으로 첫 번째 자료와 키 값을 비교합니다.
첫 번째 자료가 더 크다면 두 번째 자리에 첫 번째 자료를 넣어줍니다.
(작다면 바꿀 필요 없이 그대로 검사를 종료하고, 키 값을 두 번째 자리에 위치시켜주면 되겠죠?)
더 이상 비교할 대상이 없으니 첫 번째 자료 위치에 키 값을 넣어줍니다.
세 번째, 네 번째 회전 모두 앞의 회전과 같은 방식으로 진행됩니다.
5개라면 4 회전, 10개 라면 9회전 n-1회전 만큼 진행됩니다.
실제로 5개의 숫자 배열 자료가 어떻게 정렬되는지 확인해볼까요?
7, 4, 10, 3, 5 다섯 숫자를 가지고
삽입정렬 하는 과정을 보도록 하겠습니다.
1 회전
가장 먼저 두 번째 자리의 4를 키 값으로 가지고 앞의 자리를 비교합니다.
앞의 자리는 첫 째 자리 하나밖에 없죠?
비교 결과 키 값인 4가 첫 째 자리의 7보다 작기 때문에
첫 째 자리의 7은 두 번째 자리로 이동하고
키 값은 더 이상 비교 대상이 없기 때문에 남은 자리(첫 째 자리)로 들어갑니다.
2 회전
두 번째 회전에서의 키 값은 세 번째 자리의 10이 됩니다.
그리고 바로 앞의 자리인 두 번째 자리의 7과 비교합니다.
비교 결과 키 값인 10보다 두 번째 자리의 7이 더 작기 때문에
현재 위치로 키 값의 자리가 결정됩니다.
3 회전
세 번째 회전에서의 키 값은 네 번째 자리의 3이 됩니다.
그리고 바로 앞의 자리인 세 번째 자리의 10과 비교합니다.
비교 결과 키 값인 3보다 세 번째 자리의 3이 더 크기 떄문에
네 번째 자리에 10을 넣어줍니다.
(아직 3의 자리는 확정되지 않았죠? 더 비교해야 합니다.)
편의상 교환이라고 적어뒀지만 실제로는 교환이 아니라 이 전의 값이 들어있습니다.
실제로 데이터를 비교하여 작은 값을 만나 확정되면 그 자리에 들어갑니다.
다음으로 키 값인 3과 두 번째 자리의 7을 비교합니다.
비교 결과 키 값인 3보다 두 번째 자리의 7이 더 크기 때문에
세 번째 자리에 7을 넣어줍니다.
(작은 값을 만나거나 마지막 자리 검사할 때까지 계속 검사는 이어집니다.)
다음으로 키 값인 3과 첫 번째 자리의 4를 비교합니다.
비교 결과 키 값인 3보다 첫 번째 자리의 4가 더 크기 때문에
두 번째 자리에 4를 넣어줍니다.
그리고 첫 번째 자리까지 시작 지점으로부터 모든 앞 자리를 모두 검사했기 때문에
검사를 종료하고 해당 위치에 키 값인 3을 넣어줍니다.
4 회전
5개 배열에서의 마지막 회전으로 키 값은 다섯 번째 자리의 5입니다.
키 값인 5와 바로 앞의 자리인 네 번째 자리의 10을 비교합니다.
비교 결과 키 값인 5보다 네 번째 자리의 10이 더 크기 때문에
다섯 번째 자리에 10을 넣어줍니다.
다음으로 키 값인 5와 세 번째 자리의 7을 비교합니다.
비교 결과 키 값인 5보다 세 번째 자리의 7이 더 크기 때문에
네 번째 자리에 7을 넣어줍니다.
다음으로 키 값인 5와 두 번째 자리의 4를 비교합니다.
비교 결과 키 값인 5보다 두 번째 자리의 4가 더 작기 때문에
4의 위치는 그대로이며 키 값의 위치가 결정되었습니다.
이렇게 삽입 정렬은 시작 지점부터 앞으로 하나씩 검사하며
자신이 지정한 조건이 만족할 때까지 반복됩니다.
정렬들은 조건 부분을 알맞게 바꿔주면 오름차순, 내림차순 모두 가능하겠죠?
그럼 이번에는 C 프로그램으로 삽입 정렬을 확인해볼까요?
(소스는 제공하지만, 위의 과정을 보고 직접 만들어 보시면 좋을 것 같네요.)
출력 결과 예를 보고
프로그램의 소스를 작성해보세요.
(출력 결과 예)
제가 완성한 소스입니다.
보고 참고하세요.
(복사할 수 있는 소스는 아래 전체복사용소스보기를 누르시면 됩니다.)
전체복사용소스보기
궁금한 점 있으시면 댓글이나 따로 메일로 질문하시면 시간되는 대로 답변드리겠습니다. ( 연락 )
출처: http://prosto.tistory.com/163 [Prosto]