day04-과제)삽입정렬

• Isertion Sort [삽입정렬]

 

삽입정렬이란 현재 비교하고자 하는 타겟과 이전의 원소들을 비교하여 자리를 교환하는 정렬 방법이다.

삽입 정렬은 데이터를 비교하면서 찾는 '비교정렬'이며, 버블 정렬과 마찬가지로 정렬의 대상이 되는 데이터 외에  추가적인 공간이 필요하지 않기 때문에 '제자리정렬'이기도 하다 

---

• 삽입 정렬의 과정(오름차순 기준 설명)

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다.(두 번째 원소부터 타겟 시작)

2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.

3. 그 다음 타겟을 찾아 위와 같은 방법으로 n-1회 반복한다.

 

---

• 삽입정렬 구현하기

package homework;

import java.util.Random;
import java.util.Scanner;

public class InsertionSort {

	public static void main(String[] args) {
    	//======랜덤 숫자 배열생성=========
		Random rand = new Random();
		int[] data = new int[10];
		for (int i = 0; i < data.length; i++) {
			//10개 정수 데이터 랜덤으로 생성
			data[i]=rand.nextInt(10)+1;
		}
		System.out.print("[");
		for(int v:data) {
			System.out.print(v+" ");
		}
		System.out.println("]");
		
		//======삽입 정렬 알고리즘=========
        
		for(int i = 1; i < data.length; i++) {
			int target = data[i];// 타겟 넘버		
			int j = i - 1;
			
			
			while(j >= 0 && target < data[j]) {
				//index가 0이상이여야하고,타겟이 이전 원소보다 크기 전 까지 반복 
				data[j + 1] = data[j];	// 이전 원소를 한 칸씩 뒤로 미룬다.
				j--;
			}
			
			/*
			 위 반복문에서 탈출 하는 경우 앞의 원소가 타겟보다 작다는 의미이므로
			 타겟 원소는 j번째 원소 뒤에 와야한다.
			 그러므로 타겟은 j + 1 에 위치하게 된다.
			 */
			data[j + 1] = target;	
		}
		
        //======삽입정렬후 배열=========
		System.out.print("[");
		for(int v:data) {
			System.out.print(v+" ");
		}
		System.out.print("]");
		
	}

}

/*콘솔값
[4 8 5 1 8 7 4 10 5 9 ]
[1 4 4 5 5 7 8 8 9 10 ]*/

참조 블로그

https://st-lab.tistory.com/179

자바 [JAVA] - 삽입 정렬 (Insertion Sort)