1 of 50

Data Structures – Recitation 6

Shay Golan

Partially based on Rani Hod slides

1

2 of 50

מיונים

2

3 of 50

הגדרות במיון

קלט: איברים (נגיד כרטיסי מידע של סטודנטים) שלכל איבר מספר שדות.
אחד השדות נקרא מפתח – זהו השדה שלפי ערכו מתבצע המיון (למשל מס' ת"ז).
כאשר ממינים מערך הסדר בין כל שני איברים עם מפתח שונה בפלט מוגדר לפי יחס הסדר בין המפתחות.
אם יש במערך שני איברים עם מפתח זהה, דרישת המיון מבטיחה שהם יהיו סמוכים (בלי מפתחות אחרים ביניהם) אך לא קובעת את הסדר ביניהם.

3

4 of 50

תזכורת למיונים מוכרים

מיון הכנסה (Insertion sort)
מיון בועות (Bubble sort)
מיון בחירה (Selection sort)
מיון מהיר (Quick sort)
מיון מיזוג (Merge sort)
מיון AVL
מיון ערימה (ספוילר/תזכורת)

4

5 of 50

מיון הכנסה

5

6 of 50

מיון בועות

6

7 of 50

מיון בחירה

7

8 of 50

מיון מהיר

8

9 of 50

מיון מיזוג

9

10 of 50

מיון AVL

10

11 of 50

מיון יציב

מיון יקרא מיון יציב אם הסדר של שני איברים עם מפתח זהה בפלט המיון, יהיה הסדר שהיה להם בקלט.

שימו לב, לא כל המיונים שלמדתם הם יציבים.
למשל, מיון מהיר אינו יציב (ודאו שאתם מבינים מדוע).

11

2

3

0

5

3

5

0

2

5

A

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

A

0

1

2

3

4

5

6

7

8

0

2

3

5

3

5

2

6

0

7

1

3

4

5

8

12 of 50

שאלה

תאר שיטה להפוך כל אלגוריתם מיון מבוסס השוואות למיון יציב.
כמה זמן ומקום דורשת השיטה?

12

13 of 50

תשובה

13

14 of 50

חסם תחתון למיון

14

15 of 50

תזכורת/ספוילר

15

16 of 50

שאלה

16

17 of 50

תשובה

17

18 of 50

מיונים אחרים

18

19 of 50

מיון לא מבוסס השוואות

19

20 of 50

מיון מנייה�Count Sort

20

21 of 50

מיון מנייה

21

2

3

0

5

3

5

0

2

0

A

22 of 50

מיון מנייה

22

2

3

0

5

3

5

0

2

0

A

0

C

0

1

2

3

4

5

R=5

23 of 50

מיון מנייה

23

2

3

0

5

3

5

0

2

5

A

0

1

0

C

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

24 of 50

מיון מנייה

24

2

3

0

5

3

5

0

2

5

A

0

1

0

C

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

25 of 50

מיון מנייה

25

2

3

0

5

3

5

0

2

5

A

1

0

1

0

C

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

26 of 50

מיון מנייה

26

2

3

0

5

3

5

0

2

5

A

2

0

2

0

3

C

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

27 of 50

מיון מנייה

בעזרת המערך C בלבד: כמה מופעים של הערך 3 יש במערך המקורי?
שני מופעים.

איפה נמצאים שני המופעים האלה?
באינדקסים 4,5 – כי יש 4 איברים קטנים משלוש.

27

2

0

2

0

3

C

0

1

2

3

4

5

28 of 50

מיון מנייה

28

2

0

2

0

3

C

0

1

2

3

4

5

29 of 50

מיון מנייה

29

2

3

0

5

3

5

0

2

5

A

2

0

2

0

3

C

0

1

2

3

4

5

6

7

8

2

4

6

9

0

1

2

3

4

5

30 of 50

מיון מנייה

העבר איברים למערך הפלט

30

2

3

0

5

3

5

0

2

5

A

2

4

6

9

C

/

B

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

31 of 50

מיון מנייה

31

2

3

0

5

3

5

0

2

5

A

2

4

6

9

C

/

B

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

32 of 50

מיון מנייה

32

2

3

0

5

3

5

0

2

5

A

2

4

6

8

C

/

5

B

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

33 of 50

מיון מנייה

33

2

3

0

5

3

5

0

2

5

A

2

3

6

8

C

/

2

/

5

B

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

34 of 50

מיון מנייה

34

2

3

0

5

3

5

0

2

5

A

1

2

3

6

8

C

/

0

/

2

/

5

B

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

35 of 50

מיון מנייה

35

2

3

0

5

3

5

0

2

5

A

1

2

3

6

7

C

/

0

/

2

/

5

B

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

36 of 50

מיון מנייה

36

2

3

0

5

3

5

0

2

5

A

1

2

3

5

6

7

C

/

0

/

2

/

3

/

5

B

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

37 of 50

מיון מנייה

37

2

3

0

5

3

5

0

2

5

A

0

2

4

6

C

0

2

3

5

B

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

38 of 50

מיון מנייה

38

39 of 50

מיון מנייה

39

40 of 50

מיון מנייה

40

41 of 50

מיון מנייה – מיון יציב

מיון מניה הינו מיון יציב - כל שני איברים עם מפתח זהה שומרים על הסדר לאחר המיון.
כיוון שהסריקה שלנו מתחילה לעבור על המערך מימין לשמאל, ומעתיקה כל איבר למקום הימני ביותר שעוד פנוי ומיועד לאיברים עם מפתח זה.

42 of 50

מיון בסיס�Radix Sort

42

43 of 50

מיון בסיס - Radix-Sort

43

44 of 50

מיון בסיס - Radix-Sort

44

45 of 50

45

2

8

7

1

4

5

9

1

6

5

7

2

1

3

0

1

2

4

7

2

3

5

7

0

2

8

3

9

4

8

4

3

5

3

6

2

8

7

1

4

5

9

1

3

0

1

6

5

7

2

4

7

2

7

0

2

8

3

9

4

8

4

3

5

3

5

3

6

1

3

0

1

7

0

2

3

5

3

6

4

8

4

3

5

2

8

7

1

6

5

7

2

4

7

2

4

5

9

1

8

3

9

4

7

0

2

1

3

0

1

8

3

9

4

2

4

7

2

3

5

3

6

3

5

6

5

7

2

4

5

9

1

4

8

4

2

8

7

1

3

0

1

2

4

7

2

8

7

1

3

5

3

6

3

5

4

5

9

1

4

8

4

6

5

7

2

7

0

2

8

3

9

4

מיון בסיס - Radix-Sort

46 of 50

מיון בסיס - נכונות

46

47 of 50

מיון בסיס – יעילות

47

48 of 50

שאלה

ממשלת סין עושה מבחן לכל התלמידים בכיתה א' במדינה (n). כל תלמיד מקבל במכתב הביתה את מיקומו היחסי בין 1 ל-n מבין כל בני גילו.

הצע מבנה נתונים התומך בפעולות הבאות:

בניה: מקבלת את רשימת כל התלמידים, לכל תלמיד את המיקום היחסי שלו ואת ביה"ס בו הוא לומד.
שאילתא: מקבלת בית-ספר ומספר i, ומחזירה את התלמיד ה-i ברמתו בבית-הספר (אפשר להניח ש-i לא חורג מגודל בית הספר).

48

49 of 50

תשובה (לא יעילה)

49

50 of 50

תשובה יעילה

קודם נמיין את כל התלמידים במדינה לפי הציון היחסי.
אח"כ, נחלק את התלמידים לבתי הספר לפי הסדר.
בעת שאילתא, נחזיר את התלמיד ה-i של בית הספר.

זמן בניה – לינארי (שימו לב, המיון הוא מיון מניה).
זמן שאילתא – O(1).

50