پاورپوینت موردآرایه ها مرتب سازی

نوع پاورپوینت( Power Point )قابل ویرایش

تعداداسلایدها اسلاید

بخشی ازاسلایدها:

lآرایه مجموعه ای محدود معین عناصر نوع است

–مثال :,5] [1 ,2,3,4

lاعضای آرایه صورت صریح تعریف می شوند

–آرایه اعضای آن صورت کامل مشخص می شود

–تعاریف ریاضی مفهومی “ مجموعه اعداد اول کوچکتر 100” اینجا استفاده نمی شود

lاعمال روی آرایه

–ساخت آرایه: شامل اختصاص حافظه تعداد معین نوع معین است:

lX = Create_Array(‘integer’ , 100);

–دسترسی برای مقدار دهی آرایه طریق یک اندیس عملگر []انجام می گیرد: x[2] = 5

–خواندن مقدار آرایه همین عملگر میسر است: y = x[34]

–جستجو آرایه مرتب سازی آن منظور جستجوی سریعتر، مهمترین اعمال سطح بالای آرایه هستند

lمرتب سازی

–برای یافتن یک عضو خاص، باید تمام اعضای آرایه بازبینی کرد. برای آرایه های خیلی بزرگ این کار زمان زیادی می برد

–اگر آرایه مرتب شد باشد یعنی یک رابطه ترتیب : for all i , j if  i < j à A[i]<= A[j] بین تمام اعضای آن برقرار باشد، محدوده جستجوی لازم برای یافتن عضو نظر کوچکتر می شود.

lمثال: برای یافتن عضو (3) تنها کافی است نیمه اول آرایه [1 2 3 5 7 9 10] بازرسی کنیم.

lمعمولا مرتب سازی یکبار انجام می گیرد آن، افزودن اعضای جدید آرایه الگوریتم هایی ترتیب حفظ می کنند، انجام می شود.

–الگوریتم بکار رفته برای مرتب سازی ممکن است بسیار زمانبر یا پر مصرف باشد. بنابراین سعی این است الگوریتمهایی طراحی کنیم هزینه کمتری داشته باشند

lالگوریتم طراحی شده برنامه نوشته شده باید :

–درست باشد.

–از منابع موجود نحو مناسب استفاده کند.

–با برنامه های دیگر بنحو مسالمت آمیز اجرا شود.

–پیاده سازی آن راحت باشد.

lمرتب سازی

–برای یافتن یک عضو خاص، باید تمام اعضای آرایه بازبینی کرد. برای آرایه های خیلی بزرگ این کار زمان زیادی می برد

–اگر آرایه مرتب شد باشد یعنی یک رابطه ترتیب : for all i , j if  i < j à A[i]<= A[j] بین تمام اعضای آن برقرار باشد، محدوده جستجوی لازم برای یافتن عضو نظر کوچکتر می شود.

lمثال: برای یافتن عضو (3) تنها کافی است نیمه اول آرایه [1 2 3 5 7 9 10] بازرسی کنیم.

lمعمولا مرتب سازی یکبار انجام می گیرد آن، افزودن اعضای جدید آرایه الگوریتم هایی ترتیب حفظ می کنند، انجام می شود.

–الگوریتم بکار رفته برای مرتب سازی ممکن است بسیار زمانبر یا پر مصرف باشد. بنابراین سعی این است الگوریتمهایی طراحی کنیم هزینه کمتری داشته باشند

lالگوریتم طراحی شده برنامه نوشته شده باید :

–درست باشد.

–از منابع موجود نحو مناسب استفاده کند.

–با برنامه های دیگر بنحو مسالمت آمیز اجرا شود.

–پیاده سازی آن راحت باشد.

lمرتب سازی

–برای یافتن یک عضو خاص، باید تمام اعضای آرایه بازبینی کرد. برای آرایه های خیلی بزرگ این کار زمان زیادی می برد

–اگر آرایه مرتب شد باشد یعنی یک رابطه ترتیب : for all i , j if  i < j à A[i]<= A[j] بین تمام اعضای آن برقرار باشد، محدوده جستجوی لازم برای یافتن عضو نظر کوچکتر می شود.

lمثال: برای یافتن عضو (3) تنها کافی است نیمه اول آرایه [1 2 3 5 7 9 10] بازرسی کنیم.

lمعمولا مرتب سازی یکبار انجام می گیرد آن، افزودن اعضای جدید آرایه الگوریتم هایی ترتیب حفظ می کنند، انجام می شود.

–الگوریتم بکار رفته برای مرتب سازی ممکن است بسیار زمانبر یا پر مصرف باشد. بنابراین سعی این است الگوریتمهایی طراحی کنیم هزینه کمتری داشته باشند

lالگوریتم طراحی شده برنامه نوشته شده باید :

–درست باشد.

–از منابع موجود نحو مناسب استفاده کند.

–با برنامه های دیگر بنحو مسالمت آمیز اجرا شود.

–پیاده سازی آن راحت باشد.

lادغام دو آرایه مرتب

–الحاق دو آرایه مرتب سازی آن ß هزینه: O(N2)

–ادغام دو آرایه حفظ ترتیب

lدو آرایه Lو Rبتنهایی مرتب هستند. منظور ادغام حفظ ترتیب:

–با افزودن یک عدد بسیار بزرگ انتهای  L  R را مشخص می کنیم

– یک حلقه تکراری، کوچکترین عضو”فعلی” این دو انتخاب یادداشت می کنیم.

–محل “فعلی” آرایه انتخاب شده یک واحد افزایش می دهیم