- This topic has 1 reply, 2 voices, and was last updated 19 years, 5 months ago by
.
Viewing 1 reply thread
- Posts
A program to sort a range of numbers with Insertion and Quicksort, check their sorting time and prompt the result on the screen
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175/* use header file*/<br />#include <stdio.h><br />#include <iostream.h><br />#include <stdlib.h><br />#include <values.h><br />#include <time.h><br />#include <string.h><br />#include <conio.h><br />/* define variable */<br />const int max=29000;<br />int list[max];<br />FILE *fp;<br />clock_t start,end;<br />char any1[8];<br />/* Insertion sort module */<br />void insertion(int min1,int max1)<br />{<br />int a,b,v;<br />for(a=min1;a<=max1;a++)<br />{<br />v = list[a];<br />b = a;<br />do<br />{<br />list = list[b-1];<br />b = b - 1;<br />} while(list[b-1] > v);<br />list = v;<br />}<br />}<br />/* sort partitioning element */<br />void sorthree(int x,int y,int z)<br />{<br />int temp;<br />if (list[x] > list[y])<br />{<br />temp = list[x];<br />list[x] = list[y];<br />list[y] = temp;<br />}<br />if (list[z] < list[x])<br />{<br />temp = list[x];<br />list[x] = list[z];<br />list[z] = temp;<br />temp = list[y];<br />list[y] = list[z];<br />list[z] = temp;<br />}<br />if ((list[z] > list[x]) && (list[z] < list[y]))<br />{<br />temp = list[y];<br />list[y] = list[z];<br />list[z] = temp;<br />}<br />}<br />/* Quicksort module */<br />void quicksort(int min2,int max2)<br />{<br />int m,v,t,i,j,q;<br />if ((max2-min2) > 9)<br />{<br />m = (max2-min2+1)/2;<br />sorthree(min2,m,max2);<br />max2=max2-1;<br />q = list[m];<br />list[m] = list[max2];<br />list[max2] = q;<br />v = list[max2];<br />i = min2+1;<br />j = max2-1;<br />do<br />{<br />do<br />{<br />i=i+1;<br />} while (list < v);<br />do<br />{<br />j=j-1;<br />} while (list[j] > v);<br />t = list;<br />list = list[j];<br />list[j] = t;<br />} while (i<j);<br />list[j]=list;<br />list=list[max2];<br />list[max2]=t;<br />quicksort(min2,i-1);<br />quicksort(i+1,max2);<br />}<br />else<br />insertion(m,max2);<br />}<br /><br />/* main program */<br />void main()<br />{<br />int i,j,k,min,max1;<br />char any2[8];<br />clrscr();<br />cout << "Enter a file name to store data :";<br />cin >> any1; /* input data file name on */<br />cout << 'n' << "Generating file...waitsnn";/* screen */<br />fp = fopen(any1,"w");<br />for(j=0;j<max/200;j++)<br />{<br />for(i=0;i<200;i++) /* write random values to file */<br />{<br />k = rand();<br />fprintf(fp,"%dn",k);<br />}<br />}<br />fclose(fp);<br />fp = fopen(any1,"r");<br />i = 0;<br />while(fscanf(fp,"%dn",&k) != EOF)<br />{<br />list = k; /* read values from file and assign to an array */<br />i = i + 1;<br />}<br />fclose(fp);<br />min = 0;<br />max1 = max;<br />max1=max1-1;<br />cout << "Sorting with Quicksort... waits" << 'n';<br />start = clock();<br />quicksort(min,max1); /* sort an unsorted list with quicksort */<br />end=clock();<br />float result = (end-start)/CLK_TCK;<br />cout << "The time needs to sort " << max<br /><< " numbers in Quciksort is : " << result << " second(s)" << "nn";<br /><br />cout << "Enter an output file for Quicksort : ";<br />cin >> any2;<br />fp = fopen(any2,"w");<br />for(i=0;i<max;i++)<br />{ /* write the output from quicksort and put them */<br />k = list; /*to a file */<br />fprintf(fp,"%dn",k);<br />}<br />fclose(fp);<br />fp = fopen(any1,"r");<br />i = 0;<br />while(fscanf(fp,"%dn",&k) != EOF)<br />{<br />list = k;<br />i = i + 1;<br />}<br />fclose(fp);<br />cout << "nSorting with Insertion Sort... waits" << 'n';<br />start = clock();<br />insertion(0,max); /* sort an unsorted list with insertion sort */<br />end=clock();<br />result = (end-start)/CLK_TCK;<br />cout << "The time needs to sort " << max<br /><< " numbers in Insertion is : " << result << " second(s)" << "nn";<br />cout << "Sort an already sorted array again with Quicksort..." << 'n';<br />min = 0;<br />max1 = max;<br />max1=max1-1;<br />start = clock();<br />quicksort(min,max1); /* sort an already sort list with quicksort */<br />end=clock();<br />result = (end-start)/CLK_TCK;<br />cout << "The time needs to sort " << max<br /><< " numbers in Quicksort is : " << result << " second(s)" << "n";<br />cout << "Sort an already sorted array again with Insertion sort..." << 'n';<br />start = clock();<br />insertion(0,max); /* sort an already list with insertion sort */<br />end=clock();<br />result = (end-start)/CLK_TCK;<br />cout << "The time needs to sort " << max<br /><< " numbers in Insertion sort is : " << result << " second(s)" << 'n';<br />}
Viewing 1 reply thread
- The forum ‘C Programming’ is closed to new topics and replies.