تابع ()sort چگونه کار میکند؟
1-تابع sort در لیست ها ابتدا سایز (size list) را چک میکند و بر اساس آن تصمیم
میگیرد که از کدام روش مرتب سازی انتخاب کند روش های مرتب سازی عبارتند از
(bubble sort , selection sort ,insertion sort , merge sort , Quick sort)
الان با ساختارآنها و کارایی آنها کاری نداریم.
درلیستی وقتی میخواهیم داده های درون آنها رو مرتب کنیم روشی را انتخاب میکند که
با صرفه کم هرینه و از همه مهم تر بهینه تر باشد اگر لیستی سایزبالایی داشته باشد از
از روش Merge sort استفاده میکند و اگر سایز لیست کم باشد از روش Quick sort
یا Bubble sort استفاده میکند در این مرحله ممکن است از روش Quick sort برای
مرتب سازی استفاده کند اما همانظور که گفتم ابتدا مسائلی را چک میکند .
روش های sort داینامیک میتوانند باشند البته بستگی داره از libary که استفاده میکنیم
بعضی از پکیج ها از پایتون استفاده نمیکنند بلکه یک لول پایین میاد و از c استفاده میکند
در نتیجه خیلی سریع تر مرتب میکند و بهینه ترچون زبانc همانظور که میدانیم از سرعت
بالایی پیداست.
یک الگوریتم مرتب سازی Timsort پایدار ترکیبی است که نوع ادغام و مرتب سازی درج
شده و برای عملکرد مناسب در بسیاری از داده ها در دنیای واقعی طراحی شده است برای
اسنفاده از آن در زبان پایتون توسط تیم پیترز در سال 2002 اجرا شد . الگوریتم پیامد های
داده ای را که قبلا مرتب شده اند اجرا میکند و پیدا میکند و از آن ها برای مرتب سازی
باقی مانده با کارایی که بیشتراستفاده میکند این کار با ادغام انجام میشود تا زمان برآورده
شده معیار های خاص انجام میشود.
برای بهره گیری از اجرای عناصر مرتب شده متوالی که قبلاً در اکثر داده های دنیای واقعی ، اجرای طبیعی وجود داشته اند ، طراحی شده است. این امر از طریق جمع آوری داده ها ، عناصر را به صورت تکراری تکرار می کند و همزمان آن را در یک پشته قرار می دهد. هر زمان اجراهای بالای پشته با معیار ادغام مطابقت داشته باشند ، آنها ادغام می شوند. این کار ادامه می یابد تا زمانی که همه داده ها رد شوند. سپس ، همه اجراها همزمان دو بار ادغام می شوند و فقط یک نوع مرتب شده باقی می ماند. مزیت ادغام اجراهای مرتب شده به جای ادغام زیر لیست های اندازه ثابت (همانطور که توسط ادغام سنتی انجام شده است) این است که تعداد مقایسه های مورد نیاز برای مرتب سازی کل لیست را کاهش می دهد.
هر اجرا حداقل اندازه دارد که براساس اندازه ورودی است و در ابتدای الگوریتم تعریف می شود. اگر یک اجرا کوچکتر از این حداقل اندازه اجرا باشد ، از ترتیب درج برای افزودن عناصر بیشتر به اجرا تا رسیدن به حداقل اندازه اجرا استفاده می شود.
Timsort یک الگوریتم مرتب سازی پایدار است (ترتیب عناصر با همان کلید حفظ می شود) و تلاش می کند ادغام های متعادل را انجام دهد (یک ادغام بدین ترتیب اجراهایی با اندازه های مشابه را ادغام می کند).
به منظور دستیابی به ثبات مرتب سازی ، فقط اجرای های پی در پی ادغام می شوند. بین دو اجرا غیر متوالی می تواند عنصری با همان کلید عناصر در داخل اجرا ها وجود داشته باشد و ادغام این دو اجرا باعث تغییر ترتیب کلیدهای برابر می شود.
اجرای مرتب سازی اصلی ادغام در محل انجام نشده است و دارای یک فضای اضافی از N (اندازه داده) است. پیاده سازی های مرتب سازی در محل وجود دارد ، اما سربار بالایی دارند. به منظور دستیابی به یک میان مدت ، Timsort مرتب سازی ادغام را با زمان سربار کم و فضای سربار کمتر از N انجام می دهد.
- ۹۹/۱۰/۲۲