자료구조 - 삽입 정렬

삽입 정렬이란 배열의 두 번째 인덱스부터 시작하여 그 앞의 인덱스가 클 경우 그 인덱스가 위치한 곳에 삽입하여 정렬하는 방식이다.

 

 

정렬 과정을 보면 다음과 같다.

 

 

 

 

▼삽입 정렬 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void InsertionSort(int arr[], int n)
	{
		int i,j;
		int data=0;
		
		for(i=1;i<n;i++)
		{
			data = arr[i];
			for(j=i-1;j>=0;j--)
			{
				if(arr[j]>data)
				{
					arr[j+1]=arr[j];
					arr[j]=data;
				}
				else
					break;
			}
		}
	}
	
	public static void main(String[] args){
		int arr[] = {5, 2, 6, 3, 1, 4};
		
		InsertionSort(arr,6);
		
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
	}
}

 

결과

1 2 3 4 5 6