재밌고 어려운 IT를 이해해보자~!
삽입정렬 코드 실행 본문
삽입정렬 코드 작성 후 디버깅표를 만들어보자.
package day006;
public class sortedarray {
public static void main(String[] args) {
int[] arr = new int[5];
arr[0] = 100;
arr[1] = 5;
arr[2] = 60;
arr[3] = 1000;
arr[4] = 30;
for (int i = 1; i < arr.length; i++) {
int pivot = arr[i]; // 기준값
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > pivot) {
arr[j + 1] = arr[j];
arr[j] = pivot;
}
}
}
for (int datas : arr) {
System.out.print(datas + " ");
}
}
}
디버깅 표
4회전 후에 정렬이 완료된다!
삽입정렬은 안정정렬인데 안전정렬 이라는 뜻은 중복된 값이 있을때 서로의 위치가 바뀌지 않는 정렬이다.
정렬에 따라 같은 값이더라도 자리가 바뀔 수 있다.
언뜻보면 삽입정렬은 버블정렬의 반대형태를 띄우는 것 같다. 하지만 교환이 이루어지는 버블정렬과 달리 삽입정렬은
추가적인 temporary 공간을 생성 할 필요없이 정렬이 가능하다.
버블정렬 : 일단 제일 앞 녀석 데리고 뒤로 가는 것이다. 차례로 비교해나가다가, 더 큰 녀석이 있으면 더 큰 녀석을 뒤로 데리고 간다. 그러면 제일 뒤에는 제일 큰 녀석이 서겠죠. 이런 식으로 계속 하면 정렬이 되며 비교를하고 바꿀때마다 temp공간을 만들어 교환을 해준다.
삽입정렬 : 처음부터 pivot까지 봐서, 제일 작은 녀석을 제일 앞 자리와 바꾼다. 두번째로 볼 때는 나머지에서 가장 작은 사람과 두 번째 녀석이랑 바꾸는식으로 해서 가장 작은숫자가 앞으로 오게된다. 새로운공간을 만들어 교환하는것이 아닌 pivot부터 처음까지 쭈우욱 비교해보다가 pivot이 들어갈 위치가 맞으면 삽입! -> temp공간 필요하지 않다.
'코리아IT핀테크과정' 카테고리의 다른 글
선택정렬 코드 실행 (0) | 2023.11.29 |
---|---|
함수를 활용한 학생부 프로그램 리팩토링(Refactoring) (2) | 2023.11.28 |
함수(Function) (0) | 2023.11.27 |
버블정렬 코드 개선 (0) | 2023.11.27 |
이진 탐색(Binary Search) (2) | 2023.11.26 |
Comments