ترس از عاشقي

الگوريتم مرتب سازي ، در علوم كامپيوتر و رياضي ، الگوريتم ي است كه ليستي از داده ها را به ترتيبي مشخص مي چيند. پر استفاده ترين ترتيب ها، ترتيب هاي عددي و لغت نامه اي هستند. مرتب سازي كارا در بهينه سازي الگوريم هايي كه به ليست هاي مرتب شده نياز دارند (مثل جستجو و تركيب) اهميت زيادي دارد. از ابتداي علم كامپيوتر مسائل مرتب سازي تحقيقات فراواني را متوجه خود ساختند، شايد به اين علت كه در عين ساده بودن، حل آن به صورت كارا پيچيده است. براي مثال مرتب سازي حبابي در سال ۱۹۵۶ به وجود آمد. در حالي كه بسياري اين را يك مسئلهٔ حل شده مي پندارند، الگوريتم كارآمد جديدي همچنان ابداع مي شوند (مثلاً مرتب سازي كتاب خانه اي در سال ۲۰۰۴ مطرح شد). مبحث مرتب سازي در كلاس هاي معرفي علم كامپيوتر بسيار پر كاربرد است، مبحثي كه در آن وجود الگوريتم هاي فراوان به آشنايي با ايده هاي كلي و مراحل طراحي الگوريتم هاي مختلف كمك مي كند؛ مانند تحليل الگوريتم، داده ساختارها، الگوريتم هاي تصادفي، تحليل بدترين و بهترين حالت و حالت ميانگين، هزينهٔ زمان و حافظه، و حد پايين. در علم كامپيوتر معمولاً الگوريتم هاي مرتب سازي بر اساس اين معيارها طبقه بندي مي شوند: پيچيدگي (بدترين و بهترين عملكرد و عملكرد ميانگين): با توجه به اندازهٔ ليست (n). در مرتب سازي هاي معمولي عملكرد خوب (O(n log n و عملكرد بد (O(n ۲ است. بهترين عملكرد براي مرتب سازي (O(n است. الگوريتم هايي كه فقط از مقايسهٔ كليدها استفاده مي كنند در حالت ميانگين حداقل (O(n log n مقايسه نياز دارند. حافظه (و ساير منابع كامپيوتر) : بعضي از الگوريتم هاي مرتب سازي laquo;در جا [1] raquo; هستند. يعني به جز داده هايي كه بايد مرتب شوند، حافظهٔ كمي ((O(۱) مورد نياز است؛ در حالي كه ساير الگوريتم ها به ايجاد مكان هاي كمكي در حافظه براي نگه داري اطلاعات موقت نياز دارند. پايداري [2] : الگوريتم هاي مرتب سازي پايدار ترتيب را بين داده هاي داراي كليدهاي برابر حفظ مي كنند. فرض كنيد مي خواهيم چند نفر را بر اساس سن با يك الگوريتم پايدار مرتب كنيم. اگر دو نفر با نام هاي الف و ب هم سن باشند و در ليست اوليه الف جلوتر از ب آمده باشد، در ليست مرتب شده هم الف جلوتر از ب است. مقايسه اي بودن يا نبودن. در يك مرتب سازي مقايسه اي داده ها فقط با مقايسه به وسيلهٔ يك عملگر مقايسه مرتب مي شوند. روش كلي : درجي، جابجايي، گزينشي، تركيبي و غيره. جابجايي مانند مرتب سازي حبابي و مرتب سازي سريع و گزينشي مانند مرتب سازي پشته اي .