이진 검색 트리 알고리즘2

//아카데미에서 공부한답시고 대충 만든거라 문제 많다는 것이 큰 문제...

#include <iostream>

#include <ctime>

using namespace std;

//필요한 배열 버퍼 초기화

int Arrary[255] = { 0, };

//사용할 함수 선언

int input(int data, int index);

void Quick_Sort(int arrary[], int L_index, int R_index);

int partition(int arrary[], int L_index, int R_index);

int Search(int input, int f_index, int l_index);

double round(double value, int pos);

void show();

void Timer_Start();

clock_t Time_Stop();

clock_t CurTime, CheckTime;

void main()

{

int Random = 0; int exit = 1; int check = 0;

int i = 0; int command = 0; int I_search = 0;

while (exit)

{

cout << "이진 트리 검색 예제 프로그램\n";

cout << "랜덤 데이터 입력 작동(1)\n데이터 정렬[퀵 정렬](2)\n데이터 화면 출력(3)\n데이터 검색[이진 검색](4)\n프로그램 종료(0)\n";

cout << "입력 : ";

cin >> command;

switch (command)

{

case 1:

Timer_Start();

srand((unsigned)time(0));

for (i = 0; i < 255;)

{

Random = (rand() % 255) + 1;

// Random = (1000 * (rand() % 1000) + (rand() % 1000)) + 1;

i = input(Random, i);

}

cout << Time_Stop() << endl;

cout << "입력 완료!\n\n";

break;

case 2:

Timer_Start();

Quick_Sort(Arrary, 0, i - 1);

cout << Time_Stop() << endl;

cout << "정렬 완료!\n\n";

break;

case 3:

show();

break;

case 4:

cout << "검색할 데이터 값 입력 : ";

cin >> I_search;

check = Search(I_search, 0, i - 1);

if (check == -1)

cout << "에러!\n\n";

else 

cout << "동일한 데이터 확인 : " << Arrary[check] << ", " << "인덱스 값 : " << check << "\n\n";

break;

case 0:

exit = 0;

break;

}

}

}

int input(int data, int index)

{

for (int i = 0; i < index;)

{

if (Arrary[i] != data)

i++;

else

return index;

}

Arrary[index] = data;

return index += 1;

}

void show()

{

for (int i = 0; i < 255; i++)

{

cout << i + 1 << "번째 데이터 : " << Arrary[i] << endl;

}

cout << "\n";

}

void Quick_Sort(int arrary[], int L_index, int R_index)

{

int point;

if (L_index < R_index)

{

point = partition(arrary, L_index, R_index);

Quick_Sort(arrary, L_index, point - 1);

Quick_Sort(arrary, point + 1, R_index);

}

}

int partition(int arrary[], int L_index, int R_index)

{

int left = L_index, right = R_index; int point = arrary[L_index], temp;

while (left<right)

{

while (left <= R_index && arrary[left] < point)

{

left++;

}

while (right >= L_index && arrary[right] > point)

{

right--;

}

if (left < right)

{

temp = arrary[left];

arrary[left] = arrary[right];

arrary[right] = temp;

}

}

temp = arrary[left];

arrary[left] = arrary[right];

arrary[right] = temp;

return right;

}

int Search(int input, int f_index, int l_index)

{

int low = 0; int High = input; int mid = 0;

if (low < High)

{

mid = (int)round(((double)(l_index + f_index) / 2), 0);

if (High != Arrary[mid])

{

if (High < Arrary[mid])

{

return Search(High, f_index, mid);

}

else if (High > Arrary[mid])

{

return Search(High, mid, l_index);

}

}

else if (High == Arrary[mid])

{

//cout << "동일한 데이터 확인 : " << Arrary[mid] << ", " << "인덱스 값 : " << mid << endl;

return mid;

}

}

else

return -1;

// return 0;

}

double round(double value, int pos)

{

double temp;

temp = value * pow(10, pos);  // 원하는 소수점 자리수만큼 10의 누승을 함

temp = floor(temp + 0.5);          // 0.5를 더한후 버림하면 반올림이 됨

temp *= pow(10, -pos);           // 다시 원래 소수점 자리수로

return temp;

}

void Timer_Start()

{

CheckTime = clock();

}

clock_t Time_Stop()

{

CurTime = clock();

return ((CurTime - CheckTime) / 1000);

}