Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
5.0 kB
4
Indexable
Never
//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "SelectionSort.h"
#include <time.h>
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"

#define SWAP(a, b, t) (t = a, a = b, b = t) //定義SWAP功能

int data[100000];
int original_data[100000];
int n;
int r;

TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
	: TForm(Owner)
{
}

void SelectionSort(int array[], int n)
{
	int i, j, temp, min;
	for(i = 0; i < n-1; i++)
	{
		min = i;
		for(j = i+1; j < n; j++)
		{
			if(array[j] < array[min])
			{
				min = j;
			}
		}
		SWAP(array[min], array[i], temp);
		/*
		temp = array[min];
		array[min] = array[i];
		array[i] = temp;
        */
	}
}

void BubbleSort(int array[], int n)
{
	int i, j, temp;
	for(i = n-1; i > 0; i--)
	{
		for(j = 0; j < n-1; j++)
		{
			if(array[j] > array[j+1])
			{
				SWAP(array[j], array[j+1], temp);
			}
        }
    }
}

void CopyData(int a[], int b[], int n)
{
	//將a陣列的值複製到b陣列
	int i;
	for(i = 0; i < n; i++)
	{
		b[i] = a[i];
    }
}


void PrintData(int array[], int n, int flag)
{
	//顯示Data的功能寫成Function,Flag表Memo代碼
	if(flag == 1)
	{
		for(int i = 0; i < n; i++)
		{
			Form1->Memo1->Lines->Add("data[" + IntToStr(i) + "] = " + IntToStr(array[i]));
		}
	}
	else if(flag == 2)
	{
		for(int i = 0; i < n; i++)
		{
			Form1->Memo2->Lines->Add("data[" + IntToStr(i) + "] = " + IntToStr(array[i]));
		}
	}
	else if(flag == 3)
	{
		for(int i = 0; i < n; i++)
		{
			Form1->Memo3->Lines->Add("data[" + IntToStr(i) + "] = " + IntToStr(array[i]));
        }
    }
}

void SelfCheck(int a[], int n, int flag)
{
	int i;
	for(i = 0; i < n-1; i++)
	{
		if(a[i] > a[i+1])
		{
			break;
		}
	}
	if(i == n-1)
	{
		if(flag == 2)
		{
			Form1->Memo2->Lines->Add("Data Correctly Sorted!");
		}
		else if(flag == 3)
		{
			Form1->Memo3->Lines->Add("Data Correctly Sorted!");
		}
	}
	else
	{
		if(flag == 2)
		{
			Form1->Memo2->Lines->Add("Data Not Sorted!");
		}
		else if(flag == 3)
		{
			Form1->Memo3->Lines->Add("Data Not Sorted!");
		}
    }
}

int BinarySearch(int arr[], int target, int left, int right)
{
	int middle;
	while(left <= right)
	{
		middle = (left+right)/2;
		if(target < arr[middle])
		{
			right = middle-1;
		}
		else if(target == arr[middle])
		{
			return middle;
		}
		else
		{
			left = middle+1;
		}
	}
	return -1;
}





//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
	clock_t t_start, t_end;
    srand(time(NULL));
	n = StrToInt(Edit1->Text);
	int r = StrToInt(Edit2->Text);
	t_start = clock();
	for(int i = 0; i < n; i++)
	{
		original_data[i] = (rand() % r) + 1;
	}
	t_end = clock();
	if(CheckBox1->Checked)
	{
		PrintData(original_data, n, 1);
	}
    Form1->Memo1->Lines->Add("CPU TIME (sec.): " + FloatToStr((float)(t_end - t_start) / CLOCKS_PER_SEC));
}
//---------------------------------------------------------------------------


void __fastcall TForm1::Button2Click(TObject *Sender)
{
	CopyData(original_data, data, n); //記得將Original Data複製到Data陣列,不然用同一個陣列修改,可能發生排序已經Sorted後的資料
	clock_t t_begin, t_end;
	t_begin = clock();
	SelectionSort(data, n);
	t_end = clock();
	if(CheckBox2->Checked)
	{
		PrintData(data, n, 2);
	}
	if(CheckBox4->Checked)
	{
		SelfCheck(data, n, 2);
	}
	Form1->Memo2->Lines->Add("CPU TIME (sec.): " + FloatToStr((float)(t_end-t_begin)/CLOCKS_PER_SEC));
}
//---------------------------------------------------------------------------


void __fastcall TForm1::Button3Click(TObject *Sender)
{
	CopyData(original_data, data, n); //記得將Original Data複製到Data陣列,不然用同一個陣列修改,可能發生排序已經Sorted後資料的指令
	clock_t time_begin, time_end;
	time_begin = clock();
	BubbleSort(data, n);
	time_end = clock();
	if(CheckBox3->Checked)
	{
		PrintData(data, n, 3);
	}
	if(CheckBox5->Checked)
	{
		SelfCheck(data, n, 3);
	}
	Form1->Memo3->Lines->Add("CPU TIME (sec.): " + FloatToStr((float)(time_end-time_begin)/CLOCKS_PER_SEC));
}
void __fastcall TForm1::Button4Click(TObject *Sender)
{
	int target = StrToInt(Form1->Edit3->Text);
	int success = -1;
	success = BinarySearch(data, target, 0, n-1);
	if(success >= 0 && success < n)
	{
		Form1->Memo4->Lines->Add(IntToStr(data[success]) + " has been found at data[" + IntToStr(success) + "]!");
	}
	else
	{
		Form1->Memo4->Lines->Add(IntToStr(target) + " has NOT been found!");
    }
}
//---------------------------------------------------------------------------