https://virgool.ir/feed/@agc.ashkan79دانشجویی مهندسی کامپیوتر گرایش نرم افزار در دانشگاه محقق اردبیلی علاقه مند به برنامه نویسی طراحی وب و هوش مصنوعیfa2026-11-12 05:12:37https://files.virgool.ir/upload/users/45617/avatar/353bmg.pnghttps://virgool.ir/@agc.ashkan79https://virgool.ir/@agc.ashkan79/تابع-sort-پایتون-و-سی-پلاس-پلاس-vgwfn8ce3lanخوب می خوام درباره ی تابع های مرتب سازی پیشفرض پایتون و c++ صحبت کنم و بگم که هر کدوم از چه نوع الگوریتمی استفاده می کنند.پایتونالگوریتم پیش فرض پایتون برای مرتب سازی timsort است و این الگوریتم مخصوص پایتون طراحی شده ( البته جاواسکریپت نیز از این الگوریتم استفاده می کند )علت سریع و خوب بودن آن hybrid بودن است یعنی هم از mergesort و Insertion استفاده می کند .هنگام مرتب سازی بررسی می شود که آیا تعداد عناصر داخل آرایه از 64 بزرگ تر است یا کوچک تر اگر کوچک تر بود از binary insertion sort استفاده می کند .روش کار binary insertion sort نیز به این صورت است که ابتدا خانه اول را برداشته چون تک خانه است پس مرتب است سپس خانه بعدی را به آن اضافه کرده و آن دو را نسبت به هم مقایسه می کند و سپس سومی وارد می شود و عدد سوم را نسبت به دو عدد قبلی در جای مناسب قرار می دهد و این عملیات تازمانی که آرایه مرتب شود تکرار می شود .حالا اگر تعداد عناصر آرایه از 64 بیشتر باشد نیاز به استفاده از یک مفهوم تازه به نام run هستیم .خوب run نشان دهنده این است هر آرایه به زیر آرایه های با عناصر به تعداد run تقسیم شودبعد از اینکه آرایه را به زیر آرایه ها تبدیل کردیم برای هرکدام از این زیر آرایه ها insertion sort را اعمال می کنیم .پس از آنکه تمام زیر آرایه ها مرتب شد آنها را باهم merge می کنیم .سی پلاس پلاس , (swift)برای مرتب سازی از intro sort استفاده می کند این مرتب سازی نیز از سه الگوریتم heap sort و quick sort insertion sortتشکیل شده است.این مرتب سازی با quick sort شروع می شود و زمانی که عمق تابع بازگشتی از یک مشخصی فراتر می رود تبدیل به heap sort می شود تا از بدترین حالت quick sort که n^2 است جلوگیری شود .و هنگامی که تعداد عناصر آرایه کم باشد از insertion sort استفاده می شود .در این الگوریتم سه محور یکی اول یکی دوم و یکی هم وسط آرایه قرار دارد را در نظر می گیریم و سپس به کمک محور ها آرایه را به partition ها تقسیم می شود و سپس برای هر پارتیشن به کمک قواعد زیر الگوریتم مخصوص آن را انتخاب می کنیم .در این الگوریتم اگر تعداد عناصر پارتیشن از 2*(n(log(n)) بیشتر باشد از heap sort استفاده می کنیم .اگر اندازه آرایه کم تر از 16 باشد تبدیل insertion sort استفاده می شود .اگر اندازه بین 16 و 2*(n(log(n)) باشد از quick sort استفاده می کنیم.مقایسه:Introsort best:o(n) worse: O(n(log(n)) average:O(n(log(n))Timsort : best : o(n) worse: O(n(log(n)) average:O(n(log(n))اشکان گنجاشکان گنجFri, 13 Dec 2019 12:02:23 +0330