[삽입정렬]
public void sort(int[] input){
public class Input {
public static void main(String[] args) {
int []input = {15,42,45,9,2,55,23,6};
for(int i = 1 ; i<input.length; i++) {
int side = i-1;
int standard = input[i];
while(side>=0 && standard <input[side]) {
input[side+1] = input[side];
side--;
}
input[side+1]= standard;
}
for(Integer br :input) {
System.out.println(br);
}
}
}
삽입정렬은 Θ(n^2) 시간 복잡도를 갖는다.
그러나 이미 정렬이 되어 있는 경우는 한번씩 밖에 비교하지 않기 때문에 O(n) 이다.
삽입 정렬은 0번째부터가 아닌 1번째부터 이하로 데이터를 정렬한다.
기준이 되는 수를 임시변수에 넣고 기준수와 -1해서 하나씩 비교한다.
삽입되는 변수가 더 클경우 +1해서 데이터를 삽입한다.
package bubbleSort;
public class InputSort {
public static void main(String[] args) {
int i, j, temp;
int[] ar = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
// 삽입정렬은 적절한 위치에 삽압하는 것입니다.
// 앞에 있는 원소들이 정렬이 되어있다는 가정을 가지고 있습니다.
for (i = 0; i < ar.length-1; i++) {
j = i;
while (ar[j] > ar[j + 1]) {
temp = ar[j];
ar[j] = ar[j + 1];
ar[j + 1] = temp;
j--;
}
}
for(int outView : ar) {
System.out.println(outView);
}
}
}