Tại sao phải học nhiều giải thuật sắp xếp?

Chỉ cần Quick Sort và Buble Sort là đủ rồi bạn nha,
Phần lớn các ngôn ngữ lập trình đều hỗ trợ hàm sort.
Trên lớp học nhiều cho vui thế thôi.

em học cái này chủ yếu để rèn luyện tư duy lập trình.
Sau này nếu em không đi theo chuyên ngành về khoa học máy tính thì thuật toán sắp xếp ít được sử dụng.

Học nhiều giải thuật để cải thiện tư duy về thuật toán.

• Selection sort, insertion sort, buble sort là cách tiếp cận “ngây thơ”, mô phỏng cách làm của con người.
• Buble sort Shaker sort cách tiếp cận cải tiến so với insertion sort buble sort. Đính chính theo lời @tntxtnt
• Đến những thuật toán như merge sort, quick sort bắt đầu thể hiện cách nhìn khác của người lập trình, cụ thể là phương pháp chia để trị. Merge sort đạt độ phức tạp tối thiểu có thể đạt được O(nlogn) đối với giải thuật sử dụng phép so sánh.
• Và rồi cuối cùng đó là vượt qua giới hạn khi nghĩ xa hơn, thay đổi hoàn toàn cách tiếp cận. Counting sort, bucket sort và Radix sort đạt tốc độ gần với tuyến tính O(n).

-> Nó thể hiện những bước cải tiến khi phát triển thuật toán. Ban đầu là một cách tiếp cận đơn giản, chạy được làm nền để so sánh, sau đó là cải tiến hoặc thay đổi hoàn toàn, áp dụng tư tưởng riêng trong lập trình hoặc đặc điểm riêng của bài toán, của máy tính.
Mục đính chính khi dạy các giải thuật so sánh là tư duy phát triển và đánh giá thuật toán.

Mình có cái link về các trường hợp cụ thể cho từng thuật toán sắp xếp nè

When is each sorting algorithm used?

để tăng cường sự rèn luyện cho não, nghề lập trình đòi hỏi cái đầu của lập trình viên phải xử lý thông tin, tính toán và phản xạ nhanh.

nhớ lại năm kia học Tin học đại cương, thuật toán sắp xếp kiểu selection sort… hôm sau cô giáo hỏi mình quên mất, chả biết thế nào mà lại nghĩ ra cái thuật toán gần giống Bubble sort cô giáo cứ bảo sai mà ko tìm đc trường hợp nào sai cả hôm sau lên lớp cô mới bảo là thuật toán chạy đúng. hì hì

Học giải thuật rèn tư duy mà nên biết nên biết

Buble sort là một cách tiếp cận cải tiến so với insertion sort,

“cải tiến” tức là tìm ra sau? hay là tốt hơn? Ko có tốt hơn nhá. Cải lùi so với insertion sort thì đúng hơn.

“[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn’t really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!”

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0.
Pages 106–110 of section 5.2.2: Sorting by Exchanging.

bubble sort là cực kì tệ, ko ai xài/dạy nữa. Insertion sort còn được xài chung với quick sort khi còn ít phần tử.
.
.
.
.
phải biết insertion sort đầu tiên, rồi merge sort rồi quick sort. Với sort cần so sánh thì phải hiểu tại sao ko thể có hàm sort nhanh/tốt hơn O(nlogn). Với sort không cần so sánh thì biết thêm radix sort nữa là đủ rồi (thế quái nào mà sắp xếp ko cần so sánh?? )
.
.
.
.
Coursera có 2 lớp intro giải thuật của Princeton rất hay:

Coursera

Coursera | Online Courses From Top Universities. Join for Free

1000+ courses from schools like Stanford and Yale - no application required. Build career skills in data science, computer science, business, and more.

Coursera

Coursera | Online Courses From Top Universities. Join for Free

1000+ courses from schools like Stanford and Yale - no application required. Build career skills in data science, computer science, business, and more.

“cải tiến” tức là tìm ra sau? hay là tốt hơn? Ko có tốt hơn nhá. Cải lùi so với insertion sort thì đúng hơn.

Uhm mình nhầm, đã đính chính ^^

Mọi người biết bubble sort vì trong sách Việt Nam vẫn dạy
Biết nó tồi nhưng có nó để mà học cách phân tích nó tồi chỗ nào, tại sao lại phải tìm kiếm cách khác hiệu quả hơn. Cái này mới là giá trị thật Bubble sort

Mọi người cố gắng theo 2 khóa Algorithm Coursera bạn này giới thiệu, năm nào cũng mở lớp.

Mình đã viết lại mấy thuật toán sắp sếp theo cách mình nghĩ là dễ hiểu. Bạn có thể đọc ở đây : http://chingovan.blogspot.com/search/label/algorithms