01/10/2018, 17:15

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

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 !

Anh Huynh viết 19:21 ngày 01/10/2018

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é

_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 Thanks bạn.

rogp10 viết 19:22 ngày 01/10/2018

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

sort_heap()

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

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

Trương Tấn Phát viết 19:22 ngày 01/10/2018

Tech Talk – 17 Aug 18

Thuật toán sắp xếp nào là nhanh nhất? | Tech Talk

//Lời nói đầu Thuở còn ngồi trên ghế trường học đại học, khi học môn "Cấu trúc Dữ liệu & Giải thuật" hay là lúc đi phỏng vấn ở 1 công ty ABC, XYZ nào đó, mà cũng có thể đến tận lúc ngồi trà đá bàn luận với anh em đồng nghiệp chuyện nghề, chuyện...

Alone viết 19:17 ngày 01/10/2018

Hacker Noon – 30 Jun 18