정렬 알고리즘3 - 삽입정렬(Insertion Sort)

삽입정렬(Insertion Sort)

출처- 위키백과

작동방식

• 정렬된 데이터 중에 적절한 위치를 찾아 새로운 값을 넣어주는(삽입) 방식

특징

• 앞에서부터 차례대로 정렬된다
• 구현이 간단하다
• 방식이 단순하고 효율적이다.
• 버블정렬, 선택정렬 보다 효율이 좋다.
• 요소가 많을수록 효율이 떨어진다.
• 실시간 정렬이 가능하다. 정렬할 항목이 계속 추가되더라도 적절한 위치를 찾아 삽입하면 되기 때문.
• 어느 정도 정렬되어 있는 것을 완전히 정렬하는데 적합한 방식
  • 반대로 역순으로 된 상태를 재정렬하는 경우 약하다
  • 새로 삽입되는 값이 앞쪽에 위치할수록 한칸씩 밀리는 배열값 개수가 많아지기 때문이다.

 

 

 

[ 2, 17, 8, 3, 15, 9, 4, 6, 13, 7, 1, 5, 11 ] 와 같은 숫자집합이 있을때 아래와 같은 순서로 정렬된다.

 

정렬된 숫자

정렬할 숫자

 

2 17 8 3 15 9 4 6 13 7 1 5 11 
2 8 17 3 15 9 4 6 13 7 1 5 11 
2 3 8 17 15 9 4 6 13 7 1 5 11 
2 3 8 15 17 9 4 6 13 7 1 5 11 
2 3 8 9 15 17 4 6 13 7 1 5 11 
2 3 4 8 9 15 17 6 13 7 1 5 11 
2 3 4 6 8 9 15 17 13 7 1 5 11 
2 3 4 6 8 9 13 15 17 7 1 5 11 
2 3 4 6 7 8 9 13 15 17 1 5 11 
1 2 3 4 6 7 8 9 13 15 17 5 11 
1 2 3 4 5 6 7 8 9 13 15 17 11 
1 2 3 4 5 6 7 8 9 11 13 15 17 

 

 

구현코드 - Java

//오름차순 정렬
public void sort(int[] a){
	int i;      //외부 반복자. 두번째부터 n번째까지 정렬할 값 가져오기
	int j;      //내부 반복자. 정렬된 값을 하나씩 가져와서 i와 비교할 변수
	int value;  //비교할 실제값
	for(i=1; i<a.length; i++){
		
		j = i-1;        //위치값 할당
		value = a[i];   //두번째부터 n번째까지 값을 담는 변수

		/*
		-뒤에 있는 값을 모두 한칸씩 밀어줘야 하기 때문에 while 문 사용
		-배열의 앞에서부터 뒤로 밀면 바로 뒤에 있는 값과 충돌한다
		  때문에 뒤에서부터 한칸씩 밀어주고 배열은 0미만의 값이
         	 허용되지 않기 때문에 (j>=0) 조건을 넣는다
		 */
		//새로 추가할 값이 배열의 j번째보다 작다면 뒤쪽 배열의 값을 뒤로 한칸씩 밀기
		while(j >= 0 && value < a[j]){
			a[j+1] = a[j];	//배열을 한칸씩 뒤로 밀기
			j--;    //배열의 한 칸 앞에 있는 값과 다시 비교하기 위한 코드
		}		
        
		//j+1번째에 새로운 값을 할당하기
		a[j+1] = value;
	}
}

참고로 내림차순으로 정렬하려면 안에 조건식만 변경하면 된다

아래는 배열을 내림차순으로 정렬한 뒤 스트림을 활용해 출력하는 코드이다

public class Test01 {
    public static void main(String[] args) {
        int[] intArr = {2, 17, 8, 3, 15, 9, 4, 6, 13, 7, 1, 5, 11};
        Iterator<Integer> iterator = Arrays.stream(new Test01().sort(intArr)).iterator();
        while(iterator.hasNext()){
            System.out.print(iterator.next()+ " ");
        }
    }

    public int[] sort(int[] intArr){
        int i;
        int j;
        int value;
        for(i=1; i< intArr.length; i++){
            j = i-1;
            value = intArr[i];

            while(j >= 0 && value > intArr[j]){
                intArr[j+1] = intArr[j];
                j--;
            }
            intArr[j+1] = value;
        }
        return intArr;
    }
}