Sắp xếp mảng,phần tử chẵn bên trái tăng dần, lẻ bên phải giảm dần

TienDatPC · October 5, 2015, 3:54am

Bài toán của em như sau
Cho 1 mảng a[n]
Sắp xếp lại mảng sao cho các phần tử chãn ở bên trái theo chiều tăng, phần tử lẻ ở bên phải theo chiều giảm.
B1: Đếm xem mảng có bn phần tử chẵn, lẻ
B2: Duyệt mảng nếu phần tử chẵn thì đưa về đầu mảng,nếu lẻ thì đưa về cuối
B3: Sắp xếp các số chẵn
B4 Sắp các số lẻ
B5 in ra
Ngoài cách trên thì có thể dùng mảng phụ để lưu trữ.
Tuy nhiên e thấy khá là dài dòng, mặc dù code nhìn dễ hiểu.
Xin hỏi các bác đã từng làm qua có ý tưởng gì không? Có cách nào code ngắn gọn tối ưu hơn hay không?

Rookie · October 5, 2015, 5:48pm

#include "stdio.h"
#include "time.h"
#include "stdlib.h"
main()
{
    int list[100];
    int min=0,tmp,j,i,n,chan=0,k=0;
    scanf("%d",&n);
    srand(time(NULL));
    for(int i=0;i<n;i++)
    {
        list[i]=rand()%20+1;
    }
    for(int i=0; i<n; i++)
    {
        if(list[i]%2==0)
        {
            k=i;
            for( j=0; j<n; j++)
            {
                tmp=list[k]; list[k]=list[j]; list[j]=tmp;
            }
        i--;
        }
    };
    for(int i=0; i<n; i++)
    {
        if(list[i]%2==0)
        {
        min=i;
        for( j=i+1; j<n; j++)
            if(list[min]>list[j]&&list[j]%2==0) min=j;
        tmp=list[min]; list[min]=list[i]; list[i]=tmp;
        }
        else
        {
        min=i;
        for( j=i+1; j<n; j++)
            if(list[min]<list[j]&&list[j]%2!=0) min=j;
        tmp=list[min]; list[min]=list[i]; list[i]=tmp;
        }

    };
    for(int i=0; i<n; i++)
    {
        printf("\n%d",list[i]);
    };
// code by LNV
}

Cách sắp xếp thì có nhiều cái hay hơn mình lấy đại cách này (Đừng quan tâm đến nó.)

  min=i;
    for( j=i+1; j<n; j++)
        if(list[min]>=list[j]) min=j;
    tmp=list[min]; list[min]=list[i]; list[i]=tmp;

ko biết tối ưu chưa. ai tối ưu hơn thì chia sẻ nhé

Nguyen_Dong · October 5, 2015, 5:31pm

Thực ra bạn có thể dùng ý tưởng của quicksort, ko cần dùng mảng phụ.

Duyệt từ 1, giả sử đến i thì gặp số lẻ đầu tiên
Duyệt từ n, giả sử đến j gặp số chẵn đầu tiên
swap(i, j) rồi làm tiếp. Sau đó sort 2 bên thôi