Just Review and Record ….
******************************************************
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <ctime>
#include <sys/time.h>
#include <algorithm>
using namespace std;
#define MAX 1000
#define SWAP(X,Y) {int t;t=X;X=Y;Y=t;}
void show_ary(int ary[], int size)
{
int i = 0;
printf("ary[]: ");
for(i; i< MAX; i++){
printf("%d ", ary[i]);
}
return;
}
typedef enum SORT_TYPE_E
{
SORT_SELECT = 0,
SORT_INSERT,
SORT_BIBLE,
SORT_SEHLL,
SORT_QUICK,
SORT_MERGE,
SORT_CPP,
SORT_ALL
}SORT_TYPE_T;
typedef enum SEARCH_TYPE_E
{
SEARCH_LINEAR = 0,
SEARCH_BINARY,
}SEARCH_TYPE_T;
typedef enum FEATURE_TYPE_E
{
FEATURE_FIBONACCI = 0,
FEATURE_EUCLIDEAN,
}FEATURE_TYPE_T;
void sort_select(int ary[], int size)
{
int i;
int j;
for(i=0; i<size-1; i++)
{
for(j=i+1; j<size; j++)
{
if(ary[i] > ary[j])
{
SWAP(ary[i], ary[j]);
}
}
}
return;
}
void sort_insert(int ary[], int ary_size)
{
int i, j;
int n = ary_size;
for(i=1; i<n; i++)
{
j = i;
while(j>0 && ary[j-1] > ary[j])
{
SWAP(ary[j],ary[j-1]);
j--;
}
}
return;
}
int fibonacci_fun(int n)
{
if(n==1 ||n==2)
{
return 1;
}
else
{
return fibonacci_fun(n-1) + fibonacci_fun(n-2);
}
}
int linear_search(int ary[], int ary_size, int target_num)
{
int i = 0;
while(i<ary_size)
{
if(ary[i] == target_num)
{
return i;
}
i++;
}
return -1;
}
int binary_search(int ary[], int ary_size, int target_num)
{
int ret = -1;
int left = 0;
int right = ary_size - 1;
int mid;
while(left < right)
{
mid = (left+right)/2;
if(ary[mid] < target_num)
{
left = mid+1;
}
else if (ary[mid] > target_num)
{
right = mid-1;
}
else
{
ret = mid;
return ret;
}
}
return ret;
}
int main(int argc, char *argv[])
{
srand(time(NULL));
// generate (1-100) 10 number in a array
int ary[MAX] = {0};
int i = 0;
for(i=0; i<MAX; i++){
ary[i] = rand()%200 + 1;
}
show_ary(ary, MAX);
int search_num = ary[77];
printf("\r\nTarget num: %d \r\n", search_num);
cout << "\r\nType Sort Type (0-6): " << endl;
SORT_TYPE_T sort_type;
//cin >> sort_type;
scanf("%d", &sort_type);
switch(sort_type)
{
case SORT_SELECT:
{
struct timeval start;
struct timeval end;
unsigned long timer;
gettimeofday(&start, NULL);
printf("Choose SORT_SELECT \r\n");
sort_select(ary, MAX);
printf("After SORT_SELECT ...... \r\n");
show_ary(ary, MAX);
gettimeofday(&end, NULL);
timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
printf("\r\nSORT_SELECT timer = %ld us\n", timer);
}
break;
case SORT_CPP:
{
struct timeval start;
struct timeval finish;
unsigned long timer;
gettimeofday(&start, NULL);
cout << "Choose SORT_CPP" << endl;
sort(begin(ary), end(ary), less<int>());
//sort(begin(ary), end(ary), greater<int>());
cout << "After SORT_CPP ...... " << endl;
show_ary(ary, MAX);
gettimeofday(&finish, NULL);
timer = 1000000 * (finish.tv_sec - start.tv_sec) + finish.tv_usec - start.tv_usec;
printf("\r\nSORT_CPP timer = %ld us\n", timer);
}
break;
case SORT_INSERT:
{
struct timeval start;
struct timeval finish;
unsigned long timer;
gettimeofday(&start, NULL);
cout << "Choose SORT_INSERT" << endl;
sort_insert(ary, MAX);
cout << "After SORT_INSERT ...... " << endl;
show_ary(ary, MAX);
gettimeofday(&finish, NULL);
timer = 1000000 * (finish.tv_sec - start.tv_sec) + finish.tv_usec - start.tv_usec;
printf("\r\nSORT_INSERT timer = %ld us\n", timer);
}
break;
case SORT_QUICK:
{
struct timeval start;
struct timeval finish;
unsigned long timer;
gettimeofday(&start, NULL);
cout << "Choose SORT_QUICK" << endl;
sort_quick(ary, MAX);
cout << "After SORT_QUICK ...... " << endl;
show_ary(ary, MAX);
gettimeofday(&finish, NULL);
timer = 1000000 * (finish.tv_sec - start.tv_sec) + finish.tv_usec - start.tv_usec;
printf("\r\SORT_QUICK timer = %ld us\n", timer);
}
break;
default:
{
//show_usage();
}
break;
}
cout << "\r\n===== Type Search type (0-1): ";
SEARCH_TYPE_T search_type;
scanf("%d", &search_type);
switch(search_type)
{
case SEARCH_LINEAR:
{
cout << "Linear Searching ... " << endl;
struct timeval start;
struct timeval end;
unsigned long timer;
gettimeofday(&start, NULL);
// int search_num = ary[77];
// printf("Target num: %d \r\n", search_num);
int ret;
ret = linear_search(ary, MAX, search_num);
if(ret != -1)
{
printf("Get the number in ary index: %d \r\n", ret);
}
else
{
printf("Can not Found in arrray!!! \r\n");
}
gettimeofday(&end, NULL);
timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
printf("timer = %ld us\n", timer);
}
//break;
case SEARCH_BINARY:
{
cout << "Binary Searching ... " << endl;
struct timeval start;
struct timeval end;
unsigned long timer;
gettimeofday(&start, NULL);
// int search_num = ary[77];
// printf("Target num: %d \r\n", search_num);
int ret;
ret = binary_search(ary, MAX, search_num);
if(ret != -1)
{
printf("Get the number in ary index: %d \r\n", ret);
}
else
{
printf("Can not Found in arrray!!! \r\n");
}
gettimeofday(&end, NULL);
timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
printf("timer = %ld us\n", timer);
}
break;
default:
{
}
break;
}
printf("===== Type Feature type option (0-1): ");
FEATURE_TYPE_T feature_type;
scanf("%d", &feature_type);
switch(feature_type)
{
case FEATURE_FIBONACCI:
{
cout << "Fibonacci test ..." << endl;
int fib_n = 0;
cout << "Type n: ";
cin >> fib_n;
printf("fibonacci_fun(%d)=%d \r\n", fib_n, fibonacci_fun(fib_n));
}
break;
case FEATURE_EUCLIDEAN:
{
cout << "EUCLIDEAN test ..." << endl;
}
break;
default:
{
cout << "Default ..." << endl;
}
break;
}
return 0;
}
- Quick Sort
int partition_pivot_Lomuto(int arr[], int left, int right)
{
//print_arr(arr, left, right);
int pivot = arr[right];
int i = left-1;
int j;
for(j=left; j<right; j++)
{
if(arr[j] < pivot)
{
i++;
if(i != j)
{
//cout << "\n in loop: arr[i]: " << arr[i] << " arr[j]: " << arr[j] << " i: " << i << " j: " << j << endl;
swap(&arr[i], &arr[j]);
}
}
}
i++;
swap(&arr[i], &arr[right]);
return i;
}
void quick_sort(int arr[], int left, int right)
{
if(left < right)
{
int pivot;
//pivot = partition_pivot_Hoare(arr, left, right);
pivot = partition_pivot_Lomuto(arr, left, right);
quick_sort(arr, left, pivot-1);
quick_sort(arr, pivot+1, right);
}
return;
}- Merge Sort
void merge(int arr[], int left, int mid, int right)
{
printf("[merge] ===================== \r\n");
printf("[merge] left=%d, mid=%d, right=%d \r\n", left, mid, right);
int arr_len = right;
show_arr(arr, arr_len);
int l = left;
int m = mid;
int r = right;
int lenA = m-l+1;
int arrA[lenA];
int lenB = r-(m+1)+1;
int arrB[lenB];
// copy value to arrA & arrB
int arrA_i = 0;
for(arrA_i; arrA_i<lenA; arrA_i++){
arrA[arrA_i] = arr[l + arrA_i];
}
int arrB_i = 0;
for(arrB_i; arrB_i<lenB; arrB_i++){
arrB[arrB_i] = arr[(m+1)+arrB_i];
}
arrA_i = 0;
arrB_i = 0;
int arr_k = left;
// compare 2 arr
while(arrA_i < lenA && arrB_i < lenB)
{
if(arrA[arrA_i] < arrB[arrB_i]){
arr[arr_k] = arrA[arrA_i];
arrA_i++;
arr_k++;
}
else
{
arr[arr_k] = arrB[arrB_i];
arrB_i++;
arr_k++;
}
}
// handle rest
while(arrA_i < lenA){
arr[arr_k] = arrA[arrA_i];
arr_k++;
arrA_i++;
}
while(arrB_i < lenB){
arr[arr_k] = arrB[arrB_i];
arr_k++;
arrB_i++;
}
return;
}
void merge_sort(int arr[], int left, int right)
{
int mid = 0;
printf("*****************\r\n");
printf("left=%d, right=%d \r\n", left, right);
if (left < right)
{
mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid+1, right);
merge(arr, left, mid, right);
}
return;
}