مونا روشی برای مرتب‌سازی یک لیست به‌صورت صعودی ایجاد کرده است.
او از سمت چپ لیست شروع می‌کند و اعداد را به‌صورت دوتایی مقایسه می‌کند. اگر جفت اول به ترتیب [عدد کوچک‌تر، عدد بزرگ‌تر] باشد، به جفت بعدی می‌رود. اگر جفت اول به ترتیب [عدد بزرگ‌تر، عدد کوچک‌تر] باشد، آن دو عدد را جابجا کرده و سپس به جفت بعدی می‌رود. این فرآیند را تا انتهای لیست تکرار می‌کند.
سپس دوباره به ابتدای لیست باز می‌گردد و این فرآیند را تکرار می‌کند تا کل لیست مرتب شود.
اگر لیست نامرتب [3, 9, 7, 4] باشد، مراحل زیر انجام می‌شود:
- اولین جفت
[3, 9]مرتب است. حرکت به جفت بعدی. لیست:[3, 9, 7, 4]. تعداد جابجایی‌ها: 0. - جفت
[9, 7]مرتب نیست. جابجایی انجام می‌شود. لیست:[3, 7, 9, 4]. تعداد جابجایی‌ها: 1. - جفت
[9, 4]مرتب نیست. جابجایی انجام می‌شود. لیست:[3, 7, 4, 9]. تعداد جابجایی‌ها: 2. - بررسی لیست. مرتب نشده است. شروع دوباره از اولین جفت.
- جفت
[3, 7]مرتب است. حرکت به جفت بعدی. لیست:[3, 7, 4, 9]. تعداد جابجایی‌ها: 2. - جفت
[7, 4]مرتب نیست. جابجایی انجام می‌شود. لیست:[3, 4, 7, 9]. تعداد جابجایی‌ها: 3. - جفت
[7, 9]مرتب است. حرکت به جفت بعدی. لیست:[3, 4, 7, 9]. تعداد جابجایی‌ها: 3. - بررسی لیست. مرتب است. پایان.
بنابراین، مرتب‌سازی لیست [3, 9, 7, 4] به 3 جابجایی نیاز دارد.
یک تابع بنویسید که یک لیست نامرتب بگیرد و تعداد جابجایی‌های لازم برای مرتب‌سازی آن را بر اساس الگوریتم مونا برگرداند.
نمونه ورودی و خروجی
NumberOfSwaps([5, 4, 3]) ➞ 3
NumberOfSwaps([1, 3, 4, 5]) ➞ 0
NumberOfSwaps([5, 4, 3, 2]) ➞ 6
EXPECT_EQ(NumberOfSwaps({5, 4, 3}), 3);
EXPECT_EQ(NumberOfSwaps({1, 3, 4, 5}), 0);
EXPECT_EQ(NumberOfSwaps({5, 4, 3, 2}), 6);
EXPECT_EQ(NumberOfSwaps({1, 2, 4, 3}), 1);
EXPECT_EQ(NumberOfSwaps({1, 2, 5, 4, 3}), 3);
EXPECT_EQ(NumberOfSwaps({1, 3, 4, 5}), 0);
EXPECT_EQ(NumberOfSwaps({1, 2}), 0);
نظرات