[알고리즘/정렬 알고리즘] 삽입 정렬 (Insertion sort) Java, Python

삽입 정렬(Insertion sort) 알고리즘의 개념

• (오름 차순 기준) 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘이다.
• 선택 정렬과 비슷하게 보이지만 삽입 정렬은 해당 값을 가져와 알맞은 위치에 옮긴다는 점이 다르다.

삽입 정렬(Insertion sort) 예제

• 배열에 6, 4, 1, 7, 3 순으로 값이 들어가 있고 오름차순으로 정렬할 때의 삽입 정렬 예를 확인해보자

• 위와 같이 정렬을 하지 않은 부분의 첫 번째 요소를 가져와 정렬을 마친 부분의 적절한 위치를 찾아 옮기는 알고리즘이 삽입 알고리즘이다.

 

[Java 코드]

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {6, 4, 1, 7, 3};
        int temp = 0;
        int N = arr.length;
        
        for(int i = 1; i < N; i++) {
            temp = arr[i];
            int j;
            
            for(j = i-1; j >= 0 && arr[j] > temp; j--) {
                arr[j+1] = arr[j];
            }
            
            arr[j+1] = temp;
        }
        
        for(int a : arr) {
            System.out.print(a+" ");
        }
    }
} 

 

[Python 코드]

def insertion_sort(arr):
    N = len(arr)
 
    for i in range(1, N):
        for j in range(i, 0, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            else:
                break
    print(arr)
 
 
arr = [6, 4, 1, 7, 3]
insertion_sort(arr)