정렬알고리즘

삽입정렬

삽입정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결한다. 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 때만 위치를 바꾼다.
버블,선택정렬보다 빠르게 작동한다.

주요알고리즘

for (int i = 1; i < arr.length; i++) {
			int key = arr[i]; //기준
			int aux = i - 1; // 비교할 대상의 인덱스 
			while (aux >= 0 && key < arr[aux]) 
			{
				arr[aux + 1] = arr[aux];
				aux--;
			}
		arr[aux+1] = key;  //기준값저장
		}

class InsertionSort {
	int [] arr;
	private int arrSize;

	
	// 배열 사이즈 get,set
	public int getArrSize() {
		return arrSize;
	}

	public void setArrSize(int arrSize) {
		this.arrSize = arrSize;
	}


	// 정렬메서드
	public int[] solution(int n, int[]arr) {
		this.arr = arr;
		this.arrSize = n;
		
		for (int i = 1; i < arr.length; i++) {
			
			int key = arr[i]; //기준
			int aux = i - 1; // 비교할 대상의 인덱스
			
			while (aux >= 0 && key < arr[aux]) 
			{
				arr[aux + 1] = arr[aux];
				aux--;
			}
		arr[aux+1] = key;  //기준값저장
		}
		
		return arr;			
	}
}

public class InsertionSortTest {

	public static void main(String[] args) {
		InsertionSort sort = new InsertionSort();

		Scanner sc = new Scanner(System.in);

		// 배열의 길이를 입력 받고 선언한다.
		System.out.println("배열의 길이를 입력하세요: ");
		sort.setArrSize(sc.nextInt());

		int[] arr = new int[sort.getArrSize()];

		// for문: 숫자 입력,배열에 값 넣기를 반복
		for (int i = 0; i < arr.length; i++) {
			System.out.println("배열에 넣을 정수를 입력하시오: ");
			arr[i] = sc.nextInt();
		}
		// 정렬 메서드 실행
		sort.solution(sort.getArrSize(), arr);
		// 배열을 출력한다.
		System.out.println(Arrays.toString(arr));

	}

}