[TIL]삽입 정렬 Insertion Sort

1. 삽입 정렬(Insertion Sort)란?

- 배열의 모든 요소를, 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

2. 알고리즘 흐름

- 첫 Key 값은 배열의 두번째 요소부터 시작한다.

 

3. 문제 풀이

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

입력

인자 1 : arr

• int 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr.length는 1,000 이하

출력

• int 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 삽입 정렬을 구현해야 합니다.
• Arrays.sort() 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

int[] output = insertionSort(new int[]{3, 1, 21})
System.out.println(output); // --> [1, 3, 21]

 

 

4. 구현 코드

public class Daily36 {
    public int[] insertionSort(int[] arr) {
        // TODO:


        for(int i=1;i<arr.length;i++){
            for(int j=i-1;j>=0;j--){
                if(arr[j+1]<arr[j]){
                    int tmp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j]=tmp;
                }
                else break;

            }
        }
        return arr;
    }
}