Hi mn
Mình có 1 vấn đề lạ mong mn giúp ^^
Issue: thuật toán trong sort2, sort3, mình nghĩ sort2 là bubble sort, nhưng hàm đệ quy trong nó, thì ko tài nào nghĩ ra, nếu bubble thì nó phải 2 vòng lặp for, cái này chỉ có 1
Hoặc trong sort2, phải so sánh a[i].key[0] = a[j].key[0] có bằng ko trước, rồi mới sort key[1] thì đúng.
Phân tích: bài toán sort array gồm 3 key theo thứ tự ưu tiên từ trái -> phải, kết quả như list2; khi kí số bên trái giống nhau, thì tiếp tục sort dần sang phải.
Sort1: hàm quick sort để sort key[0]
Sort2: hàm để sort key[1]
Sort3: hàm để sort key[2]
Mình nghĩ trong sort1 là:
A: while ( a[i].key[k] < x.key[k])
B: while ( a[j].key[k] > x.key[k])
C: sort1(k,left,j-1);
D: sort1(k,i+1,right);
#include <stdio.h>
#define KEY 3
struct item {
char id;
int key[KEY];
};
#define N 8
struct item a[N]={
{'A', {2,2,3}},
{'B', {2,2,2}},
{'C', {1,2,2}},
{'D', {1,1,2}},
{'E', {3,2,1}},
{'F', {3,1,1}},
{'G', {1,1,1}},
{'H', {2,1,1}},
};
void printitem(){
int i,k;
printf("\n" );
for ( i = 0; i < N; i++) {
printf("<%c", a[i].id);
for (k=0; k<KEY; k++)
printf(":%d",a[i].key[k] );
printf("> " );
}
printf("\n" );
}
void sort1(int k, int left, int right){
int i,j ;
struct item x,tmp;
if (left < right) {
i= left;
j= right;
//printf("\nHehe0 %ld\n", (left+right)/2 );
x= a[(left+right)/2];
printf("k= %d\n",k );
printf("x.key[k]: %d\n", x.key[k] );
printf("x.id: %c\n", x.id );
printf("left=%d , right=%d\n",left, right );
//printf("a[0] %ld\n\n", a[0] );
do {
printf("hello1, i= %d\n",i );
//while ( (i<=j) & (a[i].key[k] < x.key[k]))
while ( a[i].key[k] < x.key[k])
{printf("hello1.1, i= %d\n",i ) ; i++ ;}; //A
printf("hello2\n" );
//while ( (i<=j) & (a[j].key[k] > x.key[k]))
while ( a[j].key[k] > x.key[k])
{printf("hello2.2, i= %d ,j= %d\n",i,j );j--; }; //B
//printf("hello3\n\n" );
printf("hello3, i= %d ,j= %d\n",i,j );
if (i<=j) {
printf("hello4,HOAN VI i= %d ,j= %d, a[i]=%c , a[j]=%c\n",i,j,a[i].id,a[j].id );
if (i<j) { tmp=a[i]; a[i]=a[j]; a[j]=tmp; }
printf("hello5, a[i]= %d ,a[j]= %d\n",a[i].key[k],a[j].key[k] );
i++; j--;
printf("hello6, i= %d ,j= %d\n\n",i,j );
//printf("i= %d , j = %d \n",i,j );
printitem();
}
} while(i<=j);
printitem();
//case i > j
if (left<j)
printf("===========HOI QUI 1\n" );
//sort1(k,left,j-1);
sort1(k,left,j);
if (i<right)
printf("====HOI QUI 2\n" );
sort1(0,i,right);
//sort1(k,i+1,right);
//sort1(k,i,right);
//tmp=a[j]; a[j]=x; x=tmp;
//printitem();
}
}
void sort2(int k, int left, int right){
int i;
struct item tmp;
printf("left= %d, right= %d\n",left, right );
if (left<right){
for (int i = left; i < right; i++) {
printf("\ni= %d\n",i );
if (a[i+1].key[k] < a[i].key[k]) {
tmp=a[i];
a[i]=a[i+1];
a[i+1]=tmp;
printf("\n sort2 %c %c\n", a[i+1].id , a[i].id );
}
//printf("hi1 %d\n", );
}
printitem();
sort2(k,left+1,right);
//sort2(k,right,left); SAI
}
}
void sort3() {
int k;
for (k = 0; k < 3; k++) {
printf("*********k= %d\n", k);
sort1(k,0,N-1);
}
}
int main (void) {
for (int i = 0; i < N; i++) {
printf("\n%c ", a[i].id );
for (int j = 0; j < KEY ; j++) {
printf("%d ", a[i].key[j] );
}
}
printf("\ntest1\n" );
printitem;
printf("\ntest2-----\n" );
sort1(0,0,7);
//sort1(1,0,7);
printitem();
//printf("\nVerify: %d \n", a[0].key[0]);
//printf("Verify: %d \n", a[0].key[1]);
//printf("Verify: %d \n", a[0].key[2]);
//sort1(0,0,7);
//sort3();
sort2(1,0,7);
printitem();
/*sort2(2,0,7);
printitem();*/
return 0;
// printf("Hello %c \n", a[1].id );
}
Output sau sort1 cua minh:
<D:1:1:2> <G:1:1:1> <C:1:2:2> / <A:2:2:3> <H:2:1:1> <B:2:2:2> / <E:3:2:1> <F:3:1:1>
Minh nghĩ qa sort2, nó sẽ swap A&H ; E&F
giữ nguyên thứ tự ban đầu khi sort.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?