[자료구조] 삽입 정렬(Insertion Sort)이란? with JAVA

 

 

 

 

 

 

 

❣️삽입 정렬(Insertion Sort)이란?

선택 정렬과 버블 정렬이 정반대로 착상된 정렬입니다.

삽입 정렬은 이미 정렬된 i개짜리 배열에 현재 비교하고자 하는 값의 위치를 찾아

삽입해 i+1개짜리 배열을 만드는 정렬방법입니다.

 

 

 

삽입 정렬 알고리즘 예제

 

 

삽입 정렬 알고리즘 코드(JAVA)

import java.util.ArrayList;
import java.util.Scanner;

public class InsertionSort {
	
	public static void main(String[] args) {
		
		
		int arr[] = {6,1,3,11,5};
		int n = arr.length;
		
		for (int i=1; i<n; i++) {
			int j = i-1; //0
			int arrResult = arr[i];
			//이 지점에서 arr[0]은 이미 정렬된 상태이다.
			while(0 <= j && arrResult < arr[j]) {
				arr[j+1] = arr[j]; //왼쪽으로 이동
				j --;
			}arr[j+1] = arrResult;
		}
		
		//arr출력
		String []in = {"1번째","2번째","3번재","4번째","5번째"};
		for(int i=0; i<arr.length; i++) {
			System.out.println(in[i]+"\t"+arr[i]);
		}
	}
}

 

- 삽입 정렬은 최악의 경우와 평균적인 경우에 O(n^2)의 시간이 들고, 최선의 경우에는 O(n) 시간이 듭니다.

- 삽입 정렬은 선택 정렬이나 버블 정렬보다 빠릅니다. 귀납법의 원리가 그대로 나타나 있습니다.
- 정렬은 데이터의 크기에 따라 속도가 느려질 수도, 빨라질 수도 있습니다.

 

 

 

 

 

참조 - 쉽게 배우는 자료구조 with 자바