삽입정렬(insert) 알고리즘_자바 구현

평소 알고리즘 공부를 해야지 ~ 해야지 하고 생각하고 있다가.

드디어 정리를 하게 됩니다.

이번에 정리할 알고리즘은 insert, 삽입정렬 알고리즘 입니다.

기본적인 개념은

5,4,3,2,1

위와같은 배열이 존재한다고 할때

5,4,3,2,1

   ↑

두번째 index를 기준으로 

이전 숫자와 대소비교를 합니다.

그래서 자기의 위치를 찾습니다.

step01

4,5,3,2,1

이렇게 정렬이 됩니다.

step02

그다음에는 3부터 시작하게 됩니다.

4,5,3,2,1

      ↑

5가 3보다 크므로 3이 들어갈 위치를 찾습니다.

3과 5비교 하여 정렬을 합니다. 4,3,5,2,1

그리고 3과 4를 비교하여 정렬을 합니다.

결과 3,4,5,2,1

 

이런식으로 for문이 계속 돌게 됩니다.

/**
	 1. 기준을 2번째 index로 잡는다.
	 2. 기준이 되는 값과 바로 이전 값과 비교
	 3. 이전값이 더 크다면 index가 0~이전index의 값과 비교하여 들어갈 자리를 찾는다. 
	 */
class InsertSort {
	Comm comm = new Comm();
	
	void insertSort(int[] testArray){
		int key;
		int i,j;
		
		for(j=1; j< testArray.length; j++){
			key = testArray[j];
			i= j-1;
			while(i>=0 && testArray[i]>key ){ // 바로 이전값이 더 크다면 0~이전index값 비
				testArray[i+1] = testArray[i];
				i = i-1;//index가 0인 자리까지 찾기위해 i-1을 해준다.
			}
			testArray[i+1] = key;
		}
		
	}
	
	


}

실행방법은 main에서 insertSort()함수를 호출하였습니다.

매개변수로 int형 배열을 넘겼습니다.

실행결과 첨부하겠습니다.