محبوبترینها
9 روش جرم گیری ماشین لباسشویی سامسونگ برای از بین بردن بوی بد
ساندویچ پانل: بهترین گزینه برای ساخت و ساز سریع
خرید بیمه، استعلام و مقایسه انواع بیمه درمان ✅?
پروازهای مشهد به دبی چه زمانی ارزان میشوند؟
تجربه غذاهای فرانسوی در قلب پاریس بهترین رستوران‌ها و کافه‌ها
دلایل زنگ زدن فلزات و روش های جلوگیری از آن
خرید بلیط چارتر هواپیمایی ماهان _ ماهان گشت
سیگنال در ترید چیست؟ بررسی انواع سیگنال در ترید
بهترین هدیه تولد برای متولدین زمستان: هدیه‌های کاربردی برای روزهای سرد
در خرید پارچه برزنتی به چه نکاتی باید توجه کنیم؟
سه برند برتر کلید و پریز خارجی، لگراند، ویکو و اشنایدر
صفحه اول
آرشیو مطالب
ورود/عضویت
هواشناسی
قیمت طلا سکه و ارز
قیمت خودرو
مطالب در سایت شما
تبادل لینک
ارتباط با ما
مطالب سایت سرگرمی سبک زندگی سینما و تلویزیون فرهنگ و هنر پزشکی و سلامت اجتماع و خانواده تصویری دین و اندیشه ورزش اقتصادی سیاسی حوادث علم و فناوری سایتهای دانلود گوناگون
مطالب سایت سرگرمی سبک زندگی سینما و تلویزیون فرهنگ و هنر پزشکی و سلامت اجتماع و خانواده تصویری دین و اندیشه ورزش اقتصادی سیاسی حوادث علم و فناوری سایتهای دانلود گوناگون
آمار وبسایت
تعداد کل بازدیدها :
1826084511
الگوریتم های مرتب سازی آرایه ها -
واضح آرشیو وب فارسی:سایت ریسک: الگوریتم های مرتب سازی آرایه ها iMacs 15 فروردين 1390, 18:48یکی از مباحث اساسی دروس ساختمان داده ها و اصول طراحی الگوریتم ، یافتن الگوریتم هایی برای مرتب سازی اعدادی بهم ریخته ای است که در یک آرایه پشت سر هم قرار گرفته اند. تا کنون الگوریتم های مختلفی برای اینکار ایجاد شده است که در این مقاله با چند تا از این الگوریتم ها آشنا میشوید. همچنین مرتبه پیچیدگی هر الگوریتم (میزان زمانی که از CPU برای اجرای هر الگوریتم می گیرد) را ذکر خواهیم کرد. الگوریتم مرتب سازی انتخابی (Selection Sort ): در این روش، برنامه کوچکترین مقدار را یافته و آنرا در اولین خانه ی آرایه قرار می دهد. حال که کوچکترین عضو یافت شده است، برنامه به سراغ یافتن دومین عنصر کوچک در میان اعداد باقی مانده که از 2 تا n هستند می رود و دومین عدد کوچک را در خانه دوم قرار میدهد. حال به سراغ سومین عدد کوچک می رود و این رویه را تا یافتن آخر عدد و قرار دادن آن در جای خودش تکرار میکند. با توجه به اینکه برنامه باید n عدد را n بار با هم مقایسه کند مرتبه ی پیچیدگی این الگوریتم O (n2)است. مرتب سازی حبابی (Bubble Sort ): در این روش هر عنصر با عنصر بعدی اش مقایسه میشود. در صورتی که عنصر دومی کوچکتر از عنصر اولی باشد، جای دو عنصر با هم عوض میشود. برنامه به کارش ادامه میدهد و عناصر دوم و سوم را با هم مقایسه میکند و این کار را تا اخر آرایه ادامه میدهد. دوباره الگوریتم ، پویش را از اول آرایه شروع میکند و مراحل قبل را تکرار میکند و این مراحل آنقدر تکرار میشوند تا آرایه کاملا مرتب شده باشد. مرتبه ی پیچیدگی این الگوریتم O(n2) است. مرتب سازی درجی (Insertion Sort ): در این روش عنصر اول و دوم با هم مقایسه شده و در صورت نیاز مرتب میشوند و سپس سومین عنصر با عناصر اول و دوم مقایسه میشود. در صورتی که عنصر سوم از اولی کوچکتر باشد به جای اولین عنصر می نشیند و عناصر قبلی به سمت راست هل داده میشوند. اگر عنصر سوم از اولی بزرگتر و از دومی کوچکتر باشد، بین آنها درج میشود و عنصر دوم به بعد یکی به سمت راست هل داده میشود. (پس در این روش همیشه عناصر ِ قبل از عنصری که میخواهیم مرتبش کنیم، مرتب هشتند.) این روال برای بقیه عناصر نیز اجرا میشود و هر عنصر در جای خودش قرار می گیرد تا تمام عناصر مرتب شوند. مرتبه ی پیچیدگی این الگوریتم O (n2) است. مرتب سازی سریع(Quick Sort ) : در این الگوریتم یک عنصر را بعنوان محور (pilot ) مرتب سازی انتخاب میکنیم. و تمام عناصر کوچکتر از آن را به سمت چپ آن برده و عناصر بزرگتر را به سمت راست اش می‌بریم. حالا بخش چپ خودش یک بخش جدید است که با الگوریتمی که گفتیم آنرا مرتب میکنیم و سمت راست را نیز همینطور. یعنی در سمت چپی ها دوباره یک عنصر را بعنوان pilot در نظر میگیریم و عناصر کوچکتر از pilot را به سمت چپ آن و عناصر بزرگتر از pilot این قسمت را ، به سمت راست pilot می بریم. دوباره الگوریتم را روی یک چهارم های به وجود آمده اجرا میکنیم و اینکار را آنقدر ادامه میدهیم تا کل آرایه مرتب شود. مرتبه پیچیدگی این الگوریتم در بدترین حالت O (n2) است. اما در حال نرمال O (n log n) است که کمترین مرتبه پیچیدگی برای مرتب سازی اعداد به حساب می آید. مرتب سازی ادغام (Merge Sort ): این الگوریتم به روش بازگشتی (Recursive ) عمل میکند و آرایه را به چند آرایه ی دو عنصری تقسیم میکند و آنها را مرتب میکند. سپس آرایه های کوچک را دوبه‌دو با هم ادغام میکند تا آرایه های مرتب 4 عنصری ایجاد شوند و بعد آرایه های 8 عنصری و به همین ترتیب پیش می رود تا آرایه اصلی بصورت مرتب شده ظاهر شود. مرتبه پیچیدگی این الگوریتم O(n log n) است. مرتب سازی هرمی (Heap Sort ): در این روش، برنامه از کل آرایه ی داده شده یک درخت MaxHeap می سازد. (درخت مکس هیپ درختی دودویی و کامل است که مقدار ذخیره شده در هر گره ، بزرگتر و یا مساوی مقدار ذخیره شده در گره فرزندانش است) سپس مقدار ماگزیمم را از درخت حذف میکند و آنرا در انتهای آرایه میگذارد و دوباره از بقیه اعداد یک درخت maxHeap میسازد و باز روش مذکور را روی آن نیز اعمال میکند تا دومین عدد بزرگ یافت شود. در این روش آرایه از آخر به اول مرتب میشود. مرتبه پیچیدگی این الگوریتم O (n log n)است. روش هایی وجود دارند که حداقل مرتبه ی پیچیدگی هر الگوریتم را با روابطی اثبات میکنند. بطور مثال برای الگوریتم های مرتب سازی ، میزان O (n Log n) حداقل است و کمتر از این میزان ممکن نیست و همانطور که میدانیم الگوریتم های ادغام و هرمی و سریع هر سه با همین میزان پیچیدگی مرتب سازی را انجام میدهند. بنابراین الگوریتمی نمیتوان نوشت که سریعتر از این حالت عمل کند و الگوریتم های مینیمم پیچیدگی در این زمینه ،قبلا کشف و ایجاد شده اند . اما مواردی هستند مانند ضرب دو ماتریس n در n که مرتبه ی پیچیدگی شانO(n3) است و روش های جدیدی مانند روش استراسن آنرا به O(n2.81) کاهش داده است. طبق روشهای اثبات شده امکان کمتر شدن این میزان وجود دارد. اما هنوز الگوریتمی که هزینه ی پیچیدگی کمتری از الگوریتم استراسن داشته باشد کشف نشده است. بنابراین هنوز شما میتوانید وقت خود را روی کاهش مرتبه ی پیچیدگی این الگوریتم و یافتن الگوریتم بهینه تر بگذارید. الگوریتم های شبیه سازی در ویکی پدیا شبیه سازی و مقایسه الگوریتم ها در کنار هم در حالات مختلف شبیه سازی مرتب سازی های مختلف (توسط اپلت جاوا) دموی دوم از الگوریتم های مرتب سازی (برای شروع به کار الگوریتم ها رویشان کلیک کنید.) سورس کد زبان C برای الگوریتم های مرتب سازی دموی اجرای کد ها و حلقه های تودرتوی هر الگوریتم منبع:جهان #C () سایت ما را در گوگل محبوب کنید با کلیک روی دکمه ای که در سمت چپ این منو با عنوان +1 قرار داده شده شما به این سایت مهر تأیید میزنید و به دوستانتان در صفحه جستجوی گوگل دیدن این سایت را پیشنهاد میکنید که این امر خود باعث افزایش رتبه سایت در گوگل میشود
این صفحه را در گوگل محبوب کنید
[ارسال شده از: سایت ریسک]
[مشاهده در: www.ri3k.eu]
[تعداد بازديد از اين مطلب: 5024]
-
گوناگون
پربازدیدترینها