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

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

اسلاید 1 :

آرايه ها و مرتب سازي
ساختمان داده ها و الگوريتمها

اسلاید 2 :

آرايه
آرايه مجموعه اي محدود و معين از عناصر هم نوع است
مثال :,5] [1 ,2,3,4
اعضاي آرايه به صورت صريح تعريف مي شوند
آرايه با اعضاي آن به صورت کامل مشخص مي شود
تعاريف رياضي و مفهومي مانند “ مجموعه اعداد اول کوچکتر از 100” در اينجا استفاده نمي شود
اعمال روي آرايه
ساخت آرايه: شامل اختصاص حافظه به تعداد معين و از نوع معين است:
X = Create_Array(‘integer’ , 100);
دسترسي براي مقدار دهي به آرايه از طريق يک انديس و عملگر []انجام مي گيرد: x[2] = 5
خواندن مقدار آرايه هم با همين عملگر ميسر است: y = x[34]
جستجو در آرايه و مرتب سازي آن به منظور جستجوي سريعتر، مهمترين اعمال سطح بالاي آرايه هستند

اسلاید 3 :

مرتب سازي
مرتب سازي
براي يافتن يک عضو خاص، بايد تمام اعضاي آرايه را بازبيني کرد. براي آرايه هاي خيلي بزرگ اين کار زمان زيادي مي برد
اگر آرايه مرتب شد باشد يعني يک رابطه ترتيب مثل : for all i , j if i < j  A[i]<= A[j] بين تمام اعضاي آن برقرار باشد، محدوده جستجوي لازم براي يافتن عضو مورد نظر کوچکتر مي شود.
مثال: براي يافتن عضو (3) تنها کافي است نيمه اول آرايه [1 2 3 4 5 7 9 10] را بازرسي کنيم.
معمولا مرتب سازي يکبار انجام مي گيرد و پس از آن، افزودن اعضاي جديد به آرايه با الگوريتم هايي که ترتيب را حفظ مي کنند، انجام مي شود.
الگوريتم بکار رفته براي مرتب سازي ممکن است بسيار زمانبر يا پر مصرف باشد. بنابراين سعي بر اين است که الگوريتمهايي طراحي کنيم که هزينه کمتري داشته باشند
الگوريتم طراحي شده و برنامه نوشته شده بايد :
درست باشد.
از منابع موجود به نحو مناسب استفاده كند.
با برنامه هاي ديگر بنحو مسالمت آميز اجرا شود.
پياده سازي آن راحت باشد.

اسلاید 4 :

يك الگوريتم مرتب سازي
void anysort(int [] A){
int N = A.length ;
int flag = 1 ;
while (flag ==1 ){
flag = 0 ;
for (int k=0 ; k < N -1 ; k ++ )
if (A[k] > A[k+1] ){
int temp = A[k] ;
A[k] = A[k+1] ;
A[k+1] = temp ;
flag = 1 ;
}
}
}
هزينه
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
تكرار
1
1
N
N
N
N(N-1)
N(N-1)
N(N-1)
N(N-1)
N(N-1)

اسلاید 5 :

هزينه الگوريتم
هزينه كل:
C1 +( N -1)( C2 + C3 + C4 + C5) + N(N-1) ( C6 + C7 + C8 + C9 + C10)

= a N2 + b N +c
هزينه
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
تكرار
1
1
N
N
N-1
N(N-1)
N(N-1)
N(N-1)
N(N-1)
N(N-1)

اسلاید 6 :

بررسي درستي الگوريتم مرتب سازي
while (flag ==1 ){
flag = 0 ;
for (int k=0 ; k < N -1 ; k ++ )
if (A[k] > A[k+1] ){
swap(A[k] , A[k+1] ) ;
flag = 1 ;
}
}
∀ k∊ [0..N -1] , A[k] >= A[k-1]

اسلاید 7 :

اثبات درستي
:فرض∀ k∊ [0..N -1] , A[k] >= A[k-1]
if ∃ m , n : m A[n] then:
A[m] > A[n -1] , A[m] > A[n-2] … A[m] > A[m+1]
A[m] > A[m+1]  خلاف فرض
الگوريتم درست اجرا مي شود

اسلاید 8 :

Bubble Sort
void anysort(int [] A){
int N = A.length ;
int flag = 1 ;
for( i=0 ; i < N ; i++ ){
for(j=N-1; j > i ; j -- ) {
if ( A[j] < A[j-1])
swap (A[j] , A[j-1] ) ;
}
}
}
هزينه
C1
C2
C3
C4
C5
C6
تكرار
1
1
N
1+2+…+N
1+2+…+N
1+2+…+N
1+2+…+ n = ½ n ( n +1 )
هزينه الگوريتم = O(N2)

اسلاید 9 :

Insertion Sort
void anysort(int [] A){
int N = A.length ;
for( i=1 ; i < N ; i++ ){
key = A[i]
for(j=i-1; j >= 0 && A[j] > key ; j-- ) {
A[j+1] = A[j] ;
}
A[j + 1] = key ;
}
}
هزينه
C1
C3
C4
C5
C6
C7
تكرار
1
N
N-1
1+2+…+N-1
1+2+…+N-1
N-1
هزينه الگوريتم = O(N2)

اسلاید 10 :

رشد توابع
f1(N) = 5N2 , f2(N) = 0.01 N3
Nf1f2
1050010
1005000010000
50012500001250000
1000500000010000000f2 = 2 f1
for N>500, f2 > f1

اسلاید 11 :

روشهاي ديگر مرتب سازي
استراتژي تقسيم و حل: Divide and Conquer
مرتب سازي با ادغامMerge Sort
مرتب سازي سريعQuick Sort
مرتب سازي خطي
Index Sort ، Counting Sort، Radix Sort
ساختمان داده هاي ويژه
Heap Sort
اين روشها را به مرور در اين درس مطالعه خواهيم کرد.

اسلاید 12 :

تقسيم و حل
حل مسائل بزرگ بوسيله تقسيم به مسايل كوچكتر
تقسيم مساله به چند قسمت
حل مسايل كوچك
ادغام پاسخ مسايل كوچك براي بدست آوردن پاسخ مساله اصلي
مثال:
پيدا كردن مينيمم يك آرايه
آرايه را به چند بخش تقسيم کرده و مينيمم هر بخش را پيدا مي کنيم. در انتها، مينيمم اين مقادير را بعنوان مينيمم آرايه گزارش مي کنيم.

اسلاید 13 :

مرتب سازي به روش تقسيم و حل
ادغام دو آرايه مرتب
الحاق دو آرايه و مرتب سازي آن  هزينه: O(N2)
ادغام دو آرايه با حفظ ترتيب
دو آرايه Lو Rبتنهايي مرتب هستند. به منظور ادغام با حفظ ترتيب:
با افزودن يك عدد بسيار بزرگ انتهاي L و R را مشخص مي كنيم
در يك حلقه تكراري، كوچكترين عضو”فعلي” اين دو را انتخاب و يادداشت مي كنيم.
محل “فعلي” آرايه انتخاب شده را يك واحد افزايش مي دهيم

اسلاید 14 :

مرتب سازي با ادغام
آرايه A=[4 2 7 5 2 1 6 3] را مرتب كنيد
اين آرايه را به دو آرايه هم اندازه تقسيم مي كنيم:
L=[4 2 7 5], R=[2 1 6 3]
هر كدام از اين دو آرايه را مرتب مي كنيم
L=[2 4 5 7], R=[1 2 3 6]
و در نهايت اين دو را با حفظ ترتيب، ادغام مي كنيم:
A=[1 2 2 3 4 5 6 7]

اسلاید 15 :

ادغام با حفظ ترتيب
MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
create arrays L[0 ‥ n1] and R[0 ‥ n2] :
for (i = 0 ; i < n1 ; i ++ ) L[i] = A[p + i - 1]
for( j = 0 ; j < n2 ; j ++ ) R[j] = A[q + j]
L[n1] = ∞
R[n2] = ∞
i = 0 , j = 0
for k = p to r
if (L[i] ≤ R[j] ) { A[k] =L[i] , i++ }
else { A[k] = R[j] , j++ }
مرتب سازي آرايه Aاز pتا r.
q محل عضو مياني براي تقسيم آرايه است
1
1
1
n1
n2
1
1
1
r-p+1
r-p+1
r-p+1
هزينه الگوريتم = a (n1 + n2) + b = O(n)

اسلاید 16 :

ادغام با حفظ ترتيب 1
قسمت مرتب شده اين آرايه را با رنگ روشن مشخص مي كنيم. آرايه هاي Rو L مرتب هستند. عناصري از اين آرايه ها را كه انتخاب و ادغام شده باشند، با رنگ تيره نشان مي دهيم.
نشان مي دهيم در پايان الگوريتم ادغام، آرايه A مرتب بوده و R و L به انتها رسيده اند.
هنگام شروع، بخش مرتب شده آرايه A خالي است، بنابراين مرتب است!

اسلاید 17 :

ادغام با حفظ ترتيب 2
: قدم اولR[1] < L[1]  A[9] = R[1]
قسمتي از آرايه Aكه با رنگ روشن مشخص شده، مرتب است. R[1]انتخاب شده و رنگ آن تيره شده است.

اسلاید 18 :

ادغام با حفظ ترتيب 3
قدم دوم: L[1] < R[2]  A[10] = L[1]
آرايه A كوچكترين عناصر Lو R را دارد. ترتيب
اين عناصر با مقايسه L[i] , R[j] مشخص مي شود
بنابراين بعد از هر تكرار، آرايه A كوچكترين
عناصردو آرايه L و R را در خود دارد و مرتب است.

اسلاید 19 :

ادغام با حفظ ترتيب 4
R[2] < L[2]  A[11] = R[2]

اسلاید 20 :

ادغام با حفظ ترتيب 5
در قسمت h ، آرايه R به انتهاي خود رسيده است.
عدد ∞ افزوده شده به انتهاي آن سبب مي شود
تا در تكرار هاي بعدي حلقه ادغام، اعضا باقيمانده
آرايه L انتخاب شوند. بنابراين در نهايت و بعد از
تكرار حلقه ادغام به تعداد مجموع طول دو آرايه،
آرايه A اعضاي Rو L را بصورت مرتب شده
در خود خواهد داشت.