1 of 69

רקורסיות

צביקה ברגר

מבני נתונים

​

מיונים

צביקה ברגר

בס"ד

2 of 69

מיון

בס"ד

1

3

8

4

2

9

6

7

5

3 of 69

מיון

בס"ד

1

3

8

4

2

9

6

7

5

9

8

7

6

5

4

3

2

1

4 of 69

מיונים מוכרים

​

  • Bubble sort
  • Merge sort
  • Quick sort
  • Insertion sort
  • Heap sort

בס"ד

5 of 69

Bubble sort

​

    • בכל איטרציה נעבור על המערך עם "חלון" בגודל 2.

​

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

​

    • בסיום כל איטרציה המקסימום "ביעבע" לסוף המערך.
      • בתחילת איטרציה i מובטח לנו שיש i איברים שלא צריך לבדוק בסוף המערך.

​

    • מספר האיטרציות הכולל צריך להיות size-1.
      • כי באיטרציה הזו אנו מסדרים גם את האיבר המינימלי.

​

בס"ד

6 of 69

Bubble sort

בס"ד

1

3

8

4

2

9

6

7

5

מספר האיטרציה (i)

0

7 of 69

Bubble sort

בס"ד

1

3

8

4

2

9

6

7

5

מספר האיטרציה (i)

0

1

3

8

4

2

9

6

7

5

מספר האיטרציה (i)

0

מיקום במערך (j)

0

8 of 69

Bubble sort

בס"ד

1

3

8

4

2

9

6

7

5

מספר האיטרציה (i)

0

מיקום במערך (j)

1

9 of 69

Bubble sort

בס"ד

1

3

8

4

2

9

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

1

10 of 69

Bubble sort

בס"ד

1

3

8

4

2

9

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

2

11 of 69

Bubble sort

בס"ד

1

3

8

4

2

9

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

3

12 of 69

Bubble sort

בס"ד

1

3

8

4

9

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

3

13 of 69

Bubble sort

בס"ד

1

3

8

4

9

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

4

14 of 69

Bubble sort

בס"ד

1

3

8

9

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

4

15 of 69

Bubble sort

בס"ד

1

3

8

9

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

5

16 of 69

Bubble sort

בס"ד

1

3

9

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

5

17 of 69

Bubble sort

בס"ד

1

3

9

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

6

18 of 69

Bubble sort

בס"ד

1

9

3

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

6

19 of 69

Bubble sort

בס"ד

1

9

3

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

7

20 of 69

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

7

נדאג לא לגלוש מגבולות המערך

for (int j = 0; j < size-1; j++)

21 of 69

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

1

22 of 69

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

0

23 of 69

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

1

24 of 69

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

2

25 of 69

Bubble sort

בס"ד

9

1

3

8

4

7

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

2

26 of 69

Bubble sort

בס"ד

9

1

3

8

4

7

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

3

27 of 69

Bubble sort

בס"ד

9

1

3

8

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

3

28 of 69

Bubble sort

בס"ד

9

1

3

8

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

4

29 of 69

Bubble sort

בס"ד

9

1

3

8

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

5

30 of 69

Bubble sort

בס"ד

9

1

8

3

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

5

31 of 69

Bubble sort

בס"ד

9

1

8

3

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

6

32 of 69

Bubble sort

בס"ד

9

8

1

3

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

6

נשפר את התנאי

for (int j = 0; j < size-1-i; j++)

33 of 69

Bubble sort

בס"ד

9

8

1

3

7

4

2

6

5

מספר האיטרציה (i)

2

34 of 69

Bubble sort

בס"ד

9

8

1

3

7

4

2

6

5

מספר האיטרציה (i)

2

35 of 69

Bubble sort

בס"ד

9

8

7

1

3

6

4

2

5

מספר האיטרציה (i)

3

36 of 69

Bubble sort

בס"ד

9

8

7

1

3

6

4

2

5

מספר האיטרציה (i)

3

37 of 69

Bubble sort

בס"ד

9

8

7

6

1

3

5

4

2

מספר האיטרציה (i)

4

38 of 69

Bubble sort

בס"ד

9

8

7

6

1

3

5

4

2

מספר האיטרציה (i)

4

39 of 69

Bubble sort

בס"ד

9

8

7

6

5

1

3

4

2

מספר האיטרציה (i)

5

40 of 69

Bubble sort

בס"ד

9

8

7

6

5

1

3

4

2

מספר האיטרציה (i)

5

41 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

1

3

2

מספר האיטרציה (i)

6

42 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

1

3

2

מספר האיטרציה (i)

6

מיקום במערך (j)

0

43 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

1

3

2

מספר האיטרציה (i)

6

מיקום במערך (j)

1

44 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

3

1

2

מספר האיטרציה (i)

6

מיקום במערך (j)

1

45 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

3

1

2

מספר האיטרציה (i)

7

46 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

3

1

2

מספר האיטרציה (i)

7

מיקום במערך (j)

0

47 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

3

2

1

מספר האיטרציה (i)

7

מיקום במערך (j)

0

48 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

3

2

1

מספר האיטרציה (i)

8

אין צורך לבצע

נגדיר את מספר האיטרציות

for (int i = 0; i < size-1; i++)

49 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

3

2

1

for (int i = 0; i < size-1; i++)

for (int j = 0; j < size-1-i; j++)

if (should_swap(j, j+1))

swap(j, j+1)

50 of 69

Bubble sort

בס"ד

9

8

7

6

5

4

3

2

1

for (int i = 0; i < size-1; i++)

for (int j = 0; j < size-1-i; j++)

if (should_swap(j, j+1))

swap(j, j+1)

 

51 of 69

Merge Sort

בס"ד

52 of 69

Quick sort

בס"ד

1

4

2

0

5

6

9

8

1

7

2

//determining the pivot

swap(vec, left, (left+right)/2);

53 of 69

Quick sort

בס"ד

//determining the pivot

swap(vec, left, (left+right)/2);

6

4

2

0

5

1

9

8

1

7

2

k

54 of 69

Quick sort

בס"ד

6

4

2

0

5

1

9

8

1

7

2

last

i

left

right

last

i

last

i

last

i

last

i

last

i

i

i

//moving all the smaller element

for (i=left+1; i<=right; i++)

if (vec[i] < vec[left])

swap(vec, ++last, i);

55 of 69

Quick sort

בס"ד

6

4

2

0

5

1

1

8

9

7

2

k

last

i

last

i

left

right

//moving all the smaller element

for (i=left+1; i<=right; i++)

if (vec[i] < vec[left])

swap(vec, ++last, i);

56 of 69

Quick sort

בס"ד

6

4

2

0

5

1

1

8

9

7

2

k

last

i

left

right

//moving all the smaller element

for (i=left+1; i<=right; i++)

if (vec[i] < vec[left])

swap(vec, ++last, i);

57 of 69

Quick sort

בס"ד

6

4

2

0

5

1

1

2

9

7

8

k

last

i

left

right

//moving all the smaller element

for (i=left+1; i<=right; i++)

if (vec[i] < vec[left])

swap(vec, ++last, i);

58 of 69

Quick sort

בס"ד

2

4

2

0

5

1

1

6

9

7

8

last

i

left

right

//moving the pivot to its place

swap(vec,left,last);

59 of 69

Quick sort

בס"ד

2

4

2

0

5

1

1

left

right

left

right

9

7

8

//continue sorting both sides

qsort(vec, left, last-1);

qsort(vec, last+1, right);

6

60 of 69

Sort

בס"ד

61 of 69

מיונים מוכרים

​

  • Bubble sort -
  • Merge sort -
  • Quick sort -
  • Insertion sort -
  • Heap sort -

בס"ד

 

 

 

 

 

62 of 69

עצים

בס"ד

63 of 69

שאלה 1

בס"ד

64 of 69

פתרון

בס"ד

65 of 69

שאלה 2

בס"ד

66 of 69

שאלה 3

בס"ד

67 of 69

שאלה 4

בס"ד

68 of 69

פתרון

בס"ד

69 of 69

שאלות?

בס"ד