Insert Sort / Bubble Sort

---

1. Insertion Sort

Space - Complexity = In - Place Sort : O(1)의 보조 메모리를 사용한다. Time - Complexity = O(n^2)

원리

n개의 원소를 가진 배열을 정렬할 때, i번째를 정렬 순서라고 가정하면,0부터 i-1까지의 원소들은 정렬되어있다는 가정하에, i번째 원소롸 i-1 번째 원소부터 0번째 원소까지 비교하면서 i번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서(i+1)의 원소와 비교하면서 정렬해준다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복해준다.

C code ` void insertion_sort(int*arr,int size){ int temp; int j;

for(int i = 1;i < size; i++){ temp = arr[i]; for(j = 1-1; j >=0; j--){ if(temp < arr[j]){ arr[j + 1] = arr[j]; }else{ break; } } arr[j + 1] = temp; } } `

2. Bubble Sort

Space - Complexity = In-place Sort:O(1)의 보조 메모리를 사용한다. Time - Complexity = O(n^2)

원리

인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 가장 큰 값을 배열의 맨 끝에다 이동시키면서 n번을 두 번 반복하게 된다.

C Code ` void bubble_sort(int*arr, int size){ for(int j = 0; j < size -1; j++){ for(int i = 0; i < (size-j)-1;i++){ if(arr[i] > arr[i+1]){ swapValue(&arr[i], &arr[i+1}); } } } }

//util - swap void swapValue(int *a,int *b){ int temp = *a; *a = *b; *b = temp; } ` 자바코드로 짜보자!