Hỏi về 3 phương pháp sắp xếp cơ bản

[fire_dragon14988]

Trong 3 phương pháp sắp xếp cơ bản (chọn trực tiếp, chèn trực tiếp, nổi bọt) phương pháp nào thực hiện sắp xếp nhanh nhất với một dãy đã có thứ tự ? Giải thích?

[huynguyen]

3 phương pháp có tốc độ như nhau, ko ai nhanh hơn ai, chỉ có ý tưởng là khác nhau tôi.

[fire_dragon14988]

Tại sạo vậy bạn?

[DKhanh]

quick sort nhanh nhất, sau đến shell short

[meoconlongvang]

quick sort chạy "nhanh" bằng selection sort nếu mảng đã được sắp xếp. Mình nghĩ chèn trực tiếp là nhanh nhất trong trường hợp mảng đã sắp xếp.

[zkday2686]

3 phương pháp có tốc độ như nhau, ko ai nhanh hơn ai, chỉ có ý tưởng là khác nhau tôi.

bạn nói vậy theo mình chưa được chính xác lắm. vì các thuật toán sắp xếp nếu nó có tốc độ như nhau thì mà chỉ khác nhau về giải thuật thôi thì người ta tìm ra nhiều thuật toán sắp xếp để làm gì?

theo mình thì 3 thuật toán trên thì tốc độ sắp xếp của nó phụ thuộc vào tính chất của mảng mà bạn cần sắp xếp.
vd: nếu mảng đã gần có thứ tự thì dùng phương pháp chèn trực tiếp (InsertionSort) là nhanh nhất.

vì nó sẽ giới hạn được các câu lệnh gán và số lần so sánh khi thực hiện thuật toán(do ý tưởng của thuật toán là tìm cách chèn phần tử đang xét vào vị trí thích hợp trong đoạn [của mảng cần sắp] đã có thứ tự).
cho nên nếu mảng đã gần có thứ tự cần sắp xếp thì chúng ta sẽ tốn ít chi phí để tìm và chèn phần tử hơn.

[DKhanh]

vd: nếu mảng đã gần có thứ tự thì dùng phương pháp chèn trực tiếp (InsertionSort) là nhanh nhất.

vì nó sẽ giới hạn được các câu lệnh gán và số lần so sánh khi thực hiện thuật toán(do ý tưởng của thuật toán là tìm cách chèn phần tử đang xét vào vị trí thích hợp trong đoạn [của mảng cần sắp] đã có thứ tự).
cho nên nếu mảng đã gần có thứ tự cần sắp xếp thì chúng ta sẽ tốn ít chi phí để tìm và chèn phần tử hơn.

Dẫu biết là thế, nhưng làm sao biết tính chất mảng này nọ để chọn thuật toán nào hợp lý. Ngay từ đầu bạn chọn thuật toán nào, mình chọn quicksort.

[meoconlongvang]

Trong 3 phương pháp sắp xếp cơ bản (chọn trực tiếp, chèn trực tiếp, nổi bọt) phương pháp nào thực hiện sắp xếp nhanh nhất với một dãy đã có thứ tự ? Giải thích?

Thì ngay từ đầu khổ chủ đã đặt tình huống là mảng đã sắp xếp rùi mà.

[DKhanh]

Thì ngay từ đầu khổ chủ đã đặt tình huống là mảng đã sắp xếp rùi mà.

Nếu biết đã sắp xếp rồi còn sắp chi nữa )

[meoconlongvang]

Nếu biết đã sắp xếp rồi còn sắp chi nữa )

Ý của bạn ấy là muốn thêm một phần tử vào mảng đã sắp xếp sẵn.