cho em hỏi thuật toán sắp xếp stable sort là gì ak
Và các thuật toán merge sort hay quíck sort có phải là stable sort hay không
Em xin cảm ơn
Sắp xếp stable sort
Stable sort nghĩa là 2 phần tử đc coi là “bằng nhau” (mình dùng từ bằng nhau khá là rộng ở đây) giữ nguyên thứ tự trước và sau khi sort.
Merge sort thường là stable (cũng có thể không stable, tùy cách viết bước merge), quick sort thì tùy vào cách viết phần partition có stable không.
Ví dụ là khi bạn xắp sếp danh sách người bằng tên theo thứ tự abc, rồi sắp xếp bằng tuổi theo thứ tự nhỏ đến lớn, sau khi sắp xếp thứ tự tuổi, những người cùng tuổi vẫn được sắp xếp bằng tên theo thứ tự abc
2 Likes
nó được dùng trong trường hợp nào ak .
Anh giải thích lại cho em với em cũng chưa hiểu lắm
Một struct chỉ có thể có một key dưới một thứ tự (toàn phần) <= nhất định. (có thể có nhiều key khả dĩ, nhưng key định nghĩa thứ tự). Hay ta nói a <= b <=> key(a) <= key(b).
Một lí do là để dãy đã sắp xếp là duy nhất. Unstable thì có nhiều đáp án. Nghĩa là khi các key bằng nhau thì thứ tự tương đối trong dãy chưa sắp xếp được thể hiện trong dãy đã sắp xếp, nên là duy nhất.
Lí do quan trọng nhất là để bảo toàn thứ tự thời gian.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?