مونا روشی برای مرتبسازی یک لیست بهصورت صعودی ایجاد کرده است.
او از سمت چپ لیست شروع میکند و اعداد را بهصورت دوتایی مقایسه میکند. اگر جفت اول به ترتیب [عدد کوچکتر، عدد بزرگتر]
باشد، به جفت بعدی میرود. اگر جفت اول به ترتیب [عدد بزرگتر، عدد کوچکتر]
باشد، آن دو عدد را جابجا کرده و سپس به جفت بعدی میرود. این فرآیند را تا انتهای لیست تکرار میکند.
سپس دوباره به ابتدای لیست باز میگردد و این فرآیند را تکرار میکند تا کل لیست مرتب شود.
اگر لیست نامرتب [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 جابجایی نیاز دارد.
یک تابع بنویسید که یک لیست نامرتب بگیرد و تعداد جابجاییهای لازم برای مرتبسازی آن را بر اساس الگوریتم مونا برگرداند.
نمونه ورودی و خروجی
number_of_swaps([5, 4, 3]) ➞ 3
number_of_swaps([1, 3, 4, 5]) ➞ 0
number_of_swaps([5, 4, 3, 2]) ➞ 6
number_of_swaps([5, 4, 3]) ➞ 3
number_of_swaps([1, 3, 4, 5]) ➞ 0
number_of_swaps([5, 4, 3, 2]) ➞ 6
number_of_swaps([1, 2, 4, 3]) ➞ 1
number_of_swaps([1, 2, 5, 4, 3]) ➞ 3
number_of_swaps([1, 3, 4, 5]) ➞ 0
number_of_swaps([1, 2]) ➞ 0
نظرات