Tweet
Nhờ các anh chị giúp em sửa lỗi này với, em viết hàm nhập 1 mảng n phần tử trong khoảng từ 1->100000 rồi sinh ra mảng ngẫu nhiên. Mặc dù hàm đúng, debug không lỗi nhưng khi chạy thì báo warning...... Với cái hàm radix sort bị lỗi nữa....
Mong các anh chị giải thích giùm....
Đây là code của em...
Mong các anh chị giải thích giùm....
Đây là code của em...
Code:
#include<time.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
void Swap(int &a, int &b)
{
int t=a;
a=b;
b=t;
}
void menu()
{
printf("....Menu tuy chon....\n");
printf("1.Tao mang ngau nhien\n");
printf("2.Interchange Sort - Doi cho truc tiep\n");
printf("3.Bubble Sort - Noi bot\n");
printf("4.Insertion Sort - Chen truc tiep\n");
printf("5.Binary Insertion Sort - Chen nhi phan\n");
printf("6.Shaker Sort - Update cua Bubble Sort\n");
printf("7.Shell Sort\n");
printf("8.Heap Sort\n");
printf("9.Quick Sort\n");
printf("10.Merge Sort\n");
printf("11. Radix Sort\n");
printf("12.So sanh thoi gian toan bo thuat toan sap xep\n");
printf("13.Thoat\n");
}
void nhap(int &n)
{
printf("Nhap n trong khoang 1-100000 = \n");
scanf("%d",&n);
}
void interchange_sort(int a[], int n)
{
for(int i = 0 ; i < n -1; i++)
for(int j = i+1 ; j < n ; j++)
if(a[i] > a[j])
Swap(a[i], a[j]);
}
void selection_sort(int a[], int n)
{
int min;
for(int i = 0 ; i < n -1 ; i++)
{
min = i;
for(int j = i +1 ; j< n ; j++)
{
if(a[min] > a[j])
{
min = j;
Swap(a[min],a[i]);
}
}
}
}
void Bubble_Sort(int a[],int n)
{
int i, j;
for (i = 0 ; i<n-1 ; i++)
for (j =n-1; j >i ; j --)
if(a[j]< a[j-1])// neu sai thi doi cho
Swap(a[j],a[j-1]);
}
void Shell_Sort(int numbers[], int array_size)
{
int i, j, increment, temp;
increment = array_size / 2;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
if (increment == 2)
increment = 1;
else
increment = increment * 5 / 11;
}
}
void Quick_Sort(int a[], int left, int right)
{
int i, j, x;
x = a[(left+right)/2];
i = left; j = right;
while(i < j)
{
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i <= j)
{
Swap(a[i],a[j]);
i++ ; j--;
}
}
if(left<j)
Quick_Sort(a, left, j);
if(i<right)
Quick_Sort(a, i, right);
}
//Heap_sort
void shift(int *a,int l,int r)// khoi tao heap//
{
int x, i ,j;
i= l ;
j= 2*i+1;
x = a[i];
while(j<=r)
{
if(j<r && a[j] < a[j+1])
j++;
if(a[j]<=x)
return;
else
{
a[i] = a[j];
a[j] = x;
i=j;
j=2*i+1;
x=a[i];
}
}
}
void CreateHeap(int *a,int n)//heap//
{
int l;
l= n/2-1;
while(l>=0)
{
shift(a,l,n-1);
l=l-1;
}
}
void Heap_Sort(int *a,int n)//sap xep heap
{
int r;
CreateHeap(a,n);
r = n-1;
while(r > 0)
{
Swap(a[0],a[r]);
r--;
if( r > 0 )
shift(a,0,r);
}
}
void Radix_Sort(int a[], int n)
{
int i, m = a[0], exp = 1;
int *b;
b = new int(sizeof(n));
for (i = 0; i < n; i++) /// tim m (max)
{
if (a[i] > m)
m = a[i];
}
while (m / exp > 0)
{
int bucket[10] = {0};
for (i = 0; i < n; i++)
bucket[a[i] / exp % 10]++;
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--bucket[a[i] / exp % 10]] = a[i];
for (i = 0; i < n; i++)
{
a[i] = b[i];
}
exp *= 10;
}
free(b);
}
void Shaker_Sort(int a[],int n)
{
int i, j;
int left, right, k;
left = 0;
right = n-1;
k = n-1;
while (left < right)
{
for(j = right; j > left; j --)
if (a[j]< a[j-1])
{
Swap(a[j], a[j-1]);
k =j;
}
left = k;
for (j = left; j < right; j ++)
if (a[j]> a[j+1])
{
Swap(a[j],a[j-1]);
k = j;
}
right = k;
}
}
void insertionSort(int a[], int n)
{
for(int i=1; i<n; i++)
{
int cur = a[i];
int j = i-1;
while((j >= 0) && (a[j] > cur))
{
a[j+1] = a[j];
j--;
}
a[j+1] = cur;
}
}
void BInsertion_Sort(int a[],int n )
{
int l,r,m,i;
int x;//luu gia tri cua a de tranh ghi de
for(int i=1 ; i<n ; i++)
{
x = a[i]; l = 0; r = i-1;
while(l<=r) // tim vi tri chen x
{
m = (l+r)/2; // tim vi tri thich hop cua m
if(x < a[m])
r = m-1;
else
l = m+1;
}
for(int j = i-1 ; j >=l ; j--)
a[j+1] = a[j];// doi cac phan tu se dung sau x
a[l] = x; // chen x vao day
}
}
//Merge Sort
int max(int x, int y)
{
if(x > y)
{
return x;
}
else
{
return y;
}
}
void merge_helper(int *input, int left, int right, int *scratch)
{
/* base case: one element */
if(right == left + 1)
{
return;
}
else
{
int i = 0;
int length = right - left;
int midpoint_distance = length/2;
/* l and r are to the positions in the left and right subarrays */
int l = left, r = left + midpoint_distance;
/* sort each subarray */
merge_helper(input, left, left + midpoint_distance, scratch);
merge_helper(input, left + midpoint_distance, right, scratch);
/* merge the arrays together using scratch for temporary storage */
for(i = 0; i < length; i++)
{
/* Check to see if any elements remain in the left array; if so,
* we check if there are any elements left in the right array; if
* so, we compare them. Otherwise, we know that the merge must
* use take the element from the left array */
if(l < left + midpoint_distance &&
(r == right || max(input[l], input[r]) == input[l]))
{
scratch[i] = input[l];
l++;
}
else
{
scratch[i] = input[r];
r++;
}
}
/* Copy the sorted subarray back to the input */
for(i = left; i < right; i++)
{
input[i] = scratch[i - left];
}
}
}
int Merge_Sort(int *input, int size)
{
int *scratch = (int *)malloc(size * sizeof(int));
if(scratch != NULL)
{
merge_helper(input, 0, size, scratch);
free(scratch);
return 1;
}
else
{
return 0;
}
}
void check(int &n)
{
if(n<=0 || n>100000)
{
do
{
printf("\nNhap sai vui long nhap lai!\n");
nhap(n);
}
while(n<=0 || n>100000);
}
}
void nhapmang(int a[], int n)
{
for(int i=0;i<n;i++)
{
a[i]=rand();
}
}
int main()
{
clock_t batdau, ketthuc;
float khoangthoigian;
srand(time(NULL));
int n,chon,*a;
a = new int(sizeof(n));
for(;;)
{
menu();
do
{
printf("Nhap tuy chon: \n");
scanf("%d",&chon);
}while(chon<1 && chon>13);
switch(chon)
{
case 1:
nhap(n);
check(n);
nhapmang(a,n);
getch();
break;
case 2:
batdau = clock();
interchange_sort(a,n);
printf("Loading.....\n");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 3:
batdau = clock();
Bubble_Sort(a,n);
printf("Loading.....\n");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 4:
batdau = clock();
Bubble_Sort(a,n);
printf("Loading.....\n");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 5:
batdau = clock();
BInsertion_Sort(a,n);
printf("Loading.....\n");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 6:
batdau = clock();
Shaker_Sort(a,n);
printf("Loading.....\n");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 7:
batdau = clock();
Shell_Sort(a,n);
printf("Loading.....");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 8:
batdau = clock();
Heap_Sort(a,n);
printf("Loading.....\n");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 9:
batdau = clock();
Quick_Sort(a,0,n-1);
printf("Loading.....\n");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 10:
batdau = clock();
Merge_Sort(a,n);
printf("Loading.....\n");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 11:
batdau = clock();
Radix_Sort(a,n);
printf("Loading.....\n");
ketthuc = clock();
khoangthoigian = float(ketthuc - batdau)/CLOCKS_PER_SEC;
printf("Khoang thoi gian sap xep la: %f",khoangthoigian);
getch();
break;
case 12:
break;
case 13:
printf("Tam biet!\n");
printf("Press any key to exit.....");
getch();
return 0;
default: break;
}
system("cls");
}
getch();
}
