Chỉ mình về cách dồn mảng ^^

[yoyo89312]

Các bạn gợi ý dùm mình thuật toán nha

Giả sử có một mảng int gồm n số, hãy viết hàm làm nhiệm vụ dồn các số lẻ lên đầu mảng, các số chẵn xuống cuối mảng.

Thank nhiều lắm ^^

[NT_OnlyLove]

Có cần dồn theo thứ tự không nhỉ?
Nếu không thì bạn có thể hình dung như sau:

1. Tạo hai biến lưu trữ chỉ số đầu và cuối
2. Dùng vòng lặp while( đầu != cuối )
3. Trong vòng lặp xác định phần tử thứ đầu :
a. Nếu lẻ thì đầu ++ để nó chạy đến phần tử là chẵn nếu có
b. Ngược lại là chẵn rùi thì tiến hành while( đầu != cuối)
b1. Nếu phần tử thứ cuối mà chẵn thì cuối-- để nó chạy đến phần tử là lẻ nếu có
b2. Ngược lại thì hoán đổi hai phần tử thứ đầu và cuối.

Nếu dồn mà vẫn giữ thứ tự thì bạn duyệt từ cuối về đầu, nếu gặp lẻ thì lưu trữ vị trí của nó. Sau đó băng qua các số lẻ phía trước nó đến khi gặp phần tử là chẵn hoặc về đầu. Nếu có phần tử là chẵn thì tiến hành hoán đổi từ đó đến vị trí lưu trữ và cập nhật lại các vị trí lưu trữ.
Nói chung bạn viết một cái ma trận ra giấy rồi nghĩ xem nó như thế nào.
Còn đây là một code mà trường hợp trên mình nói tới, bạn tham khảo chút.
Còn trường hợp 2 bạn suy nghĩ xem sao nha:

#include <iostream>using namespace std; void Swap(int &_iParam1, int &_iParam2){    int _iTemp;    _iTemp=_iParam1;    _iParam1=_iParam2;    _iParam2=_iTemp;} void Printer(int Matrix[],int _iLeng){    for(int _iIndex=0; _iIndex<_iLeng; _iIndex++)        cout<<"  "<<Matrix[_iIndex];    cout<<endl;} int main(){    int Matrix[10];    for(int _iIndex=0;_iIndex<10;_iIndex++)     {        cout<<endl            <<"Matrix["<<_iIndex<<"]=";            cin>>Matrix[_iIndex];    }     system("cls");    cout<<"Truoc khi hoan doi"<<endl;     Printer(Matrix,10);     int _iTop=0;    int _iTail=9;     while(_iTop != _iTail)    {        if(Matrix[_iTop] % 2 != 0 ) // le            _iTop++;        else        {            while(_iTop != _iTail)                if(Matrix[_iTail] % 2 ==0 )// chan                    _iTail--;                else                {                    Swap(Matrix[_iTop],Matrix[_iTail]);                    break;                }        }    }     cout<<"Sau khi hoan doi:"<<endl;    Printer(Matrix,10);    cout<<endl;    system("Pause");}

[Chautieu47]

Cách của tui là thế này: bạn duyệt các phần tử trong mảng từ trái sang phải bằng cách dùng vòng for cho i chạy từ 0 đến N - 2. Nếu phần tử a[i] chẵn thì dùng vòng for thứ 2 cho j chạy từ i + 1 đến N - 1 (Nghĩa là xét các phần từ đứng sau a[i]) nếu gặp a[j] lẻ thì đổi chổ a[j] với a[i], lúc này số lẻ lên trên, số chẵn xuống dưới. Cứ thế làm tiếp tục đến hết mảng.

void donchle(int a[], int N){    int i, j, t;     for(i = 0; i < N - 1; i++)        if(!(a[i] % 2)) {            for(j = i + 1; j < N; j++)                if(a[j] % 2)    {                    t = a[i]; a[i] = a[j]; a[j] = t;                    break;                }        }}

[yoyo89312]

Cách của tui là thế này: bạn duyệt các phần tử trong mảng từ trái sang phải bằng cách dùng vòng for cho i chạy từ 0 đến N - 2. Nếu phần tử a[i] chẵn thì dùng vòng for thứ 2 cho j chạy từ i + 1 đến N - 1 (Nghĩa là xét các phần từ đứng sau a[i]) nếu gặp a[j] lẻ thì đổi chổ a[j] với a[i], lúc này số lẻ lên trên, số chẵn xuống dưới. Cứ thế làm tiếp tục đến hết mảng.

void donchle(int a[], int N)
{
	int i, j, t;

	for(i = 0; i < N - 1; i++)
		if(!(a[i] % 2))
		{
			for(j = i + 1; j < N; j++)
				if(a[j] % 2)	{
					t = a[i]; a[i] = a[j]; a[j] = t; break;
				}
		}
}

Cách của bạn hay lắm, cám ơn nhiều nhá.
Mà nếu mình muốn sắp xếp theo thứ tự tăng dần nữa thì phải thêm đoạn code nào nữa?

^^

[NT_OnlyLove]

Thử thay

i=j+1;

vào trước break xem sao nha.

[Chautieu47]

Muốn sắp nó tăng dần nữa thì có cách là sắp tăng những số lẻ, xong rồi sắp tăng những số chẵn. Như vậy thì mình cần biết là tới vị trí nào thì kết thúc các số lẻ và qua số chẵn. Có thể làm như sau:

for(k = 0; a[k] % 2 != 0; k++);
/* Lam xong dong tren thi k la vi tri 
phan tu chan dau tien trong mang */

Sau đó mình viết một hàm sắp tăng như sau

void saptang(int a[], int d, int c)
{
	int i, j, t;

	for(i = d; i < c - 1; i++)	{
		for(j = i + 1; j < c; j++)
			if(a[j] < a[i])	{
				t = a[i]; a[i] = a[j]; a[j] = t;
			}
	}
}

Hàm saptang này dùng để sắp tăng 1 phần mảng từ vị trí d đến c - 1.
Vậy là xong bây giờ chỉ việc gọi các hàm để nó sắp tăng dần theo như sau:

donchle(a, N);   // don le len dau, chan xuong duoi
for(k = 0; a[k] % 2 != 0; k++); // lay vtri k la vtri ket thuc so le va qua so chan
saptang(a, 0, k);   // sap tang so le
saptang(a, k, N);   // sap tang so chan

Cách này thì đơn giản, dễ hiểu, nhưng mà hơi bị dài. Không biết còn cách nào hay hơn không.

[yoyo89312]

Mình vừa hỏi ông thầy, ông thầy chỉ mình cách làm như sau nè bạn:

Sau khi thực hiện công việc dồn số lẻ lên đầu mảng và số chẵn xuống cuối mảng, mình thực hiện hàm sắp xếp như sau

for(int i=0;i<n-1;i++)    for(int j=i+1;j<n;j++)        if(((a[i]%2==0) && (a[j]%2==0) ) || ((a[i]%2==1) && (a[j]%2==1) ) && a[i]>a[j])        {            int tam=a[i]; a[i]=a[j]; a[j]=tam;        }

[Chautieu47]

Hì! thay vì chia ra sắp tăng số lẻ, số chẵn thì cái điều kiện trên đã làm việc này luôn rồi. ^_^
Thank for your sharing.

[yoyo89312]

Thử thay

vào trước break xem sao nha.

Thêm đoạn đó vào có tác dụng gì thế bạn?

[xinchigiao]

Mình vừa hỏi ông thầy, ông thầy chỉ mình cách làm như sau nè bạn:

Sau khi thực hiện công việc dồn số lẻ lên đầu mảng và số chẵn xuống cuối mảng, mình thực hiện hàm sắp xếp như sau

for(int i=0;i<n-1;i++)    for(int j=i+1;j<n;j++)        if(((a[i]%2==0) && (a[j]%2==0) ) || ((a[i]%2==1) && (a[j]%2==1) ) && a[i]>a[j])        {            int tam=a[i]; a[i]=a[j]; a[j]=tam;        }

làm thế cũng tốt nhưng nếu chia ra (đổi trước sắp sau) thì thêm có mấy dòng mà dễ hiểu,dễ nhớ.
----------------------------------------------------
he he