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

[hailoc12]

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.

#include "stdio.h"#include "conio.h"#include "stdlib.h"// Khai bao bienint Maxn=1000;int Arr[1001];void initArr(){   int i;   for (i=1;i<=Maxn;++i)      {     Arr[i]= int(rand());      }}void sort(){   int trai=0;   int phai=Maxn+1;   int I=1;   int J, T;   while (I<phai)      {       if ((Arr[I] % 2)==0)      {         T= Arr[I];         Arr[0]=T;         Arr[I]= Arr[trai+1];         J= trai;         while (T<Arr[J])        {           Arr[J+1]= Arr[J];           J--;        }         Arr[J+1]= T;         trai++;         I++;      }       else      {         T= Arr[I];         Arr[Maxn+1]= T;         Arr[I]= Arr[phai-1];         J= phai;         while (T<Arr[J])        {           Arr[J-1]= Arr[J];           J++;        }         Arr[J-1]=T;         phai--;      }      }}void print(){   int i;   printf("\n");   for (i=1;i<Maxn; i++)   {      if (i % 6 == 0) printf("\n%7d ",Arr[i]);      else printf("%7d ",Arr[i]);   }}int main(){ clrscr(); printf("\nBan muon sap xep mang bao nhieu phan tu:");scanf("%d",&Maxn); initArr(); print(); sort(); print(); return 0;}

[bete]

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

[sourcecodecrazyfan]

  int n = 9;  int[] a = {5,3,2,1,6,4,9,8,2};  for (int i=0; i<n-1; i++)  {   for (int j=i+1; j<n; j++)   {    if (a[ i ]%2==1 && a[ j ]%2==0)    {     int t=a[ i ];     a[ i ]=a[ j ];     a[ j ]=t;    }    if (((a[ i ]%2==1 && a[ j ]%2==1) || (a[ i ]%2==0 && a[ j ]%2==0)) && a[ i ]>a[ j ])    {     int t=a[ i ];     a[ i ]=a[ j ];     a[ j ]=t;    }   }  }

^_^

[hailoc12]

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

[bete]

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