Cấu trúc dữ liệu và giải thuật 1 - Sorting algorithm show case.

[truonganpn]

Cho các bạn nào đang học môn CTLD&GT1. Đây là một số giải thuật sắp xếp tôi cài đặt thử và có tính thời gian chạy cho từng trường hợp. Cho các bạn nào chưa cài đặt được tất cả thuật toán có thể có một cái nhìn hình tượng hơn về sự chênh lệch trong độ phức tạp dẫn tới khác biệt thế nào trong thời gian thực thi. Với một mảng 200.000.000 số nguyên chương trình sẽ cho output dạng như thế này:

Quick sort 	took 232262606 swap	 57782172 comparision
sorted, quick sort 	took 5.27 seconds
Heap sort 	took 470497389 swap	 912176610 comparision
sorted, heap sort 	took 12.94 seconds
Merge sort 	took 166666666 swap	 520000000 comparision
sorted, merge sort 	took 5.78 seconds

Process returned 0 (0x0)   execution time : 26.980 s
Press ENTER to continue.

Cách cài đặt các thuật toán này vẫn chưa phải là trau chuốt, một số thuật toán vẫn chưa được cài đặt (natural merge sort, shaker sort, v.v..) và không loại trừ một số thuật toán cài đặt bị bug. Hoan nghênh bạn nào có thể tiếp tục trau chuốt, tìm lỗi và bổ sung chương trình cho mọi người tham khảo. Các thắc mắc (nếu có) về chương trinfhay về kiến thức môn CTDL&GT 1 nói chung có thể đặt tại đây.

Chương trình code bằng ANSI-C và đã test với GNU C compiler 4.7: $ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-unknown-linux-gnu/4.7.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: /build/src/gcc-4.7-20120324/configure --prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/ --enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-shared --enable-threads=posix --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-clocale=gnu --disable-libstdcxx-pch --enable-libstdcxx-time --enable-gnu-unique-object --enable-linker-build-id --with-ppl --enable-cloog-backend=isl --enable-lto --enable-gold --enable-ld=default --enable-plugin --with-plugin-ld=ld.gold --with-linker-hash-style=gnu --disable-multilib --disable-libssp --disable-build-with-cxx --disable-build-poststage1-with-cxx --enable-checking=release
Thread model: posix
gcc version 4.7.0 20120324 (prerelease) (GCC)

[11520447]

Đây là bài e làm (đình kèm)
làm sao để gọi lại mảng ban đầu trong mỗi lần test, e làm 3 hàm sắp xếp, thì do 1 hàm đầu nó sắp rồi nên 2 hàm sau nó sắp thì mất time (0.000)
Và e cũng ko biết đơn vị của nó là giây hay phút nữa.
e thấy tương đồng ở chỗ:
CLOCKS_PER_SEC / CLK_TCK
time_t / clock_t
nó chỉ khác nhau thư viện hay sao ạ
và tại sao fai chia cho hằng số CLOCKS_PER_SEC / CLK_TCK

[truonganpn]

Đây là bài e làm (đình kèm)
làm sao để gọi lại mảng ban đầu trong mỗi lần test, e làm 3 hàm sắp xếp, thì do 1 hàm đầu nó sắp rồi nên 2 hàm sau nó sắp thì mất time (0.000)
Và e cũng ko biết đơn vị của nó là giây hay phút nữa.
e thấy tương đồng ở chỗ:
CLOCKS_PER_SEC / CLK_TCK
time_t / clock_t
nó chỉ khác nhau thư viện hay sao ạ
và tại sao fai chia cho hằng số CLOCKS_PER_SEC / CLK_TCK

Chào em.
Nếu xem bài giải của tôi thì em sẽ thấy tôi không có sắp xếp trên mảng ban đầu mà sắp xếp một mảng copy từ đó ra.

Việc chia cho hằng số COCKS_PER_SEC tôi có giải thích trên lớp thực hành, em có một khoảng thời gian đo bằng số clocks của hệ thống, để đổi số clocks ra giây thì ta tiến hành chia nó cho hằng "Số clocks trong mỗi giây".

Còn hằng số CLK_TCK đã cũ và hiện nay người ta không dùng nữa, tôi hơi tò mò không biết em xem được nó trong tài liệu nào? Vả lại trong bài của em khi chia để đổi ra giây em chưa thực hiện ép kiểu nên kết quả sẽ có sai số.

[11520447]

Chào Thầy,
Thú thật là ban đầu nhìn bài thầy e ko hiểu ji hết (do e ko thực hành lớp thầy)
e tìm trên mạng cách đo time thì mới bik dc hằng số CLK_TCK
từ đó nhìn lại mới hiểu bài thầy .
e chỉ hiểu thầy dùng mảng động, nên đoạn này e cũng mơ hồ

int *b = (int*)malloc(sizeof(int)*n);
	memcpy(b,a,sizeof(int)*n);

Thank thầy