#include <stdio.h>
int binary_search(int* arr,int len, int key)
{
int start = 0, mid = 0, end = len;
while(start <= end){
mid = (start + end)/2;
if(arr[mid] == key){
return mid;
}else if(arr[mid] < key){
start = mid + 1;
}else{
end = mid - 1;
}
}
return start;
}
int binary_search_re(int* arr, int start, int end, int key)
{
if(start > end)
return start;
int mid = (start + end) / 2;
if(arr[mid] == key){
return mid;
}else if(arr[mid] < key){
return binary_search_re(arr, mid + 1, end, key);
}else{
return binary_search_re(arr,start, mid-1 , key);
}
}
int bsort(int* arr, int len, int flag_re)
{
int i = 0,j = 0, k = 0, act_pos = 0, key = 0;
printf("input arr list: ");
for(i = 0; i < len; i++){
printf("= ", arr[i]);
}
printf("\n");
i = 0;
for(i = 1; i < len; i++){
key = arr[i];
if(flag_re){
act_pos = binary_search_re(arr, 0, i, key);
}else{
act_pos = binary_search(arr, i, key);
}
for(j = i; j > act_pos; j--){
int tmp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = tmp;
}
arr[act_pos] = key;
printf("sort num index(-) act_pos(%d):", i, act_pos);
for(k = 0; k < len; k++){
printf("= ", arr[k]);
}
printf("\n");
}
return 0;
}
int main(int argc, char** argv)
{
int i = 0;
int array[21] = {30, 11, 71, 15, 9, 31, 12, 24, 18,10, 3,13, 14,33,80, 47,8,5,6,26};
int array1[21] = {30, 11, 71, 15, 9, 31, 12, 24, 18,10, 3,13, 14,33,80, 47,8,5,6,26};
bsort(array, 20, 0);
for(i = 0; i<20; i++){
printf("= ", array[i]);
}
printf("\n");
bsort(array1, 20, 1);
for(i = 0; i<20; i++){
printf("= ", array1[i]);
}
printf("\n");
return 0;
}
