1. این پایگاه به ثبت ستاد ساماندهی وزارت فرهنگ و ارشاد اسلامی ایران رسیده است.

    مهمان عزیز سپاس بابت بازدید شما از تالار گفتگوی دهه هفتادی ها.

    عضویت در انجمن رایگان بوده و برای عموم باز میباشد . با صرف 30 ثانیه یکی از اعضای دهه هفتادی ها شوید .

مرتبسازی ادغامی ++c

شروع موضوع توسط saeid-ha ‏Nov 1, 2013 در انجمن برنامه نویسی و طراحی سایت

  1. saeid-ha

    saeid-ha belong to autumn !...

    3,098
    11,982
    1,894
    ConflictingEmotionsروش مرتبسازی ادغامی (Merge Sort) یک روش مرتبسازی مبتنی بر مقایسه عناصر با استفاده از روش تقسیم و غلبه است. این روش از مراحل بازگشتی زیر تشکیل یافته است:
    1- آرایه را به دو زیرآرایه با اندازه تقریبا یکسان تقسیم کن.
    2- دو زیرآرایه را به روش مرتبسازی ادغامی مرتب کن.
    3- دو زیرآرایه مرتبشده را ادغام کن.

    [​IMG]
    پیادهسازی مرتبسازی ادغامی
    بر اساس توضیحات فوق قطعه کد زیر به زبان برنامهنویسی ++C الگوریتم مرتبسازی ادغامی را پیادهسازی میکند:
    کد:
    کد:
    void merge_sort( int arr[ ], int low, int high )
    {
    if( low >= high )
    {
    return;
    }
    int mid = ( low + high ) / 2;
    merge_sort( arr, low, mid );
    merge_sort( arr, mid + 1, high );
    merge( arr, low, mid, high );
    }
    این قطعه کد بازههای low تا mid و mid + 1 تا high را به صورت بازگشتی مرتب کرده، و سپس توسط تابع merge ادغام میکند. به این ترتیب آرایه arr از بازه low تا high مرتب میشود.@Admin
    تابع merge پیادهسازیهای مختلفی دارد. یک روش ساده آن است که ادغام دو زیرآرایه در یک آرایه کمکی به طول مجموع طولهای این دو زیرآرایه صورت بگیرد. در این حالت این مرتبسازی یک مرتبسازی درجا نخواهد بود. چرا که متناسب با طول آرایه نیاز به فضای اضافی جهت مرتبسازی وجود دارد.
    قطعه کد زیر یک پیادهسازی درجا برای تابع merge است:
    این تابع محل مناسب عناصر زیرآرایه سمت راست را در زیرآرایه سمت چپ پیدا کرده و در آن درج میکند. با توجه به این که عناصر دو زیرآرایه مرتب هستند، ادغام آنها پیچیدگی کمتری خواهد داشت.
    به عنوان مثال اگر هدف ادغام کردن زیرآرایههای زیر باشد:

    کد:
    void merge( int arr[ ], int low, int mid, int high )
    {
    int i, j, k, t;
    j = low;
    for( i = mid + 1 ; i <= high ; i++ )
    {
    while( arr[ j ] <= arr[ i ] && j < i )
    {
    j++;
    }
    if( j == i )
    {
    break;
    }
    t = arr[ i ];
    for( k = i ; k > j ; k -- )
    {
    arr[ k ] = arr[ k - 1 ];
    }
    arr[ j ] = t;
    }
    }
    1 3 6 9 / 2 4 5 8ترتیب چینش عناصر پس از اتمام هر تکرار حلقه بیرونی قطعه کد فوق، به این ترتیب خواهد بود:

    1) 1 3 6 9 / 2 4 5 8 => 1 2 3 6 9 / 4 5 8
    2) 1 2 3 6 9 / 4 5 8 => 1 2 3 4 6 9 / 5 8
    3) 1 2 3 4 6 9 / 5 8 => 1 2 3 4 5 6 9 / 8
    4) 1 2 3 4 5 6 9 / 8 => 1 2 3 4 5 6 8 9 /
    پیچیدگی زمانی مرتبسازی ادغامی
    تعداد عناصر آرایه را n و تعداد مقایسههای مورد نیاز جهت مرتبسازی این عناصر را ( T( n در نظر میگیریم.
    بر اساس تعریف بازگشتی این الگوریتم، مرتب کردن n عنصر نیاز به مرتب شدن دو زیر آرایه تقریبا n / 2 عنصری دارد. پس از این مرحله، این دو زیرآرایه توسط تابع merge ادغام میشوند.
    جهت ادغام دو زیرآرایه با قطعه کد فوق - که در مجموع n عنصر دارند - حداکثر n مقایسه اتفاق خواهد افتاد (چرا؟). پس میتوان نوشت:
    T( n ) = 2 T( n / 2 ) + n
    حل این رابطه بازگشتی نشان از مرتبه اجرای ( Ө( n log n دارد.

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

    ویژگیهای مرتبسازی ادغامی
    1- پیچیدگی زمانی اجرای الگوریتم در تمامی حالات ( Ө( n log n است. چرا که این الگوریتم تحت هر شرایطی آرایه را به دو قسمت کرده و مرتبسازی را انجام میدهد.
    2- پیچیدگی حافظه مصرفی بستگی به روش پیادهسازی مرحله ادغام دارد، که تا ( O( n افزایش مییابد. پیادهسازی درجای این الگوریتم حافظه مصرفی مرتبه ( Ө( 1 دارد. اما اجرای آن در بدترین حالت زمانبر است.
    3- الگوربتم مرتبسازی ادغامی با پیادهسازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتبسازی حفظ میکند. whywhy
     
    Faryade yas، Admin، میلاد 1 و 3 نفر دیگر از این ارسال تشکر کرده اند.
  2. مرسی
     
    saeid-ha از این پست تشکر کرده است.
  3. saeid-ha

    saeid-ha belong to autumn !...

    3,098
    11,982
    1,894
    خوب حالا خلاصه وار بگو ببینم چی فهمیدی؟:35:
     
  4. Admin

    Admin غواصی فقط تو چشات عضو کادر مدیریت مدیر کل سایت

    12,524
    24,695
    63,090
    کدهارو تو تگ کد بذار
     
  5. خخخ هیچی نفهمیدم فقط تشکر کردم ازت دیوانه
     
    saeid-ha از این پست تشکر کرده است.
  6. سلام عزیزان
    میتونید از کتاب زیر استفاده کنید فکنم به دردتون بخوره

    ++c به زبان فارسی

    زبان برنامه‌نویسی ++C (سی پلاس پلاس) یک زبان برنامه‌نویسی رایانه‌ای همه‌منظوره، شیءگرا، سطح بالا و چندرگه (که از برنامه‌نویسی رویه‌ای، تجرید داده‌ها و برنامه‌نویسی شیءگرا پشتیبانی می‌کند)، عمومی و با قابلیت‌های سطح بالا و سطح پایین می‌باشد.
    این زبان دارای قابلیت‌های انواع داده ایستا، نوشتار آزاد، چندمدلی، معمولاً زبان ترجمه شده با پشتیبانی از برنامه‌نویسی ساخت‌یافته، برنامه‌نویسی شیءگرا، برنامه‌نویسی جنریک است. ++C به همراه جد خود C از پرطرفدارترین زبان‌های برنامه‌نویسی تجاری هستند.
    زبان ++c یک زبان سطح میانی در نظر گرفته می‌شود. این زبان دارای قابلیت زبان‌های سطح بالا و پایین به‌صورت هم‌زمان است. زبان ++C توسط بی‌یارنه استراس‌تروپ دانمارکی در سال ۱۹۷۹ درآزمایشگاه‌های بل (Bell Labs)، برای بهبود زبان سی و بر مبنای آن ساخته شد و آن را “C با کلاس” (C With Classes) نام‌گذاری نمودند. در سال ۱۹۸۳ به ++c تغییر نام داد. توسعه با اضافه نمودن کلاس‌ها و ویژگی‌های دیگری مانند توابع مجازی، سربارگزاری عملگرها، وراثت چندگانه، قالب توابع، و پردازش استثنا انجام شد. این زبان برنامه‌نویسی در سال ۱۹۹۸ تحت نام ISO/IEC ۱۴۸۸۲:۱۹۹۸ استاندارد شد. نسخه فعلی استاندارد این زبان ISO/IEC ۱۴۸۸۲:۲۰۰۳ است. نسخه جدیدی از استاندارد (که به صورت غیررسمی C++۰x نامیده می‌شود) در دست تهیه است.


    برای مشاهده لینک ها لطفا ثبت نام کنید و یا اگر حساب کاربری دارید وارد شوید



    220.
     
    Admin از این پست تشکر کرده است.