[자료구조][정렬 알고리즘]삽입 정렬(Insertion Sort)

삽입 정렬은 선택 정렬과 함께 가장 많이 사용되는 정렬 방법이자 아주 간단한 정렬 방법입니다. 

선택 정렬이 많은 비교와 적은 교환으로 특징지워진다면 삽입 정렬은 반대로 적은 비교와 많은 교환이 특징입니다.

출처: https://www.youtube.com/watch?v=ROalU379l3U

 

위 동영상은 삽입 정렬을 춤으로 표현한 영상으로 함께 보시면 조금이 나마 이해가 가실 겁니다.

삽입 정렬을 java 코드로 구현해 보았습니다.

 

 

코드를 간략히 설명  드리자면, 

우선 위의 함수는 숫자형 배열을 받는 함수로

arr = {20, 1, 35, 23, 5, 6}  이 들어왔다 가정하겠습니다.

첫 번째 for문에서 인덱스가 0이 아닌 1 , 즉 배열의 두 번째 요소부터 정렬이 시작됩니다. 

temp라는 변수에 arr [i]의 값인 1이 들어가게 됩니다.(30라인)

그리고 두번째 for문을 돌면서 temp의 앞에 있는 값들과 비교를 하게 됩니다.

처음의 경우 temp = 1 , arr [j]=20 이므로

32라인에 있는 if문을 거치지 않고 다음 행으로 진행하여

arr [j+1]인arr [j] 값인 20 이 들어가게 됩니다.

여기까지의 배열 상태를 보자면

{20, 20, 35, 23, 5, 6}이 되는 겁니다.

이후 j--가 되므로 j = -1이 되고 그러므로 두 번째 for문은 끝나게 됩니다.

두번째 for문이 끝나면 37라인이 실행되는데,

arr [-1+1] 이므로 arr [0] 위치에 temp값인 1이 들어가게 되어

{1, 20, 35, 23, 5, 6}이 됩니다.

이와 같은 과정을 반복하면 아래와 같은 순서로 배열이 정렬됩니다.

 

 

※ 필자는 아직 배울 것이 많은 초보 개발자입니다. 잘못된 부분이나 고쳤으면 하는 부분은 댓글을 통해 알려주시면 감사하겠습니다.
도움이 되셨다면 밑에 공감 버튼 부탁드리겠습니다.