Sắp Xếp Mảng Có Giá Trị Lớn dùng thuật toán gì ?

English | Vietnamese

Rules

Main Forum

Portal

Member Listing

Statistics

Search

Reading Room
[Register]

Login [ | https ]

Forum Index

Thảo luận hệ điều hành Windows

Sắp Xếp Mảng Có Giá Trị Lớn dùng thuật toán gì ?

[Programming] Sắp Xếp Mảng Có Giá Trị Lớn dùng thuật toán gì ?	17/03/2007 01:41:36 (+0700) \| #1 \| 47207

channhua
Elite Member

Joined: 18/07/2003 04:49:28
Messages: 338
Offline

Tôi muốn sắp xếp mảng a[i] với i<=40000 và giá trị mỗi a[i] <=30000. ; i là các số tự nhiên

Với giá trị lớn như vậy, dùng thuật toán gì tối ưu nhất, ít tốn bộ nhớ trong nhất và không sử dụng bộ nhớ ngoài.

cho xét 2 trường hợp: a[i] đều khác nhau và trường hợp các a[i] có thể trung nhau smilie

[Question] Sắp Xếp Mảng Có Giá Trị Lớn dùng thuật toán gì ?	17/03/2007 04:54:47 (+0700) \| #2 \| 47242

iruy
Member

Joined: 16/08/2006 19:58:47
Messages: 15
Location: I dont know
Offline

channhua wrote:

Tôi muốn sắp xếp mảng a[i] với i<=40000 và giá trị mỗi a[i] <=30000. ; i là các số tự nhiên

Với giá trị lớn như vậy, dùng thuật toán gì tối ưu nhất, ít tốn bộ nhớ trong nhất và không sử dụng bộ nhớ ngoài.

cho xét 2 trường hợp: a[i] đều khác nhau và trường hợp các a[i] có thể trung nhau

Sắp xếp hay dùng thuật toán gì thì số phần tử, giá trị cũng không thay đổi nhiều vì vậy nó cũng chiếm trừng ấy bộ nhớ mà thôi. Đúng không nhỉ ? smilie

[Question] Sắp Xếp Mảng Có Giá Trị Lớn dùng thuật toán gì ?	17/03/2007 06:46:04 (+0700) \| #3 \| 47270

delua
Locked

Joined: 28/12/2006 00:48:39
Messages: 102
Offline

channhua wrote:

Tôi muốn sắp xếp mảng a[i] với i<=40000 và giá trị mỗi a[i] <=30000. ; i là các số tự nhiên

Với giá trị lớn như vậy, dùng thuật toán gì tối ưu nhất, ít tốn bộ nhớ trong nhất và không sử dụng bộ nhớ ngoài.

cho xét 2 trường hợp: a[i] đều khác nhau và trường hợp các a[i] có thể trung nhau

Câu hỏi này bác channhua đã hỏi bên DSAP và đã được bác NBThanh "tiếp chiêu" rồi.Nên có lẽ anh em không cần "múa rìu qua mắt thợ" nữa smilie

)

[Question] Sắp Xếp Mảng Có Giá Trị Lớn dùng thuật toán gì ?	17/03/2007 06:54:10 (+0700) \| #4 \| 47272

hoangmac
Member

Joined: 08/07/2006 15:53:56
Messages: 50
Location: hcm
Offline

channhua wrote:

Tôi muốn sắp xếp mảng a[i] với i<=40000 và giá trị mỗi a[i] <=30000. ; i là các số tự nhiên

Với giá trị lớn như vậy, dùng thuật toán gì tối ưu nhất, ít tốn bộ nhớ trong nhất và không sử dụng bộ nhớ ngoài.

cho xét 2 trường hợp: a[i] đều khác nhau và trường hợp các a[i] có thể trung nhau

giải thuật ko liên quan tớ bộ nhớ, giải thuật chỉ liên quan tớ tốc độ giải quyết bài toán nhanh hay chậm.

giải thuật tốt->1/100s thì sx xong. giải thuật ko tốt -> ctrình chạy x năm sẽ xong smilie

)

bồ có thể khai báo int a[40.000]// một mảng a có 40.000 có int
nhưng bồ ko thể khi báo int a=40.000//vì max của kiểu int là 32.687 hình như là vậy

khai báo biến mới liên quan đến bộ nhớ.

[Question] Sắp Xếp Mảng Có Giá Trị Lớn dùng thuật toán gì ?	17/03/2007 12:35:55 (+0700) \| #5 \| 47386

channhua
Elite Member

Joined: 18/07/2003 04:49:28
Messages: 338
Offline

bạn delua tinh mắt ghê, anh Nbthanh cũng trả lời rồi, nhưng lúc đầu cũng tính toán vậy thấy mới có 2 bytes đâu gì đáng kể, nhưng đề bài lại yêu cầu thế, nếu nó không hỏi đoạn sau thì chắc dùng sort nào cũng được, mà dùng radix sort cho số lớn tôi thấy lợi thế hơn

[Question] Re: Sắp Xếp Mảng Có Giá Trị Lớn dùng thuật toán gì ?	18/03/2007 15:59:13 (+0700) \| #6 \| 47602

facialz
Elite Member

Joined: 20/07/2004 03:48:17
Messages: 197
Location: HoChiMinh city
Offline

Có những số dù nhỏ hơn 30 000 vẫn không thể biểu diễn bằng 2 byte.

Ví dụ: -1 000 000.

Go to:

Users currently in here
1 Anonymous