i want to doing insertion sort and quick sort by linked list.
(我想按链接列表进行插入排序和快速排序。)
code is below and i must add code in node_t* insertion_sort and node_t* quick sort. (代码在下面，我必须在node_t * insert_sort和node_t *快速排序中添加代码。)
other code cannot be modified. (其他代码无法修改。)
and i must get result like that image i cannot do anything. (我必须得到像该图像一样的结果，我无能为力。)
please help me. (请帮我。)
i must do it until today 12 pm i want to doing insertion sort and quick sort by linked list. (我必须一直执行到今天中午12点，我要按插入列表进行插入排序和快速排序。)
code is below and i must add code in node_t* insertion_sort and node_t* quick sort. (代码在下面，我必须在node_t * insert_sort和node_t *快速排序中添加代码。)
other code cannot be modified. (其他代码无法修改。)
and i must get result like that image i cannot do anything. (我必须得到像该图像一样的结果，我无能为力。)
please help me. (请帮我。)
i must do it until today 12 pm i want to doing insertion sort and quick sort by linked list. (我必须一直执行到今天中午12点，我要按插入列表进行插入排序和快速排序。)
code is below and i must add code in node_t* insertion_sort and node_t* quick sort. (代码在下面，我必须在node_t * insert_sort和node_t *快速排序中添加代码。)
other code cannot be modified. (其他代码无法修改。)
and i must get result like that image i cannot do anything. (我必须得到像该图像一样的结果，我无能为力。)
please help me. (请帮我。)
i must do it until today 12 pm i want to doing insertion sort and quick sort by linked list. (我必须一直执行到今天中午12点，我要按插入列表进行插入排序和快速排序。)
code is below and i must add code in node_t* insertion_sort and node_t* quick sort. (代码在下面，我必须在node_t * insert_sort和node_t *快速排序中添加代码。)
other code cannot be modified. (其他代码无法修改。)
and i must get result like that image i cannot do anything. (我必须得到像该图像一样的结果，我无能为力。)
please help me. (请帮我。)
i must do it until today 12 pm (我必须直到今天中午12点为止)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct _node_t {
int element;
struct _node_t *next;
} node_t;
node_t* insertion_sort(node_t *list);
node_t* quicksort(node_t *list);
node_t* generate_random_sequence(int size)
{
node_t *buf;
int i;
buf = (node_t*)malloc(sizeof(node_t)*size);
if( buf == NULL ) exit(-1);
for( i=0 ; i<size-1 ; i++ ) {
buf[i].element = rand();
buf[i].next = buf+i+1;
}
buf[i].element = rand();
buf[i].next = NULL;
return buf;
}
node_t* generate_ordered_sequence(int size)
{
node_t *buf;
int i;
buf = (node_t*)malloc(sizeof(node_t)*size);
if( buf == NULL ) exit(-1);
for( i=0 ; i<size-1 ; i++ ) {
buf[i].element = i;
buf[i].next = buf+i+1;
}
buf[i].element = i;
buf[i].next = NULL;
return buf;
}
node_t* generate_reverse_sequence(int size)
{
node_t *buf;
int i;
buf = (node_t*)malloc(sizeof(node_t)*size);
if( buf == NULL ) exit(-1);
for( i=0 ; i<size-1 ; i++ ) {
buf[i].element = size-i;
buf[i].next = buf+i+1;
}
buf[i].element = size-i;
buf[i].next = NULL;
return buf;
}
int is_sorted(node_t *list)
{
node_t *node = list, *prev;
if( node == NULL ) return 1;
prev = node; node = node->next;
while( node != NULL ) {
if( prev->element > node->element ) return 0;
prev = node;
node = node->next;
}
return 1;
}
void print_sequence(node_t *list,int first_k)
{
int i=0;
while( list!=NULL && i<first_k ) {
printf("%d ",list->element);
list = list->next;
i++;
}
printf("
");
}
int list_length(node_t *list)
{
int len = 0;
while( list ) {
list = list->next;
len++;
}
return len;
}
void test1()
{
node_t *list, *sorted;
printf("[Test 1: Insertion Sort]
");
list = generate_random_sequence(10);
printf(" Generating %d numbers
",list_length(list));
printf(" Before sorted: ");
print_sequence(list,10);
sorted = insertion_sort(list);
printf(" After sorted: ");
print_sequence(sorted,10);
printf(" %d numbers are %s sorted
",
list_length(sorted),
is_sorted(sorted)?"well":"not");
free(list);
}
void test2()
{
node_t *list, *sorted;
printf("[Test 2: Insertion Sort]
");
printf(" For random sequence: ");
list = generate_random_sequence(1000);
sorted = insertion_sort(list);
if( list_length(sorted) == 1000 && is_sorted(sorted) ) printf("ok
");
else printf("not working
");
free(list);
printf(" For ordered sequence: ");
list = generate_ordered_sequence(1000);
sorted = insertion_sort(list);
if( list_length(sorted) == 1000 && is_sorted(sorted) ) printf("ok
");
else printf("not working
");
free(list);
printf(" For reverse sequence: ");
list = generate_reverse_sequence(1000);
sorted = insertion_sort(list);
if( list_length(sorted) == 1000 && is_sorted(sorted) ) printf("ok
");
else printf("not working
");
free(list);
}
void test3()
{
int NSize[] = {100,1000,2000,5000};
int NRepeat[] = {100,50,10,1};
int i, j;
clock_t t1, t2;
double reference, elapse;
node_t *list, *sorted;
printf("[Test 3: Insertion Sort]
");
// reference time
t1 = clock();
for( i=0 ; i<100000 ; i++ ) {
int *p = (int*)malloc(sizeof(int)*1024);
for( j=0 ; j<1024 ; j++ ) {
p[j] = rand() < rand();
}
free(p);
}
t2 = clock();
reference = (double)(t2-t1)/CLOCKS_PER_SEC;
printf(" The reference time is %.4f sec
",reference);
for( i=0 ; i<sizeof(NSize)/sizeof(int) ; i++ ) {
t1 = clock();
for( j=0 ; j<NRepeat[i] ; j++ ) {
list = generate_random_sequence( NSize[i] );
sorted = insertion_sort(list);
free(list);
}
t2 = clock();
elapse = (double)(t2-t1)/CLOCKS_PER_SEC/NRepeat[i];
printf(" random sequence : size = %9d, time = %7.4f (%9.5f x ref)
",
NSize[i],elapse,elapse/reference);
}
for( i=0 ; i<sizeof(NSize)/sizeof(int) ; i++ ) {
t1 = clock();
for( j=0 ; j<NRepeat[i] ; j++ ) {
list = generate_ordered_sequence( NSize[i] );
sorted = insertion_sort(list);
free(list);
}
t2 = clock();
elapse = (double)(t2-t1)/CLOCKS_PER_SEC/NRepeat[i];
printf(" ordered sequence: size = %9d, time = %7.4f (%9.5f x ref)
",
NSize[i],elapse,elapse/reference);
}
for( i=0 ; i<sizeof(NSize)/sizeof(int) ; i++ ) {
t1 = clock();
for( j=0 ; j<NRepeat[i] ; j++ ) {
list = generate_reverse_sequence( NSize[i] );
sorted = insertion_sort(list);
free(list);
}
t2 = clock();
elapse = (double)(t2-t1)/CLOCKS_PER_SEC/NRepeat[i];
printf(" reverse sequence: size = %9d, time = %7.4f (%9.5f x ref)
",
NSize[i],elapse,elapse/reference);
}
}
void test4()
{
node_t *list, *sorted;
printf("[Test 4: Quicksort]
");
list = generate_random_sequence(10);
printf(" Generating %d numbers
",list_length(list));
printf(" Before sorted: ");
print_sequence(list,10);
sorted = quicksort(list);
printf(" After sorted: ");
print_sequence(sorted,10);
printf(" %d numbers are %s sorted
",
list_length(sorted),
is_sorted(sorted)?"well":"not");
free(list);
}
void test5()
{
node_t *list, *sorted;
printf("[Test 5: Quicksort]
");
printf(" For random sequence: ");
list = generate_random_sequence(1000);
sorted = quicksort(list);
if( list_length(sorted) == 1000 && is_sorted(sorted) ) printf("ok
");
else printf("not working
");
free(list);
printf(" For ordered sequence: ");
list = generate_ordered_sequence(1000);
sorted = quicksort(list);
if( list_length(sorted) == 1000 && is_sorted(sorted) ) printf("ok
");
else printf("not working
");
free(list);
printf(" For reverse sequence: ");
list = generate_reverse_sequence(1000);
sorted = quicksort(list);
if( list_length(sorted) == 1000 && is_sorted(sorted) ) printf("ok
");
else printf("not working
");
free(list);
}
void test6()
{
int NSize[] = {1000,10000,100000,1000000,10000000};
int NRepeat[] = {100,100,100,10,1};
int i, j;
clock_t t1, t2;
double reference, elapse;
node_t *list, *sorted;
printf("[Test 6: Quicksort]
");
// reference time
t1 = clock();
for( i=0 ; i<100000 ; i++ ) {
int *p = (int*)malloc(sizeof(int)*1024);
for( j=0 ; j<1024 ; j++ ) {
p[j] = rand() < rand();
}
free(p);
}
t2 = clock();
reference = (double)(t2-t1)/CLOCKS_PER_SEC;
printf(" The reference time is %.4f sec
",reference);
for( i=0 ; i<sizeof(NSize)/sizeof(int) ; i++ ) {
t1 = clock();
for( j=0 ; j<NRepeat[i] ; j++ ) {
list = generate_random_sequence( NSize[i] );
sorted = quicksort(list);
free(list);
}
t2 = clock();
elapse = (double)(t2-t1)/CLOCKS_PER_SEC/NRepeat[i];
printf(" random sequence : size = %9d, time = %7.4f (%9.5f x ref)
",
NSize[i],elapse,elapse/reference);
}
for( i=0 ; i<sizeof(NSize)/sizeof(int) ; i++ ) {
t1 = clock();
for( j=0 ; j<NRepeat[i] ; j++ ) {
list = generate_ordered_sequence( NSize[i] );
sorted = quicksort(list);
free(list);
}
t2 = clock();
elapse = (double)(t2-t1)/CLOCKS_PER_SEC/NRepeat[i];
printf(" ordered sequence: size = %9d, time = %7.4f (%9.5f x ref)
",
NSize[i],elapse,elapse/reference);
}
for( i=0 ; i<sizeof(NSize)/sizeof(int) ; i++ ) {
t1 = clock();
for( j=0 ; j<NRepeat[i] ; j++ ) {
list = generate_reverse_sequence( NSize[i] );
sorted = quicksort(list);
free(list);
}
t2 = clock();
elapse = (double)(t2-t1)/CLOCKS_PER_SEC/NRepeat[i];
printf(" reverse sequence: size = %9d, time = %7.4f (%9.5f x ref)
",
NSize[i],elapse,elapse/reference);
}
}
int main(int argc, char *argv[])
{
int seed = 1;
srand(seed); test1();
srand(seed); test2();
srand(seed); test3();
srand(seed); test4();
srand(seed); test5();
srand(seed); test6();
return 0;
}
ask by Um Steve translate from so 
