Thuật toán phân tích trước khi phân loại?

Question

Đó là một vấn đề nổi tiếng với Quicksort khi tập dữ liệu nằm trong hoặc gần như theo thứ tự sắp xếp, hiệu suất giảm đáng kể. Trong trường hợp này, Sắp xếp chèn, thường rất chậm, có thể dễ dàng là lựa chọn tốt nhất. Câu hỏi đặt ra là biết khi nào nên sử dụng.

Có sẵn thuật toán để chạy qua tập dữ liệu, áp dụng hệ số so sánh và trả về báo cáo về cách tập dữ liệu sắp xếp theo thứ tự sắp xếp không? Tôi thích Delphi/Pascal hơn, nhưng tôi có thể đọc các ngôn ngữ khác nếu ví dụ không quá phức tạp.

Answer 1

Như bạn mong đợi khá nhiều suy nghĩ đi sâu vào vấn đề này. Kỹ thuật trung bình-ba có nghĩa là hành vi trường hợp xấu nhất của quicksort không xảy ra đối với dữ liệu được sắp xếp, mà thay vào đó là các trường hợp ít rõ ràng hơn.

Introsort khá thú vị, vì nó tránh trường hợp xấu nhất bậc hai của quicksort hoàn toàn. Thay vì câu hỏi tự nhiên của bạn, "làm thế nào để tôi phát hiện ra rằng dữ liệu được sắp xếp gần như", nó có hiệu lực yêu cầu chính nó như nó đi cùng, "này có phải mất quá lâu?". Nếu câu trả lời là có, nó chuyển từ quicksort sang heapsort.

Timsort kết hợp sắp xếp hợp nhất với sắp xếp chèn và thực hiện rất tốt trên dữ liệu được sắp xếp hoặc sắp xếp ngược và trên dữ liệu bao gồm các tập hợp con được sắp xếp hoặc sắp xếp ngược.

Vì vậy, có lẽ câu trả lời cho câu hỏi của bạn là "bạn không cần phân tích trước khi vượt qua, bạn cần một thuật toán sắp xếp thích ứng".

Answer 2

Tôi chưa từng nghe về bất kỳ phân tích phân loại trước nào nhưng ý kiến ​​của tôi là nếu bạn đang đi qua tập dữ liệu để phân tích nó thì bạn đã cắt thành hiệu suất của thời gian phân loại tổng thể của bạn.

Answer 3

Một giải pháp có thể là lấy phần tử đầu tiên, cuối và phần tử giữa trong phạm vi sắp xếp hiện tại (trong thao tác QuickSort) và chọn phần giữa làm phần tử trục.

Answer 4

Để phân tích đầy đủ với mục đích quyết định sử dụng thuật toán nào, bạn sẽ thực hiện gần như công việc sắp xếp. Bạn có thể làm một cái gì đó như kiểm tra các giá trị tại một tỷ lệ phần trăm nhỏ ngẫu nhiên nhưng tăng chỉ số (tức là phân tích một mẫu nhỏ của các mặt hàng).

Answer 5

Cũng có SmoothSort, có vẻ khá khó thực hiện, nhưng nó khác nhau giữa O (N log N) đến O (N) tùy thuộc vào cách sắp xếp dữ liệu bắt đầu bằng.

http://en.wikipedia.org/wiki/Smoothsort

dài khéo léo PDF: http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

Tuy nhiên, nếu dữ liệu của bạn là thực sự rất lớn và bạn phải truy cập vào nó serially, mergesort có lẽ là tốt nhất. Nó luôn luôn là O (N log N) và nó có các thuộc tính 'locality' xuất sắc.

Answer 6

Bạn vẫn phải chạy qua tất cả các bản ghi để xác định xem đã được sắp xếp hay chưa, để cải thiện hiệu suất, bắt đầu với bản ghi đầu tiên của bạn và chạy phần còn lại cho đến khi bạn nhận thấy điều gì đó không được sắp xếp đúng hoặc đến cuối danh sách. Nếu bạn tìm thấy lỗi sau đó chỉ sắp xếp các mục từ vị trí đó đến cuối (kể từ khi bắt đầu danh sách đã được sắp xếp).

Tại mỗi mục trong phần thứ hai, xem mục có là < hơn phần tử cuối cùng trong phần đầu tiên và nếu có, hãy sử dụng sắp xếp chèn vào CHỈ phần đầu tiên. Nếu không, Quicksort sẽ chống lại tất cả các mục khác trong phần thứ hai. Bằng cách này, sắp xếp được tối ưu hóa cho trường hợp cụ thể.

Answer 7

Sắp xếp nhanh beng một vấn đề duy nhất khi tập dữ liệu là rất lớn và đã chủ yếu là sắp xếp, tôi sẽ sử dụng công nghệ tự động sau (khi chờ đợi một giải pháp toàn diện):

• Đừng bận tâm nếu dữ liệu thiết lập kích thước là dưới ngưỡng.

• Nếu bạn có quyền truy cập nhanh (được lập chỉ mục) vào bản ghi (mục) lấy mẫu có 1 bản ghi trong mỗi bản ghi N và xem chúng đã được sắp xếp chưa. Nên đủ nhanh cho một mẫu nhỏ và sau đó bạn có thể quyết định sử dụng sắp xếp nhanh hay không.

Answer 8

Để tạo một điểm khái niệm mà mọi người chưa thực hiện: Quicksort là thuật toán phân chia và chinh phục thông thường với lỗi rõ ràng trong những trường hợp hiếm hoi. Giả sử bạn muốn sắp xếp một chồng giấy tờ sinh viên. (Mà tôi phải làm với một số quy luật.) Trong thuật toán quicksort, bạn chọn một số giấy, trục xoay. Sau đó chia các giấy tờ khác theo chúng cho dù trước hoặc sau trục xoay. Sau đó lặp lại điều đó với hai tập con. Lỗi là gì? Trục xoay có thể là một tên gần một đầu của danh sách thay vì ở giữa, để nó không hoàn thành nhiều để chia thành hai cọc.

Sắp xếp hợp nhất là một thuật toán phân chia và conquer khác hoạt động theo thứ tự khác. Bạn có thể hợp nhất hai danh sách được sắp xếp theo thời gian tuyến tính. Chia các bài báo thành hai đống bằng nhau hoặc gần như bằng nhau, sau đó phân loại đệ quy mỗi một, sau đó hợp nhất. Sắp xếp hợp nhất không có bất kỳ lỗi nào. Một lý do mà quicksort là phổ biến hơn so với sắp xếp hợp nhất là lịch sử: Quicksort nhanh (thường) và nó hoạt động mà không cần thêm bộ nhớ nào. Nhưng những ngày này, nó có thể quan trọng hơn để tiết kiệm so sánh hơn để tiết kiệm bộ nhớ, và sắp xếp lại thực tế thường được trừu tượng bằng cách cho phép con trỏ. Nếu mọi thứ luôn luôn như vậy, thì tôi nghi ngờ rằng sắp xếp hợp nhất sẽ đơn giản hơn phổ biến hơn quicksort. (Và có thể thêm "nhanh" vào tên là bán hàng tốt.)