PDA

View Full Version : Code thuật toán quicksort trên C++. Làm sao in số chẵn trước, số lẻ sau?



trungthuan
15-08-2010, 09:37 AM
#include<cstdio>
#include<iostream>
#include<fstream>
using namespace std;

#define FI "1.inp"
#define FO "1.out"

ifstream finp (FI);
ofstream fout (FO);

int n;
int a[20];

void Swap(int &a,int &b)
{
int c=a;
a=b;
b=c;
}

void Output()
{
for(int i=1;i<=n;i++)
{
fout.width(3);
fout<<a[i];
}
fout<<endl;
}

void Tang(int Start,int End)
{
int Key;// chon khoa chot la phan tu dung giua Start va End.
int i=Start,j=End;
if(End>Start)
{
Key=a[(Start+End)/2];
do
{
while(a[i]<Key)
i++;
while(a[j]>Key)
j--;
if(i<j)
Swap(a[i],a[j]);

}while(i<j);
Tang(Start,j-1);
Tang(i+1,End);
}

}


void Giam(int Start,int End)
{
int Key;
int i=Start,j=End;
if(End>Start)
{
Key=a[(Start+End)/2];
do
{
while(a[i]>Key)
i++;
while(a[j]<Key)
j--;
if(i<j)
Swap(a[i],a[j]);

}while(i<j);
Giam(Start,j-1);
Giam(i+1,End);
}

}
void ChanLe(int a[],int n)
{
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]%2!=0 && a[j]%2==0)
{
swap(a[i],a[j]);
i++;
}
}

void main()
{
finp>>n;
for(int i=1;i<=n;i++)
finp>>a[i];

Tang(1,n);
Output();
Giam(1,n);
Output();

ChanLe(a,n);
Output();

finp.close();
fout.close();
}

dùng thuật toán quicksort sửa hàm ChanLe()
in số chẵn trước, số lẻ sau
cần giúp đỡ!!!!!

hunterphu
15-08-2010, 09:49 AM
Nếu dùng quick sort sắp xếp mảng tăng dần ( giảm dần rồi ) thì chỉ cần 2 vòng duyệt để in ra số chẳn lẽ thôi. Độ phức tạp = quicksort O(nlogn)

AlexBlack
16-08-2010, 04:57 PM
hiểu rồi. dùng thuật toán quick sort để sort cái dãy đó chẳn đường chẵn lẻ đường lẽ. chẵn xong rồi lẽ
ví dụ như là
12345
thì sort là
24135

chuong01
16-08-2010, 07:56 PM
Câu lệnh này có ý nghĩa gì bạn?
if(a[i]%2!=0 && a[j]%2==0)



void ChanLe(int a[],int n)
{
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]%2!=0 && a[j]%2==0)
{
swap(a[i],a[j]);
i++;
}
}

vietduc
16-08-2010, 08:32 PM
hiểu rồi. dùng thuật toán quick sort để sort cái dãy đó chẳn đường chẵn lẻ đường lẽ. chẵn xong rồi lẽ
ví dụ như là
12345
thì sort là
24135

như vậy là phải code lại chứ hai hàm bạn trên kia viết cũng không để làm gì đúng không :D

aydada
16-08-2010, 08:54 PM
void ChanLe(int a[],int n)
{
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]%2!=0 && a[j]%2==0)
{
swap(a[i],a[j]);
i++;
}
}
nếu số đằng trước là số lẻ và số sau là số chẵn thì đổi số. Tư tưởng gì lạ vậy bạn ?

trungthuan
17-08-2010, 09:58 AM
uhm, mình viết code theo cảm tính thui, nghĩ sao viết vậy...
ý mình ở trên là viết lại hàm ChanLe theo thuật toán quicksort!!
vd:
1 2 3 4 5
-->2 4 1 3 5
viết theo quicksort như hàm sắp xếp tăng, giảm

thichgihp
17-08-2010, 10:36 AM
Cho em hỏi 1 câu ngoài lề nhé:


void Swap(int &a,int &b)
{
int c=a;
a=b;
b=c;
}

cái đoạn code này lạ lạ nhỉ bác nào giải thích tường tận hộ em cái. Nó hình như tác dụng lên biến trực tiếp thì phải,em hay dùng kiểu con trỏ như thế này:



void Swap(int* a,int* b)
{
int c=*a;
*a=*b;
*b=c;
}

aydada
17-08-2010, 11:43 PM
code đầu tiên thay đổi giá trị của 2 biến a và b
còn code thứ 2 của bạn thì nó chỉ thay đổi địa chỉ mà con trỏ trỏ đến thôi