Nên dùng hàm sort nào là tốt nhất trong C++

#1

Mọi người cho em hỏi là khi đi thi mà giới hạn thời gian trong 1s thì nên dùng hàm sort nào là tối ưu nhất ạ !
Em đang khá phân vân ở việc nên chọn các hàm sort viết sẵn như sort(),qsort() và sort_heap() hay là nên tự viết function ! Cho em xin lời khuyên với ạ ! Em cảm ơn !

#2

Bình thường thì những sort function mà nó có sẵn lúc nào cũng nhanh nhất. Nhưng mà bây giờ để là cơ hội học tập bạn cứ thử làm như sau nhé :smiley:

_Tạo một array với 1 triệu số integer.

_Sau đó tạo biến
clock_t time_begin, time_end;

_Để
time_begin = clock()

_Dùng mấy function sort mà bạn muốn thử để sort 1 triệu integer.

_Kiếm thời gian mà nó chạy

    time_end = clock();
    double time = time_end - time_begin;

Làm vậy bạn sẽ coi được thời gian mà mấy cái sort function của bạn nhanh hay chậm. Bạn thử làm vậy rồi post kết quả lên đây cho mọi người học hỏi luôn nha :smile: Thanks bạn.

6 Likes
#3

std::sort vì nó nlogn và ko cần phải viết :smiley:

Cái này phải tạo heap std::make_heap trước :smiley: thành ra hai câu lệnh.

Heap sort thực ra kém hơn quick vì bị cache miss :slight_smile: nên load lâu.

3 Likes
#4

3 Likes
#5
2 Likes
#6

Timsort có nhiều tham số (config :smiley: ) ảo lắm, có sẵn (bên Python) thì đỡ, tự viết thì ngồi tune cũng oải.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?