프로그래밍/코딩테스트

[정렬] 삽입정렬(Insertion Sort)

코드몬스터 2023. 7. 28. 13:10
728x90
💡 해당 글은 여기 블로그 를 참고하여 작성했습니다.

 

 

👉 특징

  • 해당 배열 안에서 교환하는 방식으로, 다른 메모리 공간이 필요하지 않다. ⇒ 제자리 정렬(in-place sorting)

 

👉 나만의 코드 해석

해당 코드에서 중요하다고 생각 되는 변수는 prev 이다.

 

Process

  1. 두 개의 인덱스 값을 기준으로 움직안다.
    • prev, index 
  2. for 문의 index 값을 기준으로 이전 값들을 비교한다.
    • int temp = arr[index];
    • arr[prev] > temp
  3. 만약, 이전 값(prev)이 큰 경우에는 prev + 1 의 인덱스 위치에 prev 인덱스의 값을 넣어준다.
    • arr[prev + 1] = arr[prev];
  4. 그리고 prev--; 를 해줘서 한 칸 이전으로 움직인다.
  5. 마지막으로 prev + 1의 인덱스 위치에 처음 비교 기준이 되었던  temp 값을 넣어준다.

 

import java.util.*;
class Solution {
    public int[] solution(int[] arr) {
        
        int[] test = {1, 2, 3, 4};

        for(int index = 1 ; index < arr.length ; index++){
            int temp = arr[index];
            int prev = index - 1;
            while( (prev >= 0) && (arr[prev] > temp) ) {
                arr[prev+1] = arr[prev];        // 3 번
                prev--;	// 4 번
            }
            arr[prev + 1] = temp;	// 5 번
            
        }
            
        return test;
    }
}

 

 

결국은 다른 사람의 코드이기 때문에 코드를 보고 이해하려고 노력하지 않으면 내 것이 되기 어렵다고 생각한다!