Thuật toán tốt nhất để sắp xếp các bài kiểm tra

Question

Tôi là một học sinh lớp cho một khóa học thống kê và có một loạt bài tập về nhà giấy được giao cho tôi theo thứ tự ngẫu nhiên. Một phần công việc của tôi là sắp xếp chúng theo thứ tự bảng chữ cái. Tôi đã sử dụng một phương pháp tương tự như sắp xếp nhanh, nhưng các học sinh khác đã sử dụng các phương pháp khác nhau. Tôi muốn một phương pháp phân loại hiệu quả, với sự biện minh, vì khi tôi có một "lớn" số của các kỳ thi, với sự biện minh được cung cấp .. Dưới đây là một số chi tiết cụ thể tôi đã thừa hưởng:

• Tôi có một danh sách chứa một danh sách theo thứ tự abc của tất cả các tên tôi sẽ thấy.
• Tôi không quan tâm đến việc đặt tên được sắp xếp theo thứ tự chữ cái hơn là chữ cái đầu tiên. Ví dụ, tôi ổn nếu "Smith, John" xuất hiện trước "Salk, Jonas".
• Tôi sẽ không bao giờ phải sắp xếp hơn 300 đối tượng.

Phương pháp của tôi cho đến nay là tìm thư trung vị cuối cùng (ví dụ: nếu có 60 giấy tờ, hãy chọn chữ cái cuối cùng tương ứng với người thứ 30) của danh sách lớp, coi nó là điểm pivot, và đặt tất cả các chữ cái ở trên trung vị trong một đống, và tất cả các chữ cái dưới đây trong một cái khác. Nếu một lá thư giống như chữ cái trung bình, tôi đặt nó vào trong cái cọc trung bình. Bây giờ tôi làm điều tương tự trên các cọc trên/dưới trung bình. Khi các cọc đủ nhỏ để chỉ có ba hoặc bốn chữ cái trong một chồng, tôi tạo một ngăn xếp cho mỗi chữ cái, sau đó gấp các ngăn xếp vào ngăn xếp chính, theo thứ tự bảng chữ cái.

Có bất kỳ thuật toán nào được thiết kế riêng để sắp xếp theo thứ tự bảng chữ cái hoặc phương pháp nào hiệu quả hơn phương pháp của tôi không? Một phương pháp có vẻ ổn thỏa là tạo một ngăn xếp cho mỗi chữ cái (26 đống, trường hợp xấu nhất), nhưng điều này tiêu tốn quá nhiều không gian đến mức không thể thực hiện được cho một bàn làm việc.

Answer 1

Tôi đang xem xét một số trang web đang nói về thuật toán để con người sử dụng và một trang mà tôi thấy đang thực hiện loại sắp xếp, nơi bạn đặt nó vào trong cọc bằng cách đặt nó trực tiếp đúng thứ tự nên được.

Tính không hiệu quả của điều này có thể là phải quét qua đống để tìm vị trí khi cọc lớn hơn, vì vậy tôi nghĩ rằng để điều chỉnh, bạn có thể thêm thẻ hoặc thứ gì đó hoạt động như một chỉ mục cho một vị trí cụ thể theo thứ tự chữ cái. Vì bạn không quan tâm đến thứ tự chữ cái ngoài chữ cái đầu tiên, điều này về cơ bản sẽ đặt chi phí chèn của bạn tại O (1)

Đây chỉ là suy nghĩ của tôi khi nghĩ về nó, vì vậy tôi không thực sự cố gắng bản thân nó, và tôi không thể nói về việc nó có hiệu quả như thế nào với các cọc đủ lớn. Nhưng tôi nghĩ rằng nó sẽ hoạt động khá tốt, vì các thẻ sẽ cho phép bạn truy cập nhanh đến vị trí bạn muốn chèn.

Answer 2

Quicksort có lẽ không phải là tốt nhất vì hiệu quả của nó phụ thuộc vào lựa chọn trục xoay. Dù sao, chỉ với 300 bài kiểm tra, điều tôi muốn làm là tạo 26 cọc (một cho mỗi chữ cái) và chỉ thực hiện một lần cho tất cả các kỳ thi đặt chúng vào các cọc thích hợp

Answer 3

Đoạn cuối cùng của bạn là sắp xếp chèn. Nếu 26 đống là hai, sử dụng 24 :). Nếu 26 cọc quá nhiều, hãy chia bảng chữ cái và các bài kiểm tra thành 5 cọc. Sau đó, sắp xếp từng đống, một lần nữa bạn sẽ có 5 trường hợp (một với 6).

Answer 4

Tôi sử dụng sắp xếp nhóm. Sử dụng bốn nhóm và một lần nữa sắp xếp từng nhóm bằng cách sử dụng một loại 4-nhóm khác, sắp xếp từng nhóm con (1/16) bằng vũ phu!

Answer 5

• sắp xếp trên chữ cái đầu tiên vào M cọc
• khi bạn cần> = M cọc: đặt tất cả các mục có không phù hợp bắt đầu chữ trên thùng rác-đống
• vào cuối thời gian đầu tiên các M cọc được hoàn thành
• recurse, sử dụng thức ăn thừa từ các đống rác

hằng M có thể được điều chỉnh để phù hợp với khả năng của bạn để m atch & đặt nhiều chữ cái ngay từ cái nhìn đầu tiên. (và không gian bàn avalaible)

Trong thực tế, bạn sẽ không cần nhiều hơn một vài lần chạy, với giá trị hợp lý là M. (Zipf/Pareto pháp luật)

Answer 6

Tôi đã dựa trên thuật toán của mình trên tiền đề rằng thời gian cần để xác định thứ tự thích hợp cho hai phần tử không nhất quán. Ví dụ, thật dễ dàng để tôi nói rằng A thuộc về D, nhưng đưa tôi đến quyết định xem Q có đến trước T hay ngược lại hay không (nói chung, các chữ cái càng gần cuối bảng chữ cái và với nhau, có nhiều khả năng là tôi sẽ phải tinh thần đọc bảng chữ cái để chắc chắn).

Với điều này, tôi thấy nó làm giảm bảng chữ cái-đọc nếu tôi chia các bài kiểm tra vào chữ cái tẻ nhạt "khối":

• Beginning (AF ish)
• sớm Trung (GK ish)
• Late Middle (LP ish)
• Kết thúc (QZ ish). Điều này là lớn hơn bởi vì (a) đó là lĩnh vực mà tôi là tồi tệ nhất trong việc quyết định thứ tự của các chữ cái và (b) một vài trong số các chữ cái này không thường bắt đầu tên cuối cùng

Có chồng chéo - tức là đôi khi tôi sẽ cảm thấy như một Q là Late Middle và đôi khi tôi sẽ cảm thấy như nó là End. Nó phụ thuộc vào độ lớn của cọc tại thời điểm đó và những gì tôi sắp xếp cuối cùng ... lý thuyết của tôi là thời gian được lưu bằng cách không đánh vần bảng chữ cái trong đầu của tôi tất cả thời gian lớn hơn thời gian thêm dành cho việc sắp xếp sau trên.

Đó là như xa như tôi đã nhận được, tuy nhiên. Ngoài đoạn chunking ban đầu, tôi không bao giờ có thể quyết định điều gì hiệu quả nhất ...

Answer 7

Đây là một câu hỏi tuyệt vời! Chúng tôi đã tiến hành một thí nghiệm nhỏ để đến gần hơn với một câu trả lời.

chúng tôi thiết lập bao gồm

• 3 máy phân loại (A, B và C).

• 3 ngăn xếp gồm 40 bộ vấn đề của học sinh (một cho mỗi máy phân loại). Số tờ của một bộ vấn đề dao động từ 1 đến 5. Các tờ giấy được ghim lại và có tên học sinh được viết trên đầu trang đầu tiên.

• 3 thuật toán sắp xếp để sắp xếp các ngăn xếp theo thứ tự abc:

  • Insertion: Lấy mục đầu từ đống không được phân loại và chèn vào đúng vị trí trong đống sắp xếp. Fanning ra các cọc được sắp xếp được cho phép.
  • Xô: Sắp xếp từng mục vào một trong năm nhóm (A-E, F-J, K-O, P-T, U-Z). Sau đó sắp xếp từng nhóm bằng cách sử dụng sắp xếp chèn. Kết hợp các nhóm được sắp xếp.
  • Hợp nhất: Chia các mục thành 10 cọc. Sắp xếp từng cọc bằng cách sử dụng sắp xếp chèn. Đặt 10 cọc được sắp xếp thành 5 cặp. Hợp nhất từng cặp bằng cách liên tục xem các mục trên cùng của cặp và đặt một cặp cao hơn theo thứ tự bảng chữ cái ở dưới cùng của đống kết quả của cặp. Sau khi kết hợp 10 cọc thành 5, hợp nhất 2 trong số 5 cọc, sao cho còn lại 4 cọc. Sau đó, nhiều lần hợp nhất cặp đôi cho đến khi một cọc được sắp xếp duy nhất vẫn còn.

• đo:

  • Thời gian cho đến khi hoàn thành các thuật toán sắp xếp.
  • Số mục bị thất lạc (được đo bằng máy phân loại khác).

• Thứ tự của thuật toán sắp xếp được chọn ngẫu nhiên.

• Mỗi vòng mới ngăn xếp tập hợp sự cố được trao đổi giữa các máy phân loại và xáo trộn trong vài phút.

• Máy phân loại A và B đã thực hiện 9 vòng, máy phân loại C đã thực hiện 3 vòng.

• Trang tính có sắp xếp thứ tự bảng chữ cái và xô được đặt lên bảng của mỗi người sắp xếp.

Đây là hình ảnh thiết lập của chúng tôi.

Và đây là kết quả.

Hai kết luận là ngay lập tức.

1. Thuật toán sắp xếp hợp nhất tương đối phức tạp được tạo thành kém. Hợp nhất các loại liên tục mất từ ​​57 đến 125% dài hơn so với trong nhóm sắp xếp/chèn sắp xếp trung bình mà không có độ chính xác rõ ràng.

Chúng tôi dự đoán rằng bước đầu tiên để chia ngăn xếp tập hợp sự cố thành 10 cọc có thể góp phần kết hợp các kết quả mờ nhạt của sắp xếp. Các nhà nghiên cứu tương lai có thể thấy rằng các thuật toán giống như kết hợp được kết hợp với các quy trình thiết lập hiệu quả hơn có hiệu quả.

2. Mặc dù sắp xếp xô và chèn đều hoạt động tốt, sắp xếp nhóm nhanh hơn từ 13 đến 25% so với sắp xếp chèn trong bộ sắp xếp. Sự khác biệt này tương ứng với khoảng một phút thời gian được lưu cho mỗi loại 40 tập hợp vấn đề.

Chúng tôi dự đoán hiệu suất tương đối của nhóm sắp xếp sẽ cải thiện khi số lượng bộ sắp xếp phát triển vượt quá 40 và sắp xếp chèn sẽ chiếm ưu thế cho ngăn xếp 30 hoặc ít hơn, mặc dù cần thử nghiệm thêm. Không có sự khác biệt rõ ràng về độ chính xác giữa các loại xô và chèn.

Cuối cùng, chúng tôi lưu ý rằng có những khác biệt quan trọng trong khả năng phân loại giữa các đối tượng thử nghiệm của chúng tôi. Máy phân loại B luôn hoạt động tốt hơn các máy phân loại A và C lần lượt là 39 và 101 giây. Điều này cho thấy rằng mặc dù các thủ tục phân loại được sử dụng là rất quan trọng để phân loại tốc độ, khả năng có thể giải thích ít nhất là một phần lớn của phương sai trong các kết quả riêng lẻ. Khám phá những gì làm cho người Đức như máy phân loại tuyệt vời là một khu vực đầy hứa hẹn cho nghiên cứu trong tương lai.

Answer 8

Khoa của tôi có khóa học cơ bản với 500-600 sinh viên thường xuyên viết bài kiểm tra. Từ một đường mòn & phương pháp tiếp cận lỗi có vẻ như chúng tôi nhận được phân loại thực hiện nhanh nhất bằng cách đầu tiên làm một loại xô với khoảng một xô mỗi lá thư. Chữ S thường có thể được chia thành hai nhóm trong khi các chữ cái ở cuối bảng chữ cái (x, y, z) thường có thể chia sẻ một nhóm. Sau đó chúng tôi sắp xếp trong mỗi nhóm bằng cách sắp xếp chèn và kết thúc bằng cách xếp chồng các nhóm.

Đối với các lớp học nhỏ (lên đến khoảng 30) sắp xếp chèn trực tiếp là khả thi, nhưng thời gian cần thiết để tìm vị trí chính xác để chèn nhanh chóng được ra khỏi tay khi đống phát triển.