Phân tách ổn định cho hai loại phần tử trong một mảng

Xem xét vấn đề sau.Phân tách ổn định cho hai loại phần tử trong một mảng

Chúng tôi được cung cấp một loạt các phần tử thuộc về một trong hai lớp: màu đỏ hoặc màu xanh dương. Chúng ta phải sắp xếp lại các phần tử của mảng sao cho tất cả các phần tử màu xanh xuất hiện đầu tiên (và tất cả các phần tử màu đỏ đều theo sau). Việc sắp xếp lại phải được thực hiện là thời trang ổn định, có nghĩa là thứ tự tương đối của các yếu tố màu xanh phải được bảo quản (giống với màu đỏ).

Có thuật toán thông minh nào có thể thực hiện sắp xếp lại ở trên không?

Một giải pháp không đúng chỗ là, tất nhiên, đơn giản.

Giải pháp rõ ràng tại chỗ sẽ áp dụng bất kỳ thuật toán phân loại ổn định nào cho mảng. Tuy nhiên, bằng cách sử dụng một thuật toán phân loại chính thức trên một mảng trực quan cảm thấy giống như một overkill, đặc biệt là có tính đến thực tế là chúng tôi chỉ giao dịch với hai loại yếu tố.

Bất kỳ ý tưởng nào được đánh giá cao.

Nguồn

2010-05-25 AnT

Có thể làm điều đó trong khoảng thời gian O (n) và O (1). Bài báo Stable minimum space partitioning in linear time của Jyrki Katajainen, và Tomi Pasanen tuyên bố có thể làm điều đó.

Google cho loại 0-1 ổn định.

Nguồn

2010-05-25 17:38:08

Cảm ơn. Thật không may, bài viết này chỉ có thể đăng ký, nhưng ít nhất bây giờ tôi biết rằng nó là 1) có thể, 2) không tầm thường :) – AnT

Nó có sẵn miễn phí từ CiteSeer: http://citeseerx.ist.psu.edu/ viewdoc/summary? doi = 10.1.1.25.5554 –

@Ants Aasma: Cảm ơn bạn đã liên kết. Tôi đã cập nhật câu trả lời với điều đó. –

Tôi không biết thuật toán O (n) nhưng đây là một thuật toán đơn giản với độ phức tạp O (n * log (n)) trong trường hợp xấu nhất. Có lẽ nó sẽ hữu ích.

Cắt bỏ các số 0 từ đầu và từ cuối, chúng đã ở vị trí của chúng. Bây giờ mảng trông giống như một chuỗi các chuỗi tiếp theo là chuỗi các số 0 theo sau là chuỗi số và cứ như vậy, như sau: 1010101010

Trao đổi chuỗi thứ nhất với chuỗi đầu tiên của số 0, dãy thứ ba với chuỗi thứ ba của số 0 và vân vân. Nó sẽ trở thành: 0110011001

Số lượng chuỗi đã giảm khoảng hai lần. Lặp lại quy trình trên cho đến khi sắp xếp mảng.

Để trao đổi hai chuỗi lân cận, đảo ngược chuỗi đầu tiên, sau đó là chuỗi thứ hai và sau đó đảo ngược cả hai.

Nguồn

2010-05-25 19:58:42 rem

Đây là O (n^2) trong trường hợp xấu nhất: xem xét 0 1 (n/2 lần) 0 1 0 1 ... 0 1. Một giải pháp O (nlogn) đơn giản là có một hàm so sánh từ điển trên (màu , chỉ mục) và sử dụng bất kỳ phương thức sắp xếp nào bằng cách sử dụng hàm so sánh đó. –

Không, số tiền vượt qua là O (log (n)) trong trường hợp xấu nhất. Đây là một ví dụ: http://pastebin.com/NyekVWmv – rem

Không có thuật toán phân loại O (n * log (n)) ổn định tại chỗ. Thông thường, phân loại ổn định trong các thư viện khác nhau được thực hiện bằng cách sử dụng sắp xếp hợp nhất yêu cầu bộ nhớ bổ sung O (n), xem ví dụ thực hiện của GNU C++ của stable_sort và Arrays.sort của Sun Java. – rem

Điều này được gọi là Phân vùng ổn định trong C++ và có một thuật toán chuẩn cho điều này: std::stable_partition.

Việc thực hiện SGI có hành vi thích ứng tùy thuộc vào dung lượng bộ nhớ có sẵn:

nó chạy trong thời gian O (N) nếu nó có thể phân bổ O (N) không gian
nó chạy trong thời gian O (N log N) hoán đổi tại chỗ

Tôi tự hỏi liệu giải pháp tại chỗ có sử dụng thuật toán sắp xếp ổn định sau hậu trường hay không.

Nguồn

2010-05-26 07:21:46

Phân tách ổn định cho hai loại phần tử trong một mảng

Trả lời

Các vấn đề liên quan