پاورپوینت در موردآرايه ها و مرتب سازي
نوع فایل : پاورپوینت( Power Point )قابل ویرایش
تعداداسلایدها : 28 اسلاید
بخشی ازاسلایدها:
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 4 5 7 9 10] را بازرسي کنيم.
lمعمولا مرتب سازي يکبار انجام مي گيرد و پس از آن، افزودن اعضاي جديد به آرايه با الگوريتم هايي که ترتيب را حفظ مي کنند، انجام مي شود.
–الگوريتم بکار رفته براي مرتب سازي ممکن است بسيار زمانبر يا پر مصرف باشد. بنابراين سعي بر اين است که الگوريتمهايي طراحي کنيم که هزينه کمتري داشته باشند
lالگوريتم طراحي شده و برنامه نوشته شده بايد :
–درست باشد.
–از منابع موجود به نحو مناسب استفاده كند.
–با برنامه هاي ديگر بنحو مسالمت آميز اجرا شود.
–پياده سازي آن راحت باشد.
lمرتب سازي
–براي يافتن يک عضو خاص، بايد تمام اعضاي آرايه را بازبيني کرد. براي آرايه هاي خيلي بزرگ اين کار زمان زيادي مي برد
–اگر آرايه مرتب شد باشد يعني يک رابطه ترتيب مثل : for all i , j if i < j à A[i]<= A[j] بين تمام اعضاي آن برقرار باشد، محدوده جستجوي لازم براي يافتن عضو مورد نظر کوچکتر مي شود.
lمثال: براي يافتن عضو (3) تنها کافي است نيمه اول آرايه [1 2 3 4 5 7 9 10] را بازرسي کنيم.
lمعمولا مرتب سازي يکبار انجام مي گيرد و پس از آن، افزودن اعضاي جديد به آرايه با الگوريتم هايي که ترتيب را حفظ مي کنند، انجام مي شود.
–الگوريتم بکار رفته براي مرتب سازي ممکن است بسيار زمانبر يا پر مصرف باشد. بنابراين سعي بر اين است که الگوريتمهايي طراحي کنيم که هزينه کمتري داشته باشند
lالگوريتم طراحي شده و برنامه نوشته شده بايد :
–درست باشد.
–از منابع موجود به نحو مناسب استفاده كند.
–با برنامه هاي ديگر بنحو مسالمت آميز اجرا شود.
–پياده سازي آن راحت باشد.
lمرتب سازي
–براي يافتن يک عضو خاص، بايد تمام اعضاي آرايه را بازبيني کرد. براي آرايه هاي خيلي بزرگ اين کار زمان زيادي مي برد
–اگر آرايه مرتب شد باشد يعني يک رابطه ترتيب مثل : for all i , j if i < j à A[i]<= A[j] بين تمام اعضاي آن برقرار باشد، محدوده جستجوي لازم براي يافتن عضو مورد نظر کوچکتر مي شود.
lمثال: براي يافتن عضو (3) تنها کافي است نيمه اول آرايه [1 2 3 4 5 7 9 10] را بازرسي کنيم.
lمعمولا مرتب سازي يکبار انجام مي گيرد و پس از آن، افزودن اعضاي جديد به آرايه با الگوريتم هايي که ترتيب را حفظ مي کنند، انجام مي شود.
–الگوريتم بکار رفته براي مرتب سازي ممکن است بسيار زمانبر يا پر مصرف باشد. بنابراين سعي بر اين است که الگوريتمهايي طراحي کنيم که هزينه کمتري داشته باشند
lالگوريتم طراحي شده و برنامه نوشته شده بايد :
–درست باشد.
–از منابع موجود به نحو مناسب استفاده كند.
–با برنامه هاي ديگر بنحو مسالمت آميز اجرا شود.
–پياده سازي آن راحت باشد.
lادغام دو آرايه مرتب
–الحاق دو آرايه و مرتب سازي آن ß هزينه: O(N2)
–ادغام دو آرايه با حفظ ترتيب
lدو آرايه Lو Rبتنهايي مرتب هستند. به منظور ادغام با حفظ ترتيب:
–با افزودن يك عدد بسيار بزرگ انتهاي L و R را مشخص مي كنيم
– در يك حلقه تكراري، كوچكترين عضو”فعلي” اين دو را انتخاب و يادداشت مي كنيم.
–محل “فعلي” آرايه انتخاب شده را يك واحد افزايش مي دهيم
