بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

آرايه

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

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

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

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

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

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

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

lX = Create_Array(‘integer’ , 100);

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

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

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

اسلاید 2 :

مرتب سازي

lمرتب سازي

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

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

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

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

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

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

–درست باشد.

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

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

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

اسلاید 3 :

اثبات درستي

 :فرض∀ k∊ [0..N -1] , A[k] >= A[k-1]

lif ∃ m , n  : m <n , A[m] > A[n] then:

  A[m] > A[n -1] , A[m] > A[n-2] … A[m] > A[m+1]

  A[m] > A[m+1] è خلاف فرض

lالگوريتم درست اجرا مي شود

اسلاید 4 :

روشهاي ديگر مرتب سازي

lاستراتژي تقسيم و حل: Divide and Conquer

–مرتب سازي با ادغام  Merge Sort

–مرتب سازي سريع  Quick Sort

lمرتب سازي خطي

–Index Sort ، Counting Sort، Radix Sort

lساختمان داده هاي ويژه

–Heap Sort

lاين روشها را به مرور در اين درس مطالعه خواهيم کرد.

اسلاید 5 :

تقسيم و حل

lحل مسائل بزرگ بوسيله تقسيم به مسايل كوچكتر

–تقسيم مساله به چند قسمت

–حل مسايل كوچك

–ادغام پاسخ مسايل كوچك براي بدست آوردن پاسخ مساله اصلي

lمثال:

–پيدا كردن مينيمم يك آرايه

lآرايه را به چند بخش تقسيم کرده و مينيمم هر بخش را پيدا مي کنيم. در انتها، مينيمم اين مقادير را بعنوان مينيمم آرايه گزارش مي کنيم.

اسلاید 6 :

مرتب سازي به روش تقسيم و حل

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

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

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

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

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

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

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

اسلاید 7 :

مرتب سازي با ادغام

lآرايه A=[4 2 7 5 2 1 6 3] را مرتب كنيد

–اين آرايه را به دو آرايه هم اندازه تقسيم مي كنيم:

lL=[4 2 7 5], R=[2 1 6 3]

–هر كدام از اين دو آرايه را مرتب مي كنيم

lL=[2 4 5 7], R=[1 2 3 6]

–و در نهايت اين دو را با حفظ ترتيب، ادغام مي كنيم:

lA=[1 2 2 3 4 5 6 7]

 

اسلاید 8 :

ادغام با حفظ ترتيب 1

قسمت مرتب شده اين آرايه را با رنگ روشن مشخص مي كنيم. آرايه هاي Rو L مرتب هستند. عناصري از اين آرايه ها را كه انتخاب و ادغام شده باشند، با رنگ تيره نشان مي دهيم.

نشان مي دهيم در پايان الگوريتم ادغام، آرايه A مرتب بوده و R و L به انتها رسيده اند.

هنگام شروع، بخش مرتب شده آرايه A خالي است، بنابراين مرتب است!

اسلاید 9 :

ادغام با حفظ ترتيب 2

 : قدم اولR[1] < L[1] à A[9] = R[1]

قسمتي از آرايه Aكه با رنگ روشن مشخص شده، مرتب است. R[1]انتخاب شده و رنگ آن تيره شده است.

اسلاید 10 :

ادغام با حفظ ترتيب 3

قدم دوم: L[1] < R[2] à A[10] = L[1]

آرايه A كوچكترين عناصر Lو R را دارد. ترتيب

اين عناصر با مقايسه L[i] , R[j]   مشخص مي شود

بنابراين بعد از هر تكرار، آرايه A كوچكترين

عناصردو آرايه L و R را در خود دارد و مرتب است.

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید