반응형
삽입 정렬
삽입 정렬은 아래의 알고리즘을 따릅니다.
{8, 2, 1, 4, 5} 형태의 배열을 정렬해보는 예제입니다.
두번째 인덱스인 1의 데이터를 하위 인덱스 0까지 비교합니다.
비교하는 하위 인덱스의 값이 임시 temp값보다 작을때까지 비교하고 작지 않다면 다음 인덱스로 넘깁니다.
arr[i+1] = arr[i];
이 행동으로 배열 끝까지 진행합니다.
처음 큰 한바퀴가 진행되면 위 그림의 순서대로 정렬이 진행됩니다.
다음은 기준 인덱스가 하나 증가하여 2번째 인덱스를 0~1번째 인덱스까지 비교하고 정렬합니다.
다음은 기준 인덱스가 하나 증가하여 3번째 인덱스부터 하위 인덱스까지 비교합니다.
다음은 기준 인덱스가 하나 증가하여 4번째 인덱스부터 하위 인덱스까지 비교합니다.
정렬이 끝나면 아래와 같이 1,2,4,5,8의 형태로 배열이 정리가 됩니다.
JAVA Source
public class Sorting2 {
public static void main(String[] args) {
int[] arr = {8, 2, 1, 4, 5};
if(arr.length > 1) {
int i, j;
for(i=1; i<arr.length; i++) {
int tmp = arr[i];
for(j=i-1; j>=0; j--) {
arr[j+1] = arr[j];
if(tmp > arr[j]) {
break;
}
}
arr[j+1] = tmp;
}
}
for(int i=0; i<arr.length; i++) {
System.out.print(arr[i]);
if(i+1 != arr.length) {
System.out.print(", ");
}
}
}
}
반응형
'JAVA' 카테고리의 다른 글
Netty - Netty Client 튜토리얼 - 01 (0) | 2020.11.27 |
---|---|
JAVA - 문자열에 숫자만 존재하는지 확인하기 (2) | 2020.11.19 |
JAVA - 정렬 알고리즘 선택정렬 (배열 내림차순, 오름차순 정렬) (0) | 2020.09.03 |
JAVA - Socket server 문자열 받기 개선(br.readLine 대신 read사용) (4) | 2020.06.23 |
JAVA - String, StringBuffer, StringBuilder 알고 쓰기 (0) | 2020.06.12 |