Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: sắp xếp mảng số nguyên chẵn tăng dần, lẻ tăng dần, không dùng mảng tạm

  1. #1
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Talking sắp xếp mảng số nguyên chẵn tăng dần, lẻ tăng dần, không dùng mảng tạm

    Cho 1 dãy n số nguyên,,sắp xếp dãy thành 2 phần,,phần đầu gồm các số chẵn tăng dần,phần sau gồm các số lẻ tăng dần
    Chú ý:Không dùng mảng tạm làm trung gian trong quá trình sắp xếp
    Không viết 2 lần chương trình sắp xếp dãy

    Còn đây là cách của mình, sử dụng Insertion Sort, coi hai đầu của mảng là hai dẫy đã được sắp xếp, dãy trái là số chẵn, dãy phải là số lẻ. Duyệt qua từng phần tử của mảng, tùy thuộc vầo nó là chẵn hay lẻ mà ta tìm vị trí thích hợp của nó trong dãy trái hay phải.

    C Code:
    1. #include "stdio.h"
    2. #include "conio.h"
    3. #include "stdlib.h"
    4. // Khai bao bien
    5. int Maxn=1000;
    6. int Arr[1001];
    7. void initArr()
    8. {
    9.    int i;
    10.    for (i=1;i<=Maxn;++i)
    11.       {
    12.      Arr[i]= int(rand());
    13.       }
    14. }
    15. void sort()
    16. {
    17.    int trai=0;
    18.    int phai=Maxn+1;
    19.    int I=1;
    20.    int J, T;
    21.    while (I<phai)
    22.       {
    23.        if ((Arr[I] % 2)==0)
    24.       {
    25.          T= Arr[I];
    26.          Arr[0]=T;
    27.          Arr[I]= Arr[trai+1];
    28.          J= trai;
    29.          while (T<Arr[J])
    30.         {
    31.            Arr[J+1]= Arr[J];
    32.            J--;
    33.         }
    34.          Arr[J+1]= T;
    35.          trai++;
    36.          I++;
    37.       }
    38.        else
    39.       {
    40.          T= Arr[I];
    41.          Arr[Maxn+1]= T;
    42.          Arr[I]= Arr[phai-1];
    43.          J= phai;
    44.          while (T<Arr[J])
    45.         {
    46.            Arr[J-1]= Arr[J];
    47.            J++;
    48.         }
    49.          Arr[J-1]=T;
    50.          phai--;
    51.       }
    52.       }
    53. }
    54. void print()
    55. {
    56.    int i;
    57.    printf("\n");
    58.    for (i=1;i<Maxn; i++)
    59.    {
    60.       if (i % 6 == 0) printf("\n%7d ",Arr[i]);
    61.       else printf("%7d ",Arr[i]);
    62.    }
    63. }
    64. int main()
    65. {
    66.  clrscr();
    67.  printf("\nBan muon sap xep mang bao nhieu phan tu:");scanf("%d",&Maxn);
    68.  initArr();
    69.  print();
    70.  sort();
    71.  print();
    72.  return 0;
    73. }

  2. #2
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Tui nghĩ cách của bạn hailoc12 là đúng.

    Bây giờ mình thử nghĩ thêm 1 chút xíu coi sao nghen: giả sử mảng có nhiều phần tử => mình muốn xài quicksort cho nhanh => mình phải làm ra sao ? Một cách làm là mình đẩy các số chẵn về 1 đầu & các số lẻ về 1 đầu rồi gọi quick sort. Nhưng đề bài là yêu cần chỉ 1 lần sắp xếp !

    Thêm nữa, thay vì chẵn & lẻ thì giả sử đề bài là: bội số của 2 ở bên trái, bội số của 3 ở giữa và còn lại thì ở bên phải => mình phải làm ra sao ?

    Trong PERL có hàm sort và C có hàm qsort. Cả 2 cái này có chung 1 ý tưởng rất hay: các giải thuật sắp xếp thông thường cuối cùng cũng phải gọi 1 hàm để so sánh 2 phần tử a[i] & a[j] nào đó => mình chỉ cần viết cái hàm này => khi gọi giải thuật sắp xếp thì đưa vô như là 1 tham số. Cái hàm này làm như sau: cho 2 phần tử a và b: trả về -1 nếu a<b, trả về 0 nếu a==b, và trả về 1 nếu a>b (đại khái là như vậy) . Trong ví dụ của mình thì:

    1) nếu a chẵn và b lẻ thì a<b; nếu a lẻ và b chẵn thì a>b; ...........

    2) nếu a là bội số của 2 và b không là bội số của 2 thì a<b, nếu a là bội số của 3 ......

    Trường hợp thứ 2 rắc rối 1 chút (if, else .....); nhưng mình không cần phải viết lại hàm sắp xếp (mà lúc nào cũng chỉ cần viết lại hàm so sánh mà thôi). Mình có thể viết hàm so sánh ở trường hợp thứ hai khác đi 1 chút: xài 2 cấp so sánh. Nếu bội số của 2 thì cho điểm (ở mức 1) là 1, nếu là bội số của 3 thì cho điểm (ở mức 1) là 2, còn lại thì cho điểm là 3; nếu a & b có cùng điểm (ở múc 1) thì ........... . Viết như vậy thì sẽ đỡ sót trường hợp và "if else" rối rắm

    (có gì sai sót mong được góp ý, xin cám ơn)

    -thân
    Đã được chỉnh sửa lần cuối bởi bete : 09-08-2006 lúc 02:11 AM.

  3. #3
    No Avatar
    sourcecodecrazyfan Khách

    C Code:
    1.   int n = 9;
    2.   int[] a = {5,3,2,1,6,4,9,8,2};
    3.   for (int i=0; i<n-1; i++)
    4.   {
    5.    for (int j=i+1; j<n; j++)
    6.    {
    7.     if (a[ i ]%2==1 && a[ j ]%2==0)
    8.     {
    9.      int t=a[ i ];
    10.      a[ i ]=a[ j ];
    11.      a[ j ]=t;
    12.     }
    13.     if (((a[ i ]%2==1 && a[ j ]%2==1) || (a[ i ]%2==0 && a[ j ]%2==0)) && a[ i ]>a[ j ])
    14.     {
    15.      int t=a[ i ];
    16.      a[ i ]=a[ j ];
    17.      a[ j ]=t;
    18.     }
    19.    }
    20.   }

    ^_^

  4. #4
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Cách của sourcecrazyfan dùng Bubble Sort chạy khá tốt.
    Còn cái hàm qsort ở trên, nếu như xử lý các quan hệ không lớn hơn, không nhỏ hơn thì ta phải xây dựng như thế nào, bete trả lời giúp với

  5. #5
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Còn cái hàm qsort ở trên, nếu như xử lý các quan hệ không lớn hơn, không nhỏ hơn thì ta phải xây dựng như thế nào, bete trả lời giúp với
    => tui không hiểu câu hỏi cho lắm. Khi mình muốn sắp xếp thứ tự một số phần từ nào đó thì giữa 2 phần tử bất kỳ mình phải luôn xác định được quan hệ (lớn hơn, nhỏ hơn, hay bằng). Bạn có thể cho 1 ví dụ được hay không ?

    -thân

Các đề tài tương tự

  1. Bài tập C bài tập sắp xếp số chẵn tăng dần số lẻ giảm dần trong mảng 1 chiều
    Gửi bởi ronoa trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 07-01-2012, 08:33 AM
  2. Kỹ thuật C Nhập mảng nguyên sao cho chẵn tăng, lẻ giảm
    Gửi bởi lytieu_long550 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 19-08-2011, 07:19 PM
  3. Bài tập C Sắp xếp chẵn lẻ xen kẽ tăng dần
    Gửi bởi Pop trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 13
    Bài viết cuối: 14-08-2011, 05:32 PM
  4. Sắp xếp mảng theo chẵn lẽ và tăng dần trên C?
    Gửi bởi interpol_trinh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 14
    Bài viết cuối: 21-04-2009, 10:11 PM
  5. Sắp xếp ma trận theo thứ tự tăng dần của các số chẵn rồi đến các số lẻ??
    Gửi bởi thanhtung0601 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 02-04-2009, 11:24 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn