[lập trình C++] Sắp xếp mảng

[antonixic]

Mod cho em sống tới hết hôm nay, mai em thi rồi ạh :(
Các bác giúp em giải bài này với ạh:*
Yêu cầu đề bài: cho mảng 1 chiều ngẫu nhiên, sắp xếp sao cho phần tử âm về đầu dãy, 0 về giữa và dương về cuối dãy. Không thay đổi thứ tự các phần tử cùng loại và không dùng mảng phụ.

Ví dụ:
mảng: -3 5 8 0 -4 -2 0 1 0 -5 -1
sau khi xếp: -3 -4 -2 -5 -1 0 0 0 5 8 1

p/s: có bác nào mai thi Học viện Tp HCM hông :byebye:

em có code phần sắp xếp dương về cuối, âm về đầu, các bác xem thử có tí ánh sáng le lói nào không nha :adore:


mảng: -3 5 8 -4 -2 1 -5 -1
sau khi xếp: -3 -4 -2 -5 -1 5 8 1

int check(int k)
{
if(k <0)
return -1;
if(k>0)
return 0;
}
void sapxep(array a, int n)
{
bool flag;
int i=0;
do
{
flag =false;
for(int j=n-1;j>i;j--)
{
if(check(a)<check(a[j-1]))
{
int temp=a;
a=a[j-1];
a[j-1]=temp;
flag=true;
}
}
i++;
}while(flag);
}

[TranTienHung]

google buble sort đi

[duyminh1987]

google buble sort đi
đó là sắp xếp tăng dần, trông cái này giống dùng queue ( hàng đợi ) thì đúng hơn. Mà không cho dùng mảng phụ àh ???!!

[flsfls]

Đơn giản là bạn lập ra 3 mảng con, một mảng lưu phần tử âm, một mảng lưu phần tử 0, một mảng lưu phẩn tử dương sau đó duyệt mảng ban đầu từ trái sang phải, gặp phần tử thuộc loại nào thì tống vào mảng loại ấy. Sau đó ghép 3 mảng lại là đc thôi

[P.E Onimusha]

Đơn giản là bạn lập ra 3 mảng con, một mảng lưu phần tử âm, một mảng lưu phần tử 0, một mảng lưu phẩn tử dương sau đó duyệt mảng ban đầu từ trái sang phải, gặp phần tử thuộc loại nào thì tống vào mảng loại ấy. Sau đó ghép 3 mảng lại là đc thôi
Không dùng mảng phụ :sure:

[antonixic]

google buble sort đi

buble thay đổi thứ tự (vì nó sắp xếp) bác ạh:haha:

đó là sắp xếp tăng dần, trông cái này giống dùng queue ( hàng đợi ) thì đúng hơn. Mà không cho dùng mảng phụ àh ???!!
vâng, ko cho dùng mảng phụ mới chết chứ :tire:
Đơn giản là bạn lập ra 3 mảng con, một mảng lưu phần tử âm, một mảng lưu phần tử 0, một mảng lưu phẩn tử dương sau đó duyệt mảng ban đầu từ trái sang phải, gặp phần tử thuộc loại nào thì tống vào mảng loại ấy. Sau đó ghép 3 mảng lại là đc thôi
không dùng mảng phụ bác ạh:D

[cuoc_song]

Bài này có độ phức tạp n^2, hơi ngán
đi từ đầu đến cuối, gặp thằng nào >=0 thì thêm 1 vòng while típ để tìm thằng nào âm, rồi lưu thằng âm vào 1 biến chờ rồi dịch đoạn đó lên 1 ô, sau đó chèn thằng âm ngược lại dãy, tương tự cho thằng nào = 0. Thế là xong rùi

[Dark_D]

Dùng bubble sort nhưng thay đổi điều kiện if(a[i]>a) thành mấy cái điều kiện (a[i]==0&&a<0) thì đổi chỗ, tương tự làm thêm mấy cái if khác (a[i]<0&&a>0),(a[i]>0&&a=0) nữa thì đc kết quả không nhỉ
Lười làm quá =.=!

[flsfls]

Sory các bác. Em chưa đọc kĩ là ko được dùng mảng phụ

[demonhunt]

Dùng bubble sort nhưng thay đổi điều kiện if(a[i]>a) thành mấy cái điều kiện (a[i]==0&&a<0) thì đổi chỗ, tương tự làm thêm mấy cái if khác (a[i]<0&&a>0),(a[i]>0&&a=0) nữa thì đc kết quả không nhỉ
Lười làm quá =.=!
Bác này đúng nè, đang định post :D:D

[Dark_D]

Dùng bubble sort nhưng thay đổi điều kiện if(a[i]>a) thành mấy cái điều kiện (a[i]==0&&a<0) thì đổi chỗ, tương tự làm thêm mấy cái if khác (a[i]<0&&a>0),(a[i]>0&&a=0) nữa thì đc kết quả không nhỉ
Lười làm quá =.=!

Post xong quay ra coi thấy chủ thớt cũng làm tương tự mình, bác sửa hàm check thành nếu <0 thì -1, lớn hơn 0 thì là 1, bằng 0 thì là 0 rồi hàm if ở vòng lặp thêm mấy cái else xem đi :D

[antonixic]

Post xong quay ra coi thấy chủ thớt cũng làm tương tự mình, bác sửa hàm check thành nếu <0 thì -1, lớn hơn 0 thì là 1, bằng 0 thì là 0 rồi hàm if ở vòng lặp thêm mấy cái else xem đi :D

hêhê, em cũng sửa check trả về -1, 0 ,1. Xong cũng thêm if vào phần do while mà mãi vẫn chưa đc :what:

[flsfls]

code day. em test thu thay co ve dung tuy hoi dai ti
#include
#include

/*
*j luu so phan tu am da duoc sap xep
*/
void main()
{
int array[11] = {-3, 5, 8, 0, -4, -2, 0, 1, 0, -5, -1};
int i, j,k,l, tmp;

j = -1, k = 0;

printf("phan tu mang ban dau\n");
for(i = 0; i<11; i++)
printf("%d ", array[i]);
/* dua cac phan tu am ve dau mang*/
for(i = 0; i<11; i++)
{
if(array[i] < 0)
{
j++;
if(i == j)
{
continue;
}

tmp = array[i];
for(l = i; l>=j; l--)
{

array = array[l-1];
}
array = tmp;
}
}

/* dua cac phan tu 0 ve giua mang*/
for(i = j; i<11; i++)
if(array[i] == 0)
{
j++;
if(i == j)
continue;

tmp = array[i];
for(l = i; l>=j; l--)
array = array[l-1];
array = tmp;
}

/* in ra phan tu mang sau khi sap xep*/
printf("\nphan tu mang sau khi sap xep\n");
for(i = 0; i<11; i++)
printf("%d ", array[i]);
}

ket qua dinh kem

[Dark_D]

Gõ trong C#, máy ko có C++ =.=! Bạn xem thử nhé =.+!

static int check(int a)
{
if (a < 0) return -1;
else if (a == 0) return 0;
else return 1;
}
static void Main(string[] args)
{
int[] a = new int[] {-3,-5,0,-2,5,0,4,-2};
for (int i = 0; i < a.Count(); i++)
for (int j=i;j<a.Count();j++)
if (check(a) < check(a[i]))
{
int temp = a;
a = a[i];
a[i] = temp;
}

for (int i = 0; i < a.Count(); i++) Console.Write(a[i]+" ");
Console.ReadLine();
}

Code bị lỗi ở khúc cuối, số dương đầu tiên bị đẩy xuống cuối chuỗi :ops:

[untouchable]

Ko cần dùng bubble sort đâu, chia công việc 2 phần gom vào 1 lặp là xong. Nhìn lặp nhiều vậy chứ thật ra chạy nhanh vì chỉ số dòng lặp ngoài cùng là i nó vẫn tăng liên tục trong các vòng lặp con nên chạy rất mau (Bạn debug sẽ thấy) .
#include
using namespace std;

void Swap(int &a,int &b)
{
int t=a;
a=b;
b=t;
}
int main()
{
int a[]={-3, 5, 8, 0, -4, -2, 0, 1, 0, -5, -1,6,-1,0,-2,3,-1,-5};
int n=sizeof(a)/sizeof(a[0]);
int i,j;
//Cờ zero chưa bật tức là chưa đến lượt xử lý dồn số 0
bool Zero=false;
for( i=0;i xử lý dồn số âm
{
while(j>i)
{
//a chạy đến khi gặp số không âm đầu tiên
while(a[i]<0) i++;
//j chạy đến khi gặp số âm đầu tiên
while(a>=0) j--;
if(j>i)//2 chỉ số vẫn chưa đụng nhau
Swap(a[i],a);//Swap để dồn số âm đằng sau lên
}
//xong phần số âm thì bật cờ zero bắt đầu dồn số 0 vào tiếp
Zero=true;
}
else
{
//bắt đầu xử lý số 0
while(j>i)
{
//i dừng khi gặp số 0 đầu tiên
while(a[i]==0) i++;
//j dừng khi gặp số dương đầu tiên
while(a>0) j--;
//Nếu 2 chỉ số chưa đụng nhau
if(j>i) Swap(a[i],a);//Swap đề dồn 0 lên trước (phần giữa mảng)
}
//hoàn thành thì break
break;
}
}

return 0;
}

P/s: Code dài quá là do 1 dòng code 1 dòng comment :pudency:

[nopass289]

cái này chắc làm 2 vòng for là xong thôi, cứ đến số nào <0 thì swap nó với số bên phải nó là đc, nghĩ thế, sai các bác đừng ném gạch :)

[rar_hill]

Không cho dùng array thì dùng linked list based queue, quất 3 cái queue là xong xuôi.

[antonixic]

@Các bác ở trên: cảm ơn các bác nhọc công code, em đang test thử :beauty:

Không cho dùng array thì dùng linked list based queue, quất 3 cái queue là xong xuôi.

ax, nói như bác em làm cái struct cũng xong :tire:

[flowerfx]

check it out, easy and understood :boss:

#include "conio.h"
#include
using namespace std;

int main(void)
{
//int n=11;
//int a[11]={-3,5,8,0,-4,-2,0,1,0,-5,-1};
//for(int i=0;i>n;
int * a=new int ;
for(int i=0;i>a[i];}
for(int i=0;i0;i--){
for(int j=i-1;j>=0;j--){if(a[i]==00&&a>0){swap(a[i],a);}}
}
for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<endl;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){if(a[i]==0&&a<0){swap(a[i],a);}}
}
for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<endl;
return 1;

}

caí này vừa chạy vừa debug luôn, sướng vãi ,lại rất đơn giản dễ hiểu :)

[ghk456]

Mềnh là mềnh chưa thử nhưng thấy các bợn làm có swap là nghi lắm, swap sẽ làm mất thứ tự các số cùng loại trong dãy. Cái này phải dồn toa mới được :shot:

[untouchable]

Mềnh là mềnh chưa thử nhưng thấy các bợn làm có swap là nghi lắm, swap sẽ làm mất thứ tự các số cùng loại trong dãy. Cái này phải dồn toa mới được :shot:

Ủa đề có bảo là phải đảm bảo thứ tự các số cùng loại hả :oh::oh::oh:

[flowerfx]

Mềnh là mềnh chưa thử nhưng thấy các bợn làm có swap là nghi lắm, swap sẽ làm mất thứ tự các số cùng loại trong dãy. Cái này phải dồn toa mới được :shot:

tùy nữa bạn, nhưng chạy ra thì đúng , hê hê:rap::rap:

[thienthan0101]

oánh dấu lát nữa xem:beauty:

[ghk456]

Đề ra là phải không thay đổi thứ tự các số cùng loại đới.
Và cái test cũng khá là thâm vì nó để -3 đầu dãy :brick:

[untouchable]

Mới đọc lại đề, đúng là :brick:.
-3 5 8 0 -4 -2 0 1 0 -5 -1
Sau 1 lần swap nó thành
-3 -1 8 0 -4 -2 0 1 0 -5 5
Sai thứ tự mất rồi còn gì :brick:.
Coi bộ ko Swap được mà phải dồn thật rồi.:angry:

[flowerfx]

Mới đọc lại đề, đúng là :brick:.
-3 5 8 0 -4 -2 0 1 0 -5 -1
Sau 1 lần swap nó thành
-3 -1 8 0 -4 -2 0 1 0 -5 5
Sai thứ tự mất rồi còn gì :brick:.
Coi bộ ko Swap được mà phải dồn thật rồi.:angry:

cách mình làm vẫn ra như kết quả mà, vẫn swap ầm ầm có sao đâu :D

[Dark_D]

Đây, dồn toa =.=!
static int check(int a)
{
if (a < 0) return -1;
else if (a == 0) return 0;
else return 1;
}
static void Main(string[] args)
{
int[] a = new int[] {-3,9,-5,0,3,-2,5,-8,0,4,-1,6,1,-2};
for (int i = 0; i < a.Count(); i++)
for (int j = i + 1; j < a.Count(); j++)
if (check(a[i]) > check(a))
{
int temp = a;
for (int k = j; k > i; k--)
{
a = a[k - 1];
}
a[i] = temp;
}
for (int i = 0; i < a.Count(); i++) Console.Write(a[i] + " ");
Console.ReadLine();
}

Test chạy ngon trên VS2010 :matrix:

[antonixic]

ôi, cảm ơn các tình iu nhoá :adore::beauty::*

nhìu code quá :aboom:

[FunnyKids]

Chạy từ đầu tới cuối, cứ số dương thì nhét về cuối (như bạn nào nói ở trên gọi là dồn toa ý). Bài này đơn giản mà :) đâu cần 2 vòng for đâu.

[ghk456]

+1. Đúng rồi, cứ dồn toa là xong. 1 vòng lặp với 1 đoạn dồn toa thế mà cứ phức tạp hóa vấn đề :brick:

[Rosario]

Dồn toa có nhầm hay ko mình ko biết, mỗi tội cách Code của các bạn trẻ nhìn phức tạp vãi đái. Mình già rồi nên lối code cũng đơn giản, với thuật toán của mình thì bài này chả khác gì bài sắp xếp bình thường.

Trước hết là sắp xếp ưu tiên dấu: - trước , rồi đến 0 , rồi đến + . Sau đó là đến thứ tự. Vậy mình làm như sau: tìm giá trị tuyệt đối lớn nhất của mảng, cộng lên với 1 được 1 giá trị gọi là A. Sau đó biến đổi mỗi phần tử của mảng như sau

+)Nếu a[i]>0
a[i] = A*(n-i+1) + giá trị tuyệt đối của a[i]
+)Nếu a[i]=0
a[i]= A*(n-i+1)*(n+2)
+)Nếu a[i] <0
a[i]= A*(n-i+1)*(n+2)*(n+3) + giá trị tuyệt đối của a[i]

Sau khi biến đổi thành như thế thì sắp xếp từ lớn về bé, sau khi sắp xếp rồi thì chuyển lại giá trị cũ là xong (giá trị tuyệt đối ban đầu = giá trị mới mod A, dấu má tự xét nhé).

Edit lại cho các bạn trẻ dễ hiểu hơn. Ý tưởng là 1 số như đề bài có 3 thuộc tính là dấu, vị trí ban đầu và giá trị tuyệt đối. Nếu vậy hãy gắn mỗi thuộc tính với 1 tỉ trọng nào đó sao cho:
Thằng có dấu tốt hơn luôn có giá trị lớn hơn thằng thua dấu nhưng hơn về vị trí
Nếu cùng dấu thằng có vị trí tốt hơn luôn có giá trị lớn hơn thằng có vị trí kém hơn cho dù thằng vị trí kém hơn về giá trị tuyệt đối.