اگه شما یه سری از اعداد رو داشته باشین چه جوری مرتب می کنید؟ ذهن انسان به طور خودکار الگوریتمی کار می کنه ولی کامپیوتر که هوش نداره و برای حل مسئله به الگوریتم نیاز داره مثلا:

اولین عدد رو در نظر می گیریم و با عددهای بعد از خودش مقایسه می کنیم اگه بزرگتر باشه جابجا می کنیم و تا زمانی این کار رو انجام میدهیم که عدد در نظر گرفته شده از عدد بعدی بزرگتر نباشد بدین ترتیب جای اولین عدد در سری پیدا میشه بعد از اون به سراغ عدد بعدی می رویم و همین عمل رو تکرار می کنیم. اگه این کار رو تا آخر لیست انجام دهیم همه اعداد مرتب می شوند. خوب این یه نوع الگوریتم مرتب سازیه که پیچیدگی زمانیش n به توان ۲ است. حالا پیچیدگی زمانی چی هست بماند.اگه بخوام در موردش صحبت کنم یه کتاب باید بنویسم فقط این رو بدونید که هر چه کوچک تر باشد الگوریتم سریعتر است.

اثبات شده الگوریتم هایی که از طریق مقایسه به مرتب سازی می پردازند حداقل پیچیدگی زمانی n ضربدر لگاریتم n (مبنای ۲) را دارا می باشند یعنی سریعترین الگوریتم مرتب سازی (که با نام Quick Sort معروف است) این پیچیدگی زمانی را دارا می باشد و اثبات شده که نمیشه الگوریتمی سریعتر از این برای مرتب سازی از طریق مقایسه پیدا کرد.

اگه خیلی علاقمندید که در این مورد بیشتر بدونید بهتون ۲ تا کتاب معروف در زمینه طراحی الگوریتم معرفی می کنم:

اگه دانشجوی ریاضی یا علوم کامپیوتر هستین کتاب طراحی الگوریتم نوشته Brasard خیلی عالیه چون به قضیه به صورت ریاضی نگاه کرده (من از کتاب Brassard تو بازار ترجمه ای ندیدم) ولی اگه از ریاضی خوشتون نمیاد کتاب دکتر نعیمی پور که ترجمه های زیادی هم ازش تو بازار هست کتاب خوبیه. (دکتر نعیمی پور ایران نیست و کتاب نوشته ایشون هم فارسی نیست). 

امیدوارم که تا حدی استفاده کرده باشین. دیگه بیشتر از این نمی شد اینجا فنی نوشت.

به امید روز های بهتر.