نمايش نتايج 1 تا 6 از 6

تاپیک: انواع مرتب سازی

  1. #1
    تازه وارد
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2007/4
    امتیاز
    10
    پست ها
    3

    پيش فرض انواع مرتب سازی

    من يه پروژه در باره انواع مرتب سازي دارم اگه ميشه در باره shell و quick sort و heapesort
    و radix sort كه همون مبنا مي باشد بنويسيد واگر هم مقدور بود مثالي هم ذكر كنيد
    اگه ننويسم 6 نمره از دست ميدم تو رو به خدا

  2. #2
    تازه وارد
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2007/4
    امتیاز
    14
    پست ها
    4

    پيش فرض

    نقل قول نوشته اصلي بوسيله hosein.kamali.vb نمايش پست
    من يه پروژه در باره انواع مرتب سازي دارم اگه ميشه در باره shell و quick sort و heapesort
    و radix sort كه همون مبنا مي باشد بنويسيد واگر هم مقدور بود مثالي هم ذكر كنيد
    اگه ننويسم 6 نمره از دست ميدم تو رو به خدا
    در علم کامپیوتر معمولاً الگوریتم‌های مرتب‌سازی بر اساس این معیارها طبقه‌بندی می‌شوند:
    • پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین): با توجه به اندازهٔ لیست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n۲ است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسهٔ کلیدها استفاده می‌کنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.
    • حافظه (و سایر منابع کامپیوتر) : بعضی از الگوریتم‌های مرتب‌سازی «در جا[مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.
    • پایداری[مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] : الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نام‌های الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.
    • مقایسه‌ای بودن یا نبودن. در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.
    • روش کلی : درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] و گزینشی مانند [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ].
    الگوریتم‌های مرتب سازی
    [[مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]] مرتب سازی حبابی

    (به [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]: Bubble Sort)
    فرض کنید n داده داریم که می‌خواهیم به صورت صعودی مرتب شوند. عنصر اول رو با دومی مقایسه ، و در صورتی که اولی بزرگتر باشد جاهاشون رو عوض می‌کنیم. همین کار رو با عناصر دوم و سوم انجام می‌دهید و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تموم شد بزرگترین عنصر بین داده‌ها به آخر لیست می‌رسد . حالا یک بار دیگه از اول این کار رو انجام می‌دهیم اما این بار تا عنصر (n -۱)ام ادامه می‌دهیم (عنصر nام مرحله اول جای خودش رو پیدا کرده). باز هم این کار رو تا عنصر (n - ۲)ام تکرار می‌کنیم ، و بازهم .... تا اینکه بالاخره داده‌ها مرتب می‌شوند. مثلا:
    ۰ - ۰) ۵ ۶ ۴ ۲۱ - ۱) ۵ ۶ ۴ ۲۱ - ۲) ۵ ۴ ۶ ۲۱ - ۳) ۵ ۴ ۲ ۶۲ - ۱) ۴ ۵ ۲ ۶۲ - ۲) ۴ ۲ ۵ ۶۳ - ۱) ۲ ۴ ۵ ۶
    مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می‌شوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:
    ۰ - ۰) ۰ ۷ ۱ ۳ ۵ ۴۱ - ۱) ۰ ۱ ۷ ۳ ۵ ۴۱ - ۲) ۰ ۱ ۷ ۳ ۵ ۴۱ - ۳) ۰ ۱ ۳ ۷ ۵ ۴۱ - ۴) ۰ ۱ ۳ ۵ ۷ ۴ ۱ - ۵) ۰ ۱ ۳ ۵ ۴ ۷ ۲ - ۱) ۰ ۱ ۳ ۵ ۴ ۷۲ - ۲) ۰ ۱ ۳ ۵ ۴ ۷۲ - ۳) ۰ ۱ ۳ ۵ ۴ ۷۲ - ۴) ۰ ۱ ۳ ۴ ۵ ۷ ۳ - ۱) ۰ ۱ ۳ ۴ ۵ ۷۳ - ۲) ۰ ۱ ۳ ۴ ۵ ۷۳ - ۳) ۰ ۱ ۳ ۴ ۵ ۷۴ - ۱) ۰ ۱ ۳ ۴ ۵ ۷۴ - ۲) ۰ ۱ ۳ ۴ ۵ ۷۵ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
    همونطور که می‌بینید انتهای مرحله ۲ داده‌ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله‌ای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه می‌شه که داده‌ها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن می‌شیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست. پیاده سازی (مرتب سازی حبابی) در c++


    void bubble_sort (int arr [ ] , int n){ register int i , j , t , c;(-- for (i = n - ۲ ; i >= ۰ ; i { c = ۰; (++ for (j = ۰ ; j <= i ; j if (arr [ j ] > arr [ j + ۱ ]) { ; ] t = arr [ j arr [ j ] = arr [ j + ۱ ]; ; arr [ j + ۱ ] = t C++; } (if (c == ۰ ; break }}


    [[مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]] مرتب سازی گزینشی

    (به [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]: Selection Sort)
    معمولا اطلاعات و داده‌های خامی که در اختیار برنامه نویس قرار داره بصورت نامرتب هستن. مواقعی پیش می‌یاد که لازمه این داده‌ها بر حسب فیلد خاصی مرتب بشن؛ مثل لیست دانش آموزان بر حسب معدل ، لیست کارمندان بر حسب شماره پرسنلی ، لیست دفترچه تلفن بر حسب نام خانوادگی و ... روشهای متعددی برای مرتب سازی وجود داره که من قصد دارم تا حد امکان شما رو با این روشها آشنا کنم. برای شروع روش مرتب سازی انتخابی (Selection Sort) رو توضیح می‌دم.
    روش انتخابی اولین روشیه که به ذهن می‌رسه: بزرگترین رکورد بین رکوردهای لیست رو پیدا می‌کنیم و به انتهای لیست انتقال می‌دیم. از بقیه رکوردها بزرگترین رو انتخاب می‌کنیم و انتهای لیست - کنار رکورد قبلی - قرار می‌دیم و ... مثلا:
    ۰: ۹ ۱ ۶ ۴ ۷ ۳ ۵۱: ۵ ۱ ۶ ۴ ۷ ۳ ۹۲: ۵ ۱ ۶ ۴ ۳ ۷ ۹۳: ۵ ۱ ۳ ۴ ۶ ۷ ۹۴: ۴ ۱ ۳ ۵ ۶ ۷ ۹۵: ۳ ۱ ۴ ۵ ۶ ۷ ۹۶: ۱ ۳ ۴ ۵ ۶ ۷ ۹

    پیاده سازی (مرتب سازی انتخابی) در c++
    void selection_sort (int arr[] , int n) { register int i , j; int max , temp; (--for (i = n - ۱ ; i > ۰ ; i } max = ۰; for (j = ۱ ; j <= i ; j++) if (arr[ max ] < arr[ j]) max = j; ; ] temp = arr[ i arr[ i ] = arr[ max]; arr[ max ] = temp; }}

    ۳ - مرتب سازی (Shell Sort)
    نام این الگوریتم از نام مخترع آن گرفته شده‌است. در این الگوریتم از روش درج استفاده می‌شود .
    به عنوان مثال رشته f d a c b e را تحت این الگوریتم مرتب می‌کنیم.
    F d a c b e : شروع C d a f d e : مرحله اول A b c d e f : مرحله دوم A b c d e f : نتیجه
    در مرحله اول : دادههای با فاصله ۳ از یکدیگر ، مقایسه و مرتب شده ، در مرحله دوم داده‌های با فاصله ۲ از یکدیگر ، مقایسه و مرتب می‌شوند و در مرحله دوم داده‌ها با فاصله یک از یکدیگر مقایسه و مرتب می‌شوند .منظور از فاصله سه این است که عنصر اول با عنصر چهارم(۳+۱) ، عنصر دوم با عنصر پنجم(۵=۳+۲) و عنصر سوم با عنصر ششم(۶=۳+۳) مقایسه شده در جای مناسب خود قرار می‌گیرد .
    برای انتخاب فاصله در اولین مرحله ، تعداد عناصر لیست بر ۲ تقسیم می‌شود(n/۲) وفاصله بعدی نیز با تقسیم فاصله فعلی بر ۲ حاصل می‌گردد و الگریتم تا زمانی ادامه پیدا می‌کند که این فاصله به صفر برسد.
    برای نمونه اگر تعداد عناصر برابر با ۱۰ باشد ، فاصله در مرحله اول برابر با ۵ ، در مرحله دوم برابر با ۲ ور در مرحله سوم برابر با ۱ و در نهایت برابر با صفر خواهد بود .
    زمان مرتب سازی shell از رابطه n پیروی می‌کند که نسبت به n^۲ بهبود خوبی پیدا کرده‌است لذا سرعت عمل روش مرتب سازی shell از روشهای انتخابی ، در جی و حبابی بیشتر است.پیاده سازی مرتب سازی Shell sort)) در c++ :
    #include<stdio.h>#include<conio.h>< include<string.h#Void shell(int *,char*,int)Int main(){ Char s[۸۰]; Int gap[۸۰]; (); Clrscr ;(«: Printf(» Enter a string ); Gets(s )); Shell(gap,s,strlen(s ); Printf(«\n the sorted string is : ٪s»,s Getch(); Return ۰;}****************************//Void shell(int gap [], char * item, int count){ Register int I, j,step,k,p; ; Char x Gap[۰] =count /۲; While(gap[k] > ۱){ ++; KGap[k]=gap[k-۱]/۲;}//end of whileFor (i= ۰;i<=k;i++){Step=gap[i];For(j=step;j<count; j++){X=item[j];P=j-step; While(p>=۰ && x<item[p]){Item[p+step]=item[p];P=p-step;}Item[p+step]=x; }} }


    [[مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]] مرتب سازی سریع

    (به [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]: Quick Sort)
    مرتب سازی سریع (Quick Sort) از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شه. این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. به این ترتیب که داده‌ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده‌ها رو مرتب می‌کنه. برای اینکار یکی از داده‌ها (مثلا داده اول) به عنوان محور انتخاب می‌شه. داده‌ها بر اساس محور طوری چینش می‌شن که همه داده‌های کوچکتر از محور سمت چپ و داده‌های بزرگتر یا مساوی اون سمت راستش قرار می‌گیرن. با مرتب کردن دو قسمت به دست اومده کل داده‌ها مرتب می‌شن. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچکتر هستن و بالعکس. مثلا اعداد صحیح زیر رو در نظر بگیرید:
    ۵ ۶ ۱ ۹ -۲ ۴ ۵ ۱۵ ۳ ۱ ۴ ۱۰

    عدد ۵ رو به عنوان محور در نظر می‌گیریم. داده‌ها به این صورت بازچینی می‌شن:
    ۱ -۲ ۴ ۳ ۱ ۴ ۵ ۶ ۹ ۵ ۱۵ ۱۰

    همونطور که مشاهده می‌کنید اعداد سمت چپ عدد ۵ زیر خط دار همگی از ۵ کوچیکتر و اعداد سمت راست بزرگتر یا مساوی اون هستن.
    پیاده سازی مرتب سازی Quick sort)) در c++
    تابع partition با دریافت آرایه و حد بالا و پایین تکه‌ای که باید تقسیم بشه عملیات لازم رو انجام می‌ده، و اندیس محل تفکیک رو (محل عدد ۵ در مثال بالا) به عنوان نتیجه بر می‌گردونه.
    int partition (int arr[ ] , int low , int high) { int lb = low + ۱ , rb = high , temp , pivot = arr[ low ] , p; while (lb <= rb) { while (arr[ lb ] <= pivot && lb <= rb) lb++; while (arr[ rb ] > pivot && lb <= rb) rb--; if (lb < rb) { temp = arr[ lb]; arr[ lb ] = arr[ rb]; arr[ rb ] = temp; } } (if (rb == high p = high; else if(rb == low) p = low; else p = lb – ۱; arr[ low ] = arr[ p]; arr[ p ] = pivot; return p;}
    اگه این تابع رو برای مثال بالا استفاده کنیم مقدار ۶ (اندیس ۵ زیرخط دار) برگشت داده می‌شه. با تکرار کردن این عملیات برای دو قسمت به دست اومده (در مثال بالا از اندیس صفر تا ۵ و از اندیس ۷ تا ۱۱) داده‌ها به صورت کامل مرتب می‌شن.
    بر اساس گفته‌های بالا تابع مرتب سازی به این صورت خواهد بود:
    void quick_sort (int arr[ ] , int low , int high){if (low < high) { int p = partition(arr , low , high); quick_sort(arr , low , p – ۱); quick_sort(arr , p + ۱ , high); }}
    همونطور که مشاهده می‌کنید این تابع بصورت بازگشتی نوشته شده. در صورتی که بخواید به صورت غیر بازگشتی بنویسید باید از پشته به صورت زیر استفاده کنید:
    void quick_sort (int arr[ ] ,int n){ stack st; st.push(۰); st.push(n – ۱); int low , p , high; while(! st.isempty()) { high = st.pop(); low = st.pop(); p = partition(arr , low , high); if (p > low) { st.push(low); st.push(p – ۱); } if (p < high) { st.push(p + ۱); st.push(high); }}}

    ۵ - مرتب سازی ادغامSort) Merge)

    روش مرتب سازی ادغام از الگوریتم تقسیم و حل (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;


    این توابع اونقدر ساده هستن که نیاز به هیچ توضیحی ندارن. فقط می‌مونه تابع merge_array که دو زیر آرایه رو با هم ادغام می‌کنه.
    void merge (int arr[ ] , int low , int mid , int high){ register int i , j , k , t; j = low; for (i = mid + ۱ ; 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 – ۱]; arr[ j ] = t; }}procedure merge_array (var arr : array of integer ; l : integer ; m : integer ; h : integer); var i , j , k , t : integer; begin j := l; for i := m + ۱ to h do begin while (arr[ j ] <= arr[ i ]) and (j < i) do inc (j); if j = i then break; t := arr[ i]; for k := i downto j + ۱ do arr[ k ] := arr[ k – ۱]; arr[ j ] := t; end; End;


    تابع merge_array خود آرایه و اندیسهای بالا ، پایین و جداکننده زیر آرایه‌ای رو که باید ادغام بشه دریافت می‌کنه ، و به صورت درجا (بدون استفاده از آرایه کمکی) دو قمست مرتب شده زیر آرایه رو ادغام می‌کنه.
    ۶ - مرتب سازی درجی (Insertion Sort)
    مرتب سازی درجی (Insertion Sort) یکی از روشهای مرتب سازی رایج و البته نه چندان کارا محسوب می‌شه. این روش در مقایسه با مرتب سازی حبابی و انتخابی سرعت بهتری داره و برای مرتب کردن تعداد کمی از عناصر مناسبه. به همین خاطر مراخل انتهایی روش مرتب سازی سریع (Quick Sort) با کمک گرفتن از این روش انجام می‌گیره.
    الگوریتم مرتب سازی درجی بر اساس مرتب سازیهایی که معمولا خود ما بصورت دستی انجام می‌دیم طراحی شده. فرض کنید دسته کارتی با شماره‌های ۱ تا ۱۰ بصورت نامرتب و کنار هم روی زمین چیده شدن:
    ۵ ۲ ۹ ۳ ۱ ۱۰ ۴ ۶ ۸ ۷
    کارت دوم رو نسبت به کارت اول در جای مناسب خودش قرار می‌دیم:
    ۲ ۵ ۹ ۳ ۱ ۱۰ ۴ ۶ ۸ ۷
    حالا نوبت به کارت سوم می‌رسه. این کارت رو نسبت به دو کارت قبلی در جای مناسب قرار می‌دیم. چون ۹ در مقایسه با ۲ و ۵ جای درستی داره بدون هیچ جابجایی به کارت چهارم می‌رسیم. جای این کارت رو نسبت به سه کارت قبلی مشخص می‌کنیم:
    ۲ ۳ ۵ ۹ ۱ ۱۰ ۴ ۶ ۸ ۷
    و به همین ترتیب تا آخر ادامه می‌دیم.
    اگه n تعداد عناصر رو مشخص کنه ، این روش n - ۱ مرحله رو برای مرتب کردن طی می‌کنه. بعد از اتمام مرحله i ام مطمئنا i + ۱ عنصر اول به صورت مرتب شده هستن (قسمتی که زیرشون خط کشیده شده). این مساله یکی از حسنهای مرتب سازی درجی محسوب می‌شه: در هر مرحله حتما قطعه‌ای از عناصر مرتب شذه هستن. مرتب سازی حبابی این ویژگی رو نداره.
    پیاده سازی(مرتب سازی درجی) در c++
    void insertion_sort (int arr[ ] , int n){ register int i , j , t; (++ for (i = ۱ ; i < n ; i } ]; t = arr[ i (-- for (j = i ; j > ۰ && arr[ j - ۱ ] >= t ; j ; arr[ j ] = arr[ j - ۱] arr[ i ] = t; }}

    ۷ - مرتب سازی Heep Sort))

    یک الگوریتم مرتب سازی در حافظه (RAM) میباشد. Heap یک درخت دودویی کامل است با ارتفاع Height = ëlog nû هر گره (node) یک کلید بیشتر ندارد که بزرگتر یا برابر کلید گره پدر (parent) میباشد. بصورت یک آرایه (Array) ذخیره میشود. برای هر گره (i) فرزندان آن در گره‌های (۲i) و (۲i+۱) ذخیره شده‌اند. پدر هر گره (j) در گره (j/۲) میباشد.
    الگوریتم Insert در Heap Sort چگونه است؟
    ۱) رکورد جدید در آخر Heap اضافه میشود.
    ۱) کلید آن با کلید گره پدر مقایسه می‌شود و اگر مقدار آن کوچکتر بود محل آن با محل گره پدر تعویض میشود.
    ۱) در صورت لزوم عمل (۲) تا ریشه درخت (Root) ادامه مییابد.
    الگوریتم Remove در Heap Sort چگونه است؟ ۱) کوچکترین کلید که در گره Root میباشد خارج میشود. ۲) بزرگترین کلید (آخرین گره) به گره Root منتقل میگردد. ۳) کلید آن با کوچکترین کلید فرزند مقایسه می‌شود و اگر بیشتر بود جای آن دو تعویض میشود. ۴) در صورت لزوم عمل (۳) تا آخر Heap تکرار میگردد.

  3. #3
    تازه وارد
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2007/4
    امتیاز
    10
    پست ها
    3

    پيش فرض

    يه دنيا ممنون

  4. #4
    کاربر فعال تالار شیمی آواتار S H i M A
    تاريخ عضويت
    2007/3
    امتیاز
    9738
    پست ها
    2,292

    پيش فرض

    مرتب سازی (Shell Sort):

    نام این الگوریتم از نام مخترع آن گرفته شده‌است. در این الگوریتم از روش درج

    استفاده می‌شود .

    به عنوان مثال رشته f d a c b e را تحت این الگوریتم مرتب می‌کنیم:


    F d a c b e : شروع

    C d a f d e : مرحله اول

    A b c d e f : مرحله دوم

    A b c d e f : نتیجه


    منظور از فاصله سه این است که عنصر اول با عنصر چهارم (۳+۱) ،

    عنصر دوم با عنصر پنجم (۵=۳+۲) و عنصر سوم با عنصر ششم (۶=۳+۳)


    مقایسه شده در جای مناسب خود قرار می‌گیرد .


    برای انتخاب فاصله در اولین مرحله ، تعداد عناصر لیست بر ۲ تقسیم می‌شود (n/۲)


    و فاصله بعدی نیز با تقسیم فاصله فعلی بر ۲ حاصل می‌گردد و الگریتم تا زمانی ادامه


    پیدا می‌کند که این فاصله به صفر برسد.


    برای نمونه اگر تعداد عناصر برابر با ۱۰ باشد ، فاصله در مرحله اول برابر با ۵ ، در مرحله


    دوم برابر با ۲ و در مرحله سوم برابر با ۱ و در نهایت برابر با صفر خواهد بود .


    زمان مرتب سازی shell از رابطه n پیروی می‌کند که نسبت به n^۲بهبود خوبی پیدا


    کرده‌است لذا سرعت عمل روش مرتب سازی shell از روشهای انتخابی، درجی و حبابی


    بیشتر است.


    پیاده سازی مرتب سازی Shell sort در c++ :


    #include<stdio.h>


    #include<conio.h>


    < include<string.h#



    (Void shell(int *,char*,int

    Int main()


    Char s[
    ۸۰];}



    (); Clrscr

    ;(«: Printf(» Enter a string

    ); Gets(s

    )); Shell(gap,s,strlen(s

    ); Printf(«\n the sorted string is :
    ٪s»,s

    Getch();

    {Return
    ۰;

    ****************************//


    Void shell(int gap [], char * item, int count)

    {

    Register int I, j,step,k,p;


    ; Char x


    Gap[
    ۰] =count /۲;

    While(gap[k] >
    ۱)


    {


    ++; K

    Gap[k]=gap[k-
    ۱]/۲;


    }//end of while


    For (i= ۰;i<=k;i++)


    {


    Step=gap[i];


    For(j=step;j<count; j++)


    {


    X=item[j];


    P=j-step;

    While(p>=
    ۰ && x<item[p])


    {


    Item[p+step]=item[p];


    P=p-step;

    }

    Item[p+step]=x;

    }

    }

    }





    2- مرتب سازی سریع (Quick Sort) :


    از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شه.


    این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن


    داده‌ها استفاده می‌کنه.


    به این ترتیب که داده‌ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده‌ها رو


    مرتب می‌کنه.


    برای اینکار یکی از داده‌ها (مثلا داده اول) به عنوان محور انتخاب می‌شه. داده‌ها بر اساس


    محور طوری چینش می‌شن که همه داده‌های کوچکتر از محور سمت چپ و داده‌های

    بزرگتر یا مساوی اون سمت راستش قرار می‌گیرن.


    با مرتب کردن دو قسمت به دست اومده کل داده‌ها مرتب می‌شن.


    در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت


    راست همگی از قسمت سمت چپ کوچکتر هستن و بالعکس.


    مثلا اعداد صحیح زیر رو در نظر بگیرید:

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


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


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

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

    و اعداد سمت راست بزرگتر یا مساوی اون هستن


    پیاده سازی مرتب سازی Quick sort در c++:


    تابع partition با دریافت آرایه و حد بالا و پایین تکه‌ای که باید تقسیم بشه عملیات


    لازم رو انجام می‌ده، و اندیس محل تفکیک رو (محل عدد ۵ در مثال بالا) به عنوان


    نتیجه بر می‌گردونه.

    int partition (int arr[ ] , int low , int high)


    {


    int lb = low +
    ۱ , rb = high , temp , pivot = arr[ low ] , p;


    while (lb <= rb)


    {


    while (arr[ lb ] <= pivot && lb <= rb)


    lb++;


    while (arr[ rb ] > pivot && lb <= rb)


    rb--;


    if (lb < rb)


    {


    temp = arr[ lb];


    arr[ lb ] = arr[ rb];


    arr[ rb ] = temp;


    }


    }


    (if (rb == high


    p = high;


    else if(rb == low)


    p = low;


    else


    p = lb –
    ۱;


    arr[ low ] = arr[ p];


    arr[ p ] = pivot;


    return p;


    }


    اگه این تابع رو برای مثال بالا استفاده کنیم مقدار ۶ (اندیس ۵ زیرخط دار) برگشت


    داده می‌شه.


    با تکرار کردن این عملیات برای دو قسمت به دست اومده (در مثال بالا از اندیس صفر


    تا ۵ و از اندیس ۷ تا ۱۱) داده‌ها به صورت کامل مرتب می‌شن.


    بر اساس گفته‌های بالا تابع مرتب سازی به این صورت خواهد بود:

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


    {


    if (low < high)


    {


    int p = partition(arr , low , high);



    quick_sort(arr , low , p –
    ۱);



    quick_sort(arr , p +
    ۱ , high);


    }


    }



    همونطور که مشاهده می‌کنید این تابع بصورت بازگشتی نوشته شده.


    در صورتی که بخواید به صورت غیر بازگشتی بنویسید باید از پشته


    به صورت زیر استفاده کنید:


    void quick_sort (int arr[ ] ,int n)


    {


    stack st;



    st.push(
    ۰);


    st.push(n –
    ۱);


    int low , p , high;


    while(! st.isempty())


    {


    high = st.pop();


    low = st.pop();


    p = partition(arr , low , high);


    if (p > low)


    {


    st.push(low);



    st.push(p –
    ۱);


    }


    if (p < high)


    {


    st.push(p +
    ۱);


    st.push(high);


    }

    }

    }




    3- مرتب سازی Heep Sort:

    یک الگوریتم مرتب سازی در حافظه (RAM) میباشد. Heap یک درخت دودویی کامل است

    با ارتفاع Height = ëlog nû هر گره (node) یک کلید بیشتر ندارد که بزرگتر یا برابر کلید گره

    پدر (parent) میباشد.

    بصورت یک آرایه (Array) ذخیره میشود.

    برای هر گره (i) فرزندان آن در گره‌های (۲i) و (۲i+۱) ذخیره شده‌اند. پدر هر گره (j) در گره

    (j/۲) میباشد.


    الگوریتم Insert در Heap Sort چگونه است؟

    ۱) رکورد جدید در آخر Heap اضافه میشود.


    ۱) کلید آن با کلید گره پدر مقایسه می‌شود و اگر مقدار آن کوچکتر بود محل آن با محل

    گره پدر تعویض میشود.


    ۱) در صورت لزوم عمل (۲) تا ریشه درخت (Root) ادامه مییابد.

    الگوریتم Remove در Heap Sort چگونه است؟ ۱

    ) کوچکترین کلید که در گره Root میباشد خارج میشود.

    ۲) بزرگترین کلید (آخرین گره) به گره Root منتقل میگردد.

    ۳) کلید آن با کوچکترین کلید فرزند مقایسه می‌شود و اگر بیشتر بود جای آن دو تعویض

    میشود.

    ۴) در صورت لزوم عمل (۳) تا آخر Heap تکرار میگردد.




    فهرست الگوریتم‌های مرتب‌سازی:

    توضیح:

    تعداد داده‌ها و k تعداد داده‌ها با کلیدهای متفاوت است.

    بهترین، میانگین و بدترین، پیچیدگی در هر حالت را نشان می‌دهد و حافظه بیانگر

    مقدار حافظهٔ کمکی (علاوه بر خود داده‌ها) است.



    نام: Shell sort

    بهترین: (O(n log n

    میانگین: ___

    بدترین: (O(n log۲n

    حافظه: (O(۱

    پایدار: خیر

    روش: درجی




    نام: Heapsort

    بهترین: (O(n log n

    میانگین: ___

    بدترین: (O(n log n

    حافظه: (O(۱

    پایدار: خیر

    روش: گزینشی




    نام: Quicksort

    بهترین: (O(n log n

    میانگین: (O(n log n

    بدترین: (O(n۲

    حافظه: (O(n

    پایدار: خیر

    روش: Partitioning




    نام: Radix sort

    بهترین: (O(nk

    میانگین: ____

    بدترین: (O(nk

    حافظه: (O(n

    پایدار: بله

    روش: Indexing




    شخصیت منو با برخوردم اشتباه نگیر!


    شخصیت من چیزیه که "من" هستم اما برخوردِ من بستگی به این داره که "تو" کی هستی...!




  5. #5
    تازه وارد
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2007/4
    امتیاز
    14
    پست ها
    4

    پيش فرض

    اميدوارم موفق باشي و نوشته ها به دردت بخوره

  6. #6
    تازه وارد آواتار music
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2008/5
    امتیاز
    10
    پست ها
    3

    پيش فرض

    ممکنه برنامه کامل quick sort, heapsort , merge sort به زبون ++C بزارید. ممنون

تاپیک های مشابه

  1. مرتب سازی به سادگی
    توسط microsoft در تالار سیستم عامل
    پاسخ ها: 0
    آخرین ارسال: 2007/12/31, 07:59 PM

عبارت‌های مرتبط

برنامه های انواع مرتب سازی به زبان c

انواع مرتب سازی

انواع sort

مرتب سازی shell

انواع الگوریتم مرتب سازی مثالویژوال بیسیک جابجایی bubble sortالگوریتم مرتب سازی دودویی به زبان #Cمرتب سازی آرایه به روش مرتب سازی حبابی به زبان اسمبلی

ثبت اين صفحه

ثبت اين صفحه

قوانين ارسال

  • شما نمی‌توانيد تاپيک جديد ارسال كنيد
  • شما نمی‌توانيد پاسخ ارسال كنيد
  • شما نمی‌توانید فایل ضمیمه ارسال كنيد
  • شما نمی‌توانيدنوشته‌های خود را ويرايش كنيد
  •