프로그래밍/코딩테스트
[정렬] 삽입정렬(Insertion Sort)
코드몬스터
2023. 7. 28. 13:10
728x90
💡 해당 글은 여기 블로그 를 참고하여 작성했습니다.
👉 특징
- 해당 배열 안에서 교환하는 방식으로, 다른 메모리 공간이 필요하지 않다. ⇒ 제자리 정렬(in-place sorting)
👉 나만의 코드 해석
해당 코드에서 중요하다고 생각 되는 변수는 prev 이다.
Process
- 두 개의 인덱스 값을 기준으로 움직안다.
- prev, index
- for 문의 index 값을 기준으로 이전 값들을 비교한다.
- int temp = arr[index];
- arr[prev] > temp
- 만약, 이전 값(prev)이 큰 경우에는 prev + 1 의 인덱스 위치에 prev 인덱스의 값을 넣어준다.
- arr[prev + 1] = arr[prev];
- 그리고 prev--; 를 해줘서 한 칸 이전으로 움직인다.
- 마지막으로 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;
}
}
결국은 다른 사람의 코드이기 때문에 코드를 보고 이해하려고 노력하지 않으면 내 것이 되기 어렵다고 생각한다!