Sắp xếp 2 danh sách liên kết 50000 số với một nhóm hoạt động giới hạn

Question

Vì vậy, tôi có dự án này cho trường học: Tôi có danh sách liên kết gồm 50 000 số và danh sách trống thứ hai. Tôi chỉ có một bảng chỉ dẫn rất hạn chế. Đó là:

• "sa" hoán đổi hai yếu tố đầu tiên của danh sách 1

• "sb" hoán đổi hai yếu tố đầu tiên của danh sách 2

• "ss" là "sa" và "sb" cùng lúc

• "pa": đẩy yếu tố đầu danh sách 2 trên đầu danh sách 1

• "pb": đẩy yếu tố đầu danh sách 1 trên đầu danh sách 2

• "ra": danh sách xoay 1 (phần tử đầu tiên trở thành cuối cùng)

• "rb": danh sách xoay 2 (lần đầu tiên trở thành cuối cùng)

• "rr": "ra" và "rb" cùng một lúc

• "RRA": xoay danh sách 1 (trở thành cuối cùng đầu tiên)

• "RRB": xoay danh sách 2 (trở thành cuối cùng đầu tiên)

• "rrr": "RRA" và "RRB" cùng một lúc

tôi phải thực hiện một thuật toán sắp xếp trong c và mục đích là để làm điều đó với số tiền nhỏ nhất của hướng dẫn. Tôi đã thử với một thuật toán rất đơn giản để xoay danh sách cho đến khi tối đa nằm trên đầu và sau đó đẩy nó vào danh sách 2 nhiều lần cho đến khi mọi thứ nằm trong danh sách 2 và sau đó đẩy mọi thứ vào danh sách 1, nhưng tôi không thể sắp xếp danh sách nhiều hơn 5k số trong một khoảng thời gian hợp lý

Answer 1

Tôi nghĩ rằng tôi đã tìm ra cách thực hiện điều này bằng cách sử dụng sắp xếp nhanh. Đây là một số mã giả.

chỉnh sửa: cập nhật giả để tập trung vào những gì nó làm và không cú pháp không cần thiết

quicksort(int n) 
    if n == 1 return 
    int top_half_len = 0 
    choose a median //it's up to you to determine the best way to do this 
    for 0 to n { //filter all values above the median into list 2 
     if (value > median) { 
      push list 1 top to list 2 //list 2 stores the larger half 
      top_half_len++ 
     } 
     rotate list 1 forward 
    } 

    //reverse the list back to original position 
    rotate list 1 backward (n - top_half_len) times 

    //push larger half onto smaller half 
    push list 2 top to list 1 top_half_len times 

    //recursively call this on the larger half 
    quicksort(top_half_len) 

    //rotate smaller half to front 
    rotate list 1 forward top_half_len times 

    //recursively call this on smaller half 
    quicksort(n - top_half_len) 

    //reverse list back to original position 
    rotate list 1 backward top_half_len times 

Về cơ bản, nó chia tách danh sách vào một phần nhỏ hơn hoặc bằng so với mức trung bình (nửa nhỏ hơn) và một phần lớn hơn trung bình (một nửa lớn hơn). Sau đó, nó tự gọi mình trên cả hai nửa này. Khi chúng dài 1, thuật toán được thực hiện, vì danh sách độ dài 1 được sắp xếp. Google nhanh chóng sắp xếp cho một lời giải thích thực tế.

Tôi nghĩ rằng điều này sẽ hoạt động, nhưng tôi có thể đã bỏ lỡ một số trường hợp cạnh. Đừng mù quáng theo dõi điều này. Ngoài ra, nếu bạn đang xử lý mảng, tôi khuyên bạn nên dừng sắp xếp nhanh ở độ sâu đệ quy nhất định và sử dụng sắp xếp đống (hoặc thứ gì đó để ngăn chặn trường hợp xấu nhất O (n^2), nhưng tôi không chắc chắn điều gì sẽ hiệu quả ở đây. cập nhật: theo Peter Cordes, bạn nên sử dụng sắp xếp chèn khi bạn nhận được dưới một kích thước mảng nhất định (IMO bạn nên ở độ sâu đệ quy nhất định quá).

Dường như sắp xếp hợp nhất nhanh hơn trên danh sách được liên kết. Nó có lẽ sẽ không quá khó để sửa đổi điều này để thực hiện sắp xếp hợp nhất. Sắp xếp hợp nhất khá giống với sắp xếp nhanh. why is merge sort preferred over quick sort for sorting linked lists

Answer 2

Các báo cáo vấn đề thiếu chức năng so sánh, vì vậy tôi sẽ xác định so sánh (Lista, listb) để so sánh nút đầu tiên của Lista với nút đầu tiên của listb và trở về -1 cho <, 0 cho =, 1 cho lớn hơn, hoặc tất cả những gì thực sự cần thiết cho sắp xếp hợp nhất là 0 cho < = và 1 cho>.

Ngoài ra còn thiếu là giá trị trả về để biểu thị danh sách trống khi thực hiện pa hoặc pb. Tôi sẽ định nghĩa pa hoặc pb để trả về 1 nếu danh sách nguồn không rỗng và 0 nếu danh sách nguồn trống (không có nút nào để sao chép).

Không rõ liệu mục tiêu là số lượng lệnh nhỏ nhất có đề cập đến số lượng hướng dẫn trong mã nguồn hoặc số lượng lệnh được thực hiện trong quá trình sắp xếp hay không.

- 

Số lệnh nhỏ nhất trong mã sẽ xoay danh sách2 dựa trên so sánh với danh sách1 để chèn các nút vào danh sách2 ở vị trí thích hợp. Bắt đầu với một pb, và thiết lập kích thước list2 là 1. Sau đó rb hoặc rrb được thực hiện để xoay list2 đến nơi mà pb tiếp theo nên được thực hiện. Mã sẽ theo dõi danh sách2 "bù đắp" đến nút nhỏ nhất để tránh vòng lặp vô tận trong danh sách xoay2. Độ phức tạp là O (n^2).

- 

Tôi nghĩ rằng sắp xếp nhanh nhất và có lẽ ít nhất số lượng lệnh được thực hiện là sắp xếp hợp nhất từ ​​dưới lên.

Thực hiện sắp xếp hợp nhất từ ​​dưới lên trong khi xoay danh sách, sử dụng chúng như bộ đệm/danh sách vòng tròn. Sao chép list1 vào list2 để tạo ra một số các nút, sử dụng chuỗi | count = 0 | trong khi (pb) {rb | đếm + = 1}.

Sử dụng số, di chuyển mọi nút khác từ list2 đến list1 bằng {pa, rr}, n/2 lần. Luôn theo dõi số lượng nút thực tế trên mỗi danh sách để biết khi nào kết thúc hợp lý của một danh sách. Cũng theo dõi một bộ đếm chạy cho mỗi danh sách để biết khi nào kết thúc hợp lý của một lần chạy. Tại thời điểm này, bạn có hai danh sách trong đó các nút đồng đều nằm trong danh sách1 và các nút lẻ nằm trong danh sách2.

Kích thước chạy bắt đầu lúc 1 và tăng gấp đôi trên mỗi lượt vượt qua. Đối với lần đầu tiên vượt qua với kích thước chạy của 1, kết hợp các nút ngay cả với các nút lẻ, tạo các lần chạy được sắp xếp có kích thước 2, xen kẽ thêm các cặp được sắp xếp của các nút vào list1 và list2. Ví dụ, nếu phụ thêm vào list1, và nút list1 < = nút list2, sử dụng {ra, run1count - = 1}, sử dụng {pa, ra, run2count - = 1}. Khi kết thúc một lần chạy, chạm phần còn lại của lần chạy còn lại vào cuối danh sách. Trong lần vượt qua tiếp theo, hợp nhất các lần chạy được sắp xếp của 2 nút từ danh sách, luân phiên nối các chuỗi được sắp xếp gồm 4 nút cho mỗi danh sách. Tiếp tục điều này cho các lần chạy 8, 16, ... cho đến khi tất cả các nút kết thúc trên một danh sách.

Vì vậy, đó là một đèo để đếm các nút, một đường chuyền để chia nhỏ các nút lẻ và lẻ, và ceil (log2 (n)) chuyển để thực hiện sắp xếp hợp nhất. Chi phí cho các hoạt động danh sách liên kết là nhỏ (xoay loại bỏ và nối thêm một nút), do đó, việc hợp nhất tổng thể nên được khá nhanh chóng.

Số lượng hướng dẫn trên đèo đếm có thể giảm xuống trong khi (pb) {count + = 1}, sẽ sao chép danh sách1 thành danh sách2 được đảo ngược. Sau đó nhổ list2 vào list1 cũng sẽ được thực hiện bằng cách sử dụng rrr để unreverse chúng.

Độ phức tạp là O (n log (n)).