שימוש ב- Java Applets להוראת אלגוריתמים במדעי המחשב

נספח: דף עבודה בנושא QuickSort

עירית הדר

ד"ר אורית חזן

 

הטכניון – מכון טכנולוגי לישראל

 

המחלקה להוראת הטכנולוגיה והמדעים

 

בעיות נבחרות במדעי המחשב – סמסטר ב' תשס"ב

 

לפניכם שני אתרי אינטרנט המציגים את האלגוריתם Quick Sort:

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html#qsort_anim

http://www.cs.princeton.edu/~ah/alg_anim/gawain-4.0/QuickSort.html

 

להבנת האלגוריתם קראו בעיון את ההסברים המופיעים באתרים הנ"ל, ובצעו את הפעולות הבאות:

1.       הסבירו בכתב, במילים שלכם, את אלגוריתם המיון.

2.       א. מיינו על פי האלגוריתם את מערכי המספרים הבאים. ערכו רישום למעקב על כל שלבי מימוש האלגוריתם.

39

66

5

89

17

14

52

8

16

מערך I

 

5

3

14

66

14

52

50

56

68

מערך II

 

1

3

5

23

34

36

36

52

60

מערך III

 

20

12

54

7

4

11

35

21

17

10

15

18

24

מערך IV

 

ב. כמה קריאות רקורסיביות התבצעו במהלך המיון על כל אחד מהמערכים?

 

3. א.  בנו מערך בן 15 איברים שבתהליך מיונו ע"י האלגוריתם Quick Sort מתבצעות 8 קריאות רקורסיביות.

ב. בנו מערך בן 15 איברים שבתהליך מיונו ע"י האלגוריתם Quick Sort מתבצעות 7 קריאות רקורסיביות.

ג. בנו מערך בן 15 איברים שבתהליך מיונו ע"י האלגוריתם Quick Sort מתבצעות  6 קריאות רקורסיביות.

ד. בנו מערך בן 15 איברים שבתהליך מיונו ע"י האלגוריתם Quick Sort מתבצעות  5 קריאות רקורסיביות.

 

4. א. עבור מערך בן 15 איברים הממוין ע"י אלגוריתם Quick Sort מצאו מהו המספר המינימלי האפשרי של קריאות רקורסיביות? בנו מערך כזה.

ב. האם קיים קשר בין גודל המערך לבין המספר המינימלי של קריאות רקורסיביות המתבצעות בתהליך מיונו ע"י אלגוריתם Quick Sort? אם כן – מהו קשר זה?

ג. עבור מערך בן 15 איברים הממוין ע"י אלגוריתם Quick Sort מצאו מהו המספר המקסימלי האפשרי של קריאות רקורסיביות? בנו מערך כזה.

ד. האם קיים קשר בין גודל המערך לבין המספר המקסימלי של קריאות רקורסיביות המתבצעות בתהליך מיונו ע"י אלגוריתם Quick Sort? אם כן – מהו קשר זה?

לאתר המרכז

לכנס תשס"ג

לתקציר ההרצאה

חזרה