【データ構造(C言語)】並べ替えアルゴリズム
#define _CRT_SECURE_NO_WARNINGS
#include<Python.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<windows.h>
#define MaxSize 100000
#define ERROR 0
#define FALSE 0
#define OK 1
#define TRUE 1
#define IsFull 2
#define IsEmpty 3
typedef int KeyType;
typedef int DataType;
typedef int Status;
typedef int ElemType;
typedef struct entry //
{
KeyType key; // ，KeyType
DataType data; //data
}Entry;
typedef struct list //
{
int n; //
Entry D[MaxSize]; //
}List;
Status Init(List *list, int mSize)
{
list->n = mSize;
return OK;
}
Status Insert(List *list, int i, ElemType x)
{
if (i<-1 || i>list->n - 1) return ERROR;
if (list->n == MaxSize) return IsFull;
for (int j = list->n - 1; j > i; j--) list->D[j + 1] = list->D[j]; // i ， 1
list->D[i + 1].key = x; // i
list->n = list->n + 1; //
return OK;
}
Status Output(List *list)
{
if (list->n == 0) return IsEmpty;
printf(" ：
");
for (int i = 0; i < list->n; i++) printf("%d ", list->D[i].key);
printf("
");
return OK;
}
Status OutputRe(List *list)
{
if (list->n == 0) return IsEmpty;
printf(" ：
");
for (int i = list->n; i > 0; i--) printf("%d ", list->D[i-1].key);
printf("
");
return OK;
}
Status Output1(List *list)
{
if (list->n == 0) return IsEmpty;
for (int i = 0; i < list->n; i++) printf("%d ", list->D[i].key);
printf("
");
return OK;
}
/* startindex */
int FindMin(List *list, int start_index)
{
int min_index = start_index;
for (int i = start_index + 1; i < list->n; i++)
if (list->D[i].key < list->D[min_index].key)
min_index = i;
return min_index;
}
/* */
void Swap(Entry *D, int i, int j)
{
Entry temp;
if (i == j) return;
temp = D[i];
D[i] = D[j];
D[j] = temp;
}
/* */
void SelectSort(List *list)
{
int min_index, start_index = 0;
while (start_index < list->n - 1)
{
min_index = FindMin(list, start_index);
Swap(list->D, start_index, min_index);
start_index++;
}
}
/* */
void InsertSort(List *list)
{
int j;
Entry insert_item; //
for (int i = 1; i < list->n; i++)
{
insert_item = list->D[i];
for (j = i - 1; j>=0; j--)
{
if (insert_item.key < list->D[j].key) list->D[j + 1] = list->D[j];// ，
else break;
}
list->D[j + 1] = insert_item;
}
}
/* */
void BubbleSort(List *list)
{
Status isSwap = FALSE; //
for (int i = list->n - 1; i > 0; i--)
{
isSwap = FALSE; //
for (int j = 0; j < i; j++)
{
if (list->D[j].key > list->D[j + 1].key)
{
Swap(list->D, j, j + 1);
isSwap = TRUE;
}
}
if (!isSwap) break; // ， 。
}
}
/* */
int Partition(List *list, int low, int high)
{
int i = low, j = high + 1;
Entry pivot = list->D[low];//pivot
do {
do i++; while (i < high&&list->D[i].key < pivot.key);//i
do j--; while (list->D[j].key > pivot.key);//j
if (i < j) Swap(list->D, i, j);
} while (i < j);
Swap(list->D, low, j);
return j;// j
}
void QuickSort(List *list, int low, int high)
{
if (low < high)// 2
{
int k = Partition(list, low, high);
QuickSort(list, low, k - 1);
QuickSort(list, k + 1, high);
}
}
/* */
void Merge(List *list, Entry *temp, int low, int n1, int n2)
{
int i = low, j = low + n1;
while (i <= low + n1 - 1 && j <= low + n1 + n2 - 1)
{
if (list->D[i].key <= list->D[j].key) *temp++ = list->D[i++];
else *temp++ = list->D[j++];
}
while (i <= low + n1 - 1) *temp++ = list->D[i++];
while (j <= low + n1 + n2 - 1) *temp++ = list->D[j++];
}
void MergeSort(List *list)
{
Entry *temp=(Entry*)malloc(sizeof(Entry)*MaxSize);
int low, n1, n2, size = 1;
while (size < list->n)
{
low = 0;
while (low + size < list->n)
{
n1 = size;
if (low + size * 2 < list->n) n2 = size;
else n2 = list->n - low - size;
Merge(list, temp + low, low, n1, n2);
low += n1 + n2;
}
for (int i = 0; i < low; i++) list->D[i] = temp[i];
size *= 2;
}
}
/* */
void AdjustDown(Entry *heap, int current, int border)
{
int p = current;
int minChild;
Entry temp;
while (2 * p + 1 <= border)// p ，
{
if ((2 * p + 2 <= border) && (heap[2 * p + 1].key > heap[2 * p + 2].key)) minChild = 2 * p + 2;
else minChild = 2 * p + 1;
if (heap[p].key <= heap[minChild].key) break;
else
{
temp = heap[p];
heap[p] = heap[minChild];
heap[minChild] = temp;
p = minChild;
}
}
}
void HeapSort(List *hp)
{
Entry temp;
for (int i = (hp->n - 2) / 2; i >= 0; i--) AdjustDown(hp->D, i, hp->n - 1);
for (int i = hp->n - 1; i > 0; i--)
{
Swap(hp->D, 0, i);
AdjustDown(hp->D, 0, i - 1);
}
}
/* excel */
Status CreateExcel(int *time)
{
PyObject *pName, *pModule, *pDict, *pFunc;
PyObject *pArgs, *pValue;
Py_Initialize();// python
//
if (!Py_IsInitialized())
{
printf("
");
Py_Finalize();
}
// python ， ， .cpp
PyRun_SimpleString("import sys");
PyRun_SimpleString("sys.path.append('./')");
//Python
pModule = PyImport_ImportModule("graph");
if (!pModule) {
printf("py
");
Py_Finalize();
}
else {
//
pFunc = PyObject_GetAttrString(pModule, "create_graph");
if (!pFunc) {
printf("
");
Py_Finalize();
}
// c/c++ python ，
pArgs = PyTuple_New(6);
pValue = PyLong_FromLong(time[0]);
PyTuple_SetItem(pArgs, 0, pValue);
pValue = PyLong_FromLong(time[1]);
PyTuple_SetItem(pArgs, 1, pValue);
pValue = PyLong_FromLong(time[2]);
PyTuple_SetItem(pArgs, 2, pValue);
pValue = PyLong_FromLong(time[3]);
PyTuple_SetItem(pArgs, 3, pValue);
pValue = PyLong_FromLong(time[4]);
PyTuple_SetItem(pArgs, 4, pValue);
pValue = PyLong_FromLong(time[5]);
PyTuple_SetItem(pArgs, 5, pValue);
// ，
pValue = PyObject_CallObject(pFunc, pArgs);
// python
Py_Finalize();
return OK;
}
}
int main()
{
clock_t start, end;
double diff_time[6] = {
0};
int operation, num, data[10] = {
-1 }, difftime[6] = {
0};
char tmpbuf[] = {
0 };
int data_t[MaxSize] = {
0 };
_tzset(); //
_strdate(tmpbuf);
while (1)
{
printf("( : %s)
", tmpbuf);
system("title MADE BY YQC");
List *list = (List*)malloc(sizeof(List));
List *list1 = (List*)malloc(sizeof(List));
List *list2 = (List*)malloc(sizeof(List));
List *list3 = (List*)malloc(sizeof(List));
List *list4 = (List*)malloc(sizeof(List));
List *list5 = (List*)malloc(sizeof(List));
Init(list, 0); //
Init(list1, 0);
Init(list2, 0);
Init(list3, 0);
Init(list4, 0);
Init(list5, 0);
printf("1.
2.
3.
4.
—— :");
scanf("%d", &operation);
system("CLS");
switch (operation)
{
case 1:
printf(" ( 200000)：");
scanf("%d", &num);
printf(" ：");
for (int i = 0; i < num; i++)
{
scanf("%d", data + i);
if (Insert(list, i - 1, data[i]) == IsFull) printf("
");
}
break;
case 2:
printf(" ( 200000)：");
scanf("%d", &num);
printf("
");
srand((unsigned)time(NULL)); //
for(int i = 0; i < num; i++)
if (Insert(list, i - 1, rand()%num) == IsFull) printf("
");
printf(" ：
");
Output1(list);
printf("
");
break;
case 3:
printf(" ( 200000)：");
scanf("%d", &num);
srand((unsigned)time(NULL)); //
printf("*** ……
");
for (int i = 0; i < num; i++)
{
data_t[i] = rand() % num;
if ( Insert(list, i - 1, data_t[i]) == IsFull
& Insert(list1, i - 1, data_t[i]) == IsFull
& Insert(list2, i - 1, data_t[i]) == IsFull
& Insert(list3, i - 1, data_t[i]) == IsFull
& Insert(list4, i - 1, data_t[i]) == IsFull
& Insert(list5, i - 1, data_t[i]) == IsFull) printf("
");
}
printf("*** ， ……
");
start = clock();
SelectSort(list);
end = clock();
diff_time[0] = (double)(end - start) / CLOCKS_PER_SEC;
difftime[0] = diff_time[0] * 1000;
printf(" :%f
", diff_time[0]);
start = clock();
InsertSort(list1);
end = clock();
diff_time[1] = (double)(end - start) / CLOCKS_PER_SEC;
difftime[1] = diff_time[1] * 1000;
printf(" %fms
", diff_time[1]);
start = clock();
BubbleSort(list2);
end = clock();
diff_time[2] = (double)(end - start) / CLOCKS_PER_SEC;
difftime[2] = diff_time[2] * 1000;
printf(" %fms
", diff_time[2]);
start = clock();
QuickSort(list3, 0, list->n - 1);
end = clock();
diff_time[3] = (double)(end - start) / CLOCKS_PER_SEC;
difftime[3] = diff_time[3] * 1000;
printf(" :%fms
", diff_time[3]);
start = clock();
MergeSort(list4);
end = clock();
diff_time[4] = (double)(end - start) / CLOCKS_PER_SEC;
difftime[4] = diff_time[4] * 1000;
printf(" :%fms
", diff_time[4]);
start = clock();
HeapSort(list5);
end = clock();
diff_time[5] = (double)(end - start) / CLOCKS_PER_SEC;
difftime[5] = diff_time[5] * 1000;
printf(" :%fms
", diff_time[5]);
printf("*** Excel ……
");
CreateExcel(difftime);
printf("*** ……
");
break;
case 4:
exit(0);
default:
printf("WARNING: ");
break;
}
if (operation == 1 || operation == 2)
{
printf("1.
2.
3.
4.
5.
6.
—— ：");
scanf("%d", &operation);
switch (operation)
{
case 1:
SelectSort(list);
if (Output(list) == IsEmpty) printf(" ， ");
break;
case 2:
InsertSort(list);
if (Output(list) == IsEmpty) printf(" ， ");
break;
case 3:
BubbleSort(list);
if (Output(list) == IsEmpty) printf(" ， ");
break;
case 4:
QuickSort(list, 0, list->n - 1);
if (Output(list) == IsEmpty) printf(" ， ");
break;
case 5:
MergeSort(list);
if (Output(list) == IsEmpty) printf(" ， ");
break;
case 6:
HeapSort(list);
if (OutputRe(list) == IsEmpty) printf(" ， ");
break;
default:
printf("WARNING: ");
break;
}
}
free(list);
free(list1);
free(list2);
free(list3);
free(list4);
free(list5);
}
return 0;
}
graph.py
# -*- coding:utf-8 -*-
import xlsxwriter
def create_graph(a,b,c,d,e,f):
# excel
workbook = xlsxwriter.Workbook(" .xlsx")
# sheet
worksheet = workbook.add_worksheet()
# worksheet = workbook.add_worksheet("bug_analysis")
# ，
bold = workbook.add_format({
'bold': 1})
# --------1、 excel---------------
# excel ，
headings = [" ", " "]
data = [[" ", " ", " ", " ", " ", " "],[a/1000,b/1000,c/1000,d/1000,e/1000,f/1000]]
#
worksheet.write_row('A1', headings, bold)
#
worksheet.write_column('A2', data[0])
worksheet.write_column('B2', data[1])
# --------2、 excel---------------
# (column chart)
chart_col = workbook.add_chart({
'type': 'column'})
#
chart_col.add_series({
'name': '=Sheet1!$B$1','categories': '=Sheet1!$A$2:$A$7','values': '=Sheet1!$B$2:$B$7','line': {
'color': 'red'},})
# sheet1 ， sheet sheet
# sheet sheet ，
# title x，y
chart_col.set_title({
'name': " "})
chart_col.set_x_axis({
'name': " "})
chart_col.set_y_axis({
'name': " (ms)"})
#
chart_col.set_style(1)
# worksheet
worksheet.insert_chart('A10', chart_col, {
'x_offset': 25, 'y_offset': 10})
workbook.close()
return 0
if __name__=="__main__":
create_graph(10, 40, 50, 20, 10, 50)