درخواست آموزش انواع مرتب سازی های Heap ,Quick, Merge

[yekta]

       سلام
 
       می خواستم اگر امکان داره آموزش انواع مرتب سازی های ادغامی، سریع و Heap Sort را برام بذارید
                                       همچنین کد این برنامه ها را به زبان ++C

       ممنون

[آرین]

روش مرتب سازی ادغامی از الگوریتم تقسیم و حل (divide-and-conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. در این الگوریتم مساله به چند جزء کوچک‌تر تقسیم می‌شه. هر کدوم از این قسمت‌ها رو به طور مجزا حل کرده ، و با ترکیب اونها به مساله اصلی می‌رسیم. و اما طرح کلی مرتب سازی ادغام:

در این روش داده‌ها به دو قسمت مساوی تقسیم می‌شن. و هر کدوم از این قسمت‌ها - به صورت بازگشتی - مرتب ، و با ادغامشون دادها بصورت کامل مرتب می‌شن.

پیاده سازی مرتب سازی Merge sort)) در c++

کد:

void merge_sort (int arr[ ] , int low , int high)

{

 if (low >= high)
  return;

 int mid = (low + high) / ۲;

 merge_sort (arr , low , mid);

 merge_sort (arr , mid + ۱ , high);

 merge_array (arr , low , mid , high);

}
procedure merge_sort (var arr : array of integer ; l : integer ; h : integer);
var

 m : integer;

begin

 if l >= h then

  exit;

 m := (l + h) div ۲;

 merge_sort (arr , l , m);

 merge_sort (arr , m + ۱ , h);

 merge_array (arr , l , m , h);

end;

برنامه کامل مرتب سازی
merg

کد:

// mergesort.cpp

#include <algorithm>
#include <iostream>
using namespace std;

template <class T>
void mergesort( T a[], int start, int stop )
   
{
  // For demonstration purposes only
  cout << "sorting: ";
  for (int i = start; i < stop; ++i)
    cout << a[i] << " ";
  cout << endl;

  if ( stop - start > 1 )
  {
    int middle = ( start + stop ) / 2;

    mergesort( a, start, middle );
    mergesort( a, middle, stop );

    inplace_merge( a+start, a+middle, a+stop );
  }

  cout << "result : ";
  for (int i = start; i < stop; ++i)
    cout << a[i] << " ";
  cout << endl;
}


int main()
{
  int a[10] = {12,6,2,25,19,23,60,42,30,59};

  mergesort(a, 0, 10);

  system("pause");
  return 0;
}

[آرین]

مرتب سازی سریع (Quick Sort) از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شه. این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. به این ترتیب که داده‌ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده‌ها رو مرتب می‌کنه. برای اینکار یکی از داده‌ها (مثلاً داده اول) به عنوان محور انتخاب می‌شه. داده‌ها بر اساس محور طوری چینش می‌شن که همه داده‌های کوچک‌تر از محور سمت چپ و داده‌های بزرگ‌تر یا مساوی اون سمت راستش قرار می‌گیرن. با مرتب کردن دو قسمت به دست اومده کل داده‌ها مرتب می‌شن. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچک‌تر هستن و بالعکس. مثلاً اعداد صحیح زیر رو در نظر بگیرید:

۵  ۶  ۱  ۹  -۲  ۴  ۵  ۱۵  ۳  ۱  ۴  ۱۰

عدد ۵ رو به عنوان محور در نظر می‌گیریم. داده‌ها به این صورت بازچینی می‌شن:

۱  -۲  ۴  ۳  ۱  ۴  ۵  ۶  ۹  ۵  ۱۵  ۱۰

همونطور که مشاهده می‌کنید اعداد سمت چپ عدد ۵ زیر خط دار همگی از ۵ کوچیکتر و اعداد سمت راست بزرگ‌تر یا مساوی اون هستن.

سورس:

کد:

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <time.h>
     
    #include <codecogs/array/sort/quick_sort.h>
     
    int main()
    {
      double vals[25];
      int n=25;
     
      srand((unsigned int) time(NULL));
      for (int i=0; i<n; i++) vals[i]=((double) n*rand())/RAND_MAX;
     
      printf("\nArray to be sorted:\n");
      for (int i=0; i<n; i++) printf("%3.0f ", vals[i]);
      printf("\n");
     
      Array::Sort::quickSort<double>(vals, n);
     
      printf("Sorted array:\n");
      for (int i=0; i<n; i++) printf("%3.0f ", vals[i]);
      printf("\n");
      return 0;
    }

    Output:

    Array to be sorted:
     12  23  10  23   4
      2   9  19  14  16
     22   5   7  16   1
      6   8  24  13  21
      9  17   1   3   6
    Sorted array:
      1   1   2   3   4
      5   6   6   7   8
      9   9  10  12  13
     14  16  16  17  19
     21  22  23  23  24

[آرین]

همان طور که می دانیم ، هرم تقریبا مرتب است، زیرا هر مسیری از ریشه به برگ ، مرتب است. به این ترتیب ، الگوریتم کارآمدی به نام مرتب سازی هرمی را می‌توان با استفاده از آن به دست آورد.این مرتب سازی همانند سایر مرتب سازی ها بر روی یک آرایه صورت می‌گیرد. این روش مرتب سازی همانند مرتب سازی سریع از یک تابع کمکی استفاده می‌کند.

    * پیچیدگی آن همواره از(O(nlgn است. و بر خلاف مرتب سازی سریع به صورت بازگشتی نیست.
    * در این روش درخت heap روی آرایه ساخته می‌شود.
    * این الگوریتم پایدار نمی‌باشد.

سورس:
 

کد:

   #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
     
    #include <codecogs/array/sort/heap_sort.h>
     
    int main()
    {
      double vals[25];
      int n=25;
     
      for (int i=0; i<n; i++) vals[i]=((double) n*rand())/RAND_MAX;
     
      printf("\nArray to be sorted:\n");
      for (int i=0; i<n; i++) printf("%3.0f ", vals[i]);
     
      Array::Sort::heapSort(vals, n);
     
      printf("\nSorted array:\n");
      for (int i=0; i<n; i++) printf("%3.0f ", vals[i]);
      printf("\n");
      return 0;
    }

    Output:

    Array to be sorted:
     23   6   6  13  11  10  13   4   9   4
     17  14   7   5  16   7  21   7  17  17
     23   6  16   9  18
    Sorted array:
      4   4   5   6   6   6   7   7   7   9
      9  10  11  13  13  14  16  16  17  17
      17  18  21  23  23