Class5_ADT_Array_Sorting_Rank-Buble-Complexity_12Jan2023.ppt

very nice and very importat

1. CS201-Data Structures and
Algorithms
•Text Books:
•T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
Introduction to Algorithms, MIT Press, 3/e, 2009.
•Y. Langsam, M. J. Augenstein, and A. M. Tenenbaum, Data
Structures Using C and C++, Prentice Hall, 2/e, 2000.
•S. Sahni, Data Structures, Algorithms, and Applications in C++ ,
Silicon Press, 2/e, 2005.
•Michael T. Goodrich, Roberto Tamassia, and David M., Data
Structures and Algorithms in C++, John Wiley & Sons, Inc., 2/e,
2004

2. Rank Sort

3. 3
INPUT : A[1..n], array of integers
OUTPUT: Rearrangement of A such that A[1]≤A[2] ≤… ≤A[n]
RANK-SORT (A)
1. for j = 1 to n
2. R[j] = 1
// Rank the n elements in A into R
3. for j = 2 to n
4. for i = 1 to j - 1
5. if A[i] <= A[j]
6. R[j] = R[j] + 1
7. else
8. R[i] = R[i] + 1
// Move to correct place in U[1 . . n]
9. for j = 1 to n
10. U[R[j]] = A[j]
// Move the sorted entries into A
11. for j = 1 to n
12. A[j] = U[j]
Rank Sort

4. INPUT : A[1..n], array of integers
OUTPUT: Rearrangement of A such that A[1]≤A[2] ≤… ≤A[n]
RANK-SORT (A)
1. for j = 1 to n
2. R[j] = 1
// Rank the n elements in A into R
3. for j = 2 to n
4. for i = 1 to j - 1
5. if A[i] <= A[j]
6. R[j] = R[j] + 1
7. else
8. R[i] = R[i] + 1
// Move to correct place in U[1 . . n]
9. for j = 1 to n
10. U[R[j]] = A[j]
// Move the sorted entries into A
11. for j = 1 to n
12. A[j] = U[j]
4
5264 1
12345
A
Rank Sort

5. 5
5264 1
12345
A
Rank Sort
11111
5264 1
12345
A
R

6. 6
11111
5264 1
12345
A
R
Rank Sort
2
j

7. 7
11111
5264 1
12345
A
R
Rank Sort
2
jji
5

8. 8
11111
5264 1
12345
A
R
Rank Sort
2
jji
5

9. 9
21111
5264 1
12345
A
R
Rank Sort
2
jji
5

10. 10
21111
5264 1
12345
A
R
Rank Sort
2
ji=j

11. 11
21111
5264 1
12345
A
R
Rank Sort
j
4

12. 12
21111
5264 1
12345
A
R
Rank Sort
j
4
i
5

13. 13
21111
5264 1
12345
A
R
Rank Sort
j
4
i
5

14. 14
31111
5264 1
12345
A
R
Rank Sort
j
4
i
5

15. 15
31111
5264 1
12345
A
R
Rank Sort
j
4
i
2

16. 16
31111
5264 1
12345
A
R
Rank Sort
j
4
i
2

17. 17
31121
5264 1
12345
A
R
Rank Sort
j
4
i
2

18. 18
31121
5264 1
12345
A
R
Rank Sort
i=j
4

19. 19
31121
5264 1
12345
A
R
Rank Sort
j
6

20. 20
31121
5264 1
12345
A
R
Rank Sort
j
6
i
5

21. 21
31121
5264 1
12345
A
R
Rank Sort
j
6
i
5

22. 22
31221
5264 1
12345
A
R
Rank Sort
j
6
i
5

23. 23
31221
5264 1
12345
A
R
Rank Sort
j
6
i
2

24. 24
31221
5264 1
12345
A
R
Rank Sort
j
6
i
2

25. 25
31321
5264 1
12345
A
R
Rank Sort
j
6
i
2

26. 26
31321
5264 1
12345
A
R
Rank Sort
j
6
i
4

27. 27
31321
5264 1
12345
A
R
Rank Sort
j
6
i
4

28. 28
31421
5264 1
12345
A
R
Rank Sort
j
6
i
4

29. 29
31421
5264 1
12345
A
R
Rank Sort
i=j
6

30. 30
31421
5264 1
12345
A
R
Rank Sort
j
1

31. 31
31421
5264 1
12345
A
R
Rank Sort
j
1
i
5

32. 32
31421
5264 1
12345
A
R
Rank Sort
j
1
i
5

33. 33
41421
5264 1
12345
A
R
Rank Sort
j
1
i
5

34. 34
41421
5264 1
12345
A
R
Rank Sort
j
1
i
2

35. 35
41421
5264 1
12345
A
R
Rank Sort
j
1
i
2

36. 36
42421
5264 1
12345
A
R
Rank Sort
j
1
i
2

37. 37
42421
5264 1
12345
A
R
Rank Sort
j
1
i
4

38. 38
42421
5264 1
12345
A
R
Rank Sort
j
1
i
4

39. 39
42431
5264 1
12345
A
R
Rank Sort
j
1
i
4

40. 40
42431
5264 1
12345
A
R
Rank Sort
j
1
i
6

41. 41
42431
5264 1
12345
A
R
Rank Sort
j
1
i
6

42. 42
42531
5264 1
12345
A
R
Rank Sort
j
1
i
6

43. 43
42531
5264 1
12345
A
R
Rank Sort
i=j
1

44. 44
42531
5264 1
12345
A
R
Rank Sort
j
1
6

45. 45
42531
5264 1
12345
A
R
Rank Sort
j
12345
U 5

46. 46
42531
5264 1
12345
A
R
Rank Sort
j
12345
U 5 2

47. 47
42531
5264 1
12345
A
R
Rank Sort
j
12345
U 5 24

48. 48
42531
5264 1
12345
A
R
Rank Sort
j
12345
U 5 246

49. 49
42531
5264 1
12345
A
R
Rank Sort
j
12345
U 5 2461

50. 50
42531
5264 1
12345
A
R
Rank Sort
j
12345
U 5 2461
A12456

51. INPUT : A[1..n], array of integers
OUTPUT: Rearrangement of A such that A[1]≤A[2] ≤… ≤A[n]
RANK-SORT (A)
1. for j = 1 to n
2. R[j] = 1
// Rank the n elements in A into R
3. for j = 2 to n
4. for i = 1 to j - 1
5. if A[i] <= A[j]
6. R[j] = R[j] + 1
7. else
8. R[i] = R[i] + 1
// Move to correct place in U[1 . . n]
9. for j = 1 to n
10. U[R[j]] = A[j]
// Move the sorted entries into A
11. for j = 1 to n
12. A[j] = U[j]
51
Rank Sort
•Best case:
•Worst case:
•Average case:
2
1 2 3
( )T n bn b n b  
2
1 2 3
( )T n an a n a  
2
1 2 3
( )T n An An A  
a
1
, a
2
and a
2
are constants
b
1
, b
2
and b
3
are constants
A
1
, A
2
and A
3
are constants

52. INPUT : A[1..n], array of integers
OUTPUT: Rearrangement of A such that A[1]≤A[2] ≤… ≤A[n]
RANK-SORT (A)
1. for j = 1 to n
2. R[j] = 1
// Rank the n elements in A into R
3. for j = 2 to n
4. for i = 1 to j - 1
5. if A[i] <= A[j]
6. R[j] = R[j] + 1
7. else
8. R[i] = R[i] + 1
// Move to correct place in U[1 . . n]
9. for j = 1 to n
10. U[R[j]] = A[j]
// Move the sorted entries into A
11. for j = 1 to n
12. A[j] = U[j]
52
Rank Sort

53. Bubble Sort

54. 54
Bubble Sort
INPUT : A[1..n], array of integers
OUTPUT: Rearrangement of A such that A[1]≤A[2] ≤… ≤A[n]
BUBBLE-SORT (A)
// Sort by bubbling the smallest element to current position.
1. j = n
2. while j ≥ 2
// Bubble up the smallest element to its correct position
3. for i = 1 to j - 1
4. if A[i] > A[i + 1]
5. temp = A[i]
6. A[i] = A[i + 1]
7. A[i + 1] = temp
8. j = j - 1

55. 55
Bubble Sort
5264 1
12345
j

56. 56
Bubble Sort
5264 1
12345
j

57. 57
Bubble Sort
5264 1
12345
j
52
ii+1

58. 58
Bubble Sort
5264 1
12345
j
52
ii+1

59. 59
Bubble Sort
5264 1
12345
j
52
ii+1
52

60. 60
Bubble Sort
2564 1
12345
j
54
ii+1

61. 61
Bubble Sort
2564 1
12345
j
54
ii+1

62. 62
Bubble Sort
2564 1
12345
j
54
ii+1
54

63. 63
Bubble Sort
2465 1
12345
j
56
ii+1

64. 64
Bubble Sort
2465 1
12345
j
56
ii+1

65. 65
Bubble Sort
2465 1
12345
j
61
ii+1

66. 66
Bubble Sort
2465 1
12345
j
61
ii+1

67. 67
Bubble Sort
2465 1
12345
j
61
ii+1
61

68. 68
Bubble Sort
2415 1
12345
j
6
i=j

69. 69
Bubble Sort
2415 6
12345
j

70. 70
Bubble Sort
2415 6
12345
j

71. 71
Bubble Sort
2415 6
12345
j
24
ii+1

72. 72
Bubble Sort
2415 6
12345
j
24
ii+1

73. 73
Bubble Sort
2415 6
12345
j
45
ii+1

74. 74
Bubble Sort
2415 6
12345
j
45
ii+1

75. 75
Bubble Sort
2415 6
12345
j
51
ii+1

76. 76
Bubble Sort
2415 6
12345
j
51
ii+1

77. 77
Bubble Sort
2415 6
12345
j
51
ii+1
51

78. 78
Bubble Sort
2411 6
12345
j
5
i=j

79. 79
Bubble Sort
2451 6
12345
j

80. 80
Bubble Sort
2451 6
12345
j

81. 81
Bubble Sort
2451 6
12345
j
24
ii+1

82. 82
Bubble Sort
2451 6
12345
j
24
ii+1

83. 83
Bubble Sort
2451 6
12345
j
41
ii+1

84. 84
Bubble Sort
2451 6
12345
j
41
ii+1

85. 85
Bubble Sort
2451 6
12345
j
41
ii+1
41

86. 86
Bubble Sort
2154 6
12345
j
4
i=j

87. 87
Bubble Sort
2154 6
12345
j

88. 88
Bubble Sort
2154 6
12345
j

89. 89
Bubble Sort
2154 6
12345
j
21
ii+1
)()(
2
nfnT

90. 90
Bubble Sort
2154 6
12345
j
21
ii+1
)()(
2
nfnT

91. 91
Bubble Sort
2154 6
12345
j
21
ii+1
21

92. 92
Bubble Sort
1254 6
12345
j
2
i=j

93. 93
Bubble Sort
1254 6
12345
j

94. 94
Bubble Sort
1254 6
12345
j

95. 95
Bubble Sort
INPUT : A[1..n], array of integers
OUTPUT: Rearrangement of A such that A[1]≤A[2] ≤… ≤A[n]
BUBBLE-SORT (A)
// Sort by bubbling the smallest element to current position.
1. j = n
2. while j ≥ 2
// Bubble up the smallest element to its correct position
3. for i = 1 to j - 1
4. if A[i] > A[i + 1]
5. temp = A[i]
6. A[i] = A[i + 1]
7. A[i + 1] = temp
8. j = j - 1
1254 6
12345
j

96. 96
Bubble Sort
INPUT : A[1..n], array of integers
OUTPUT: Rearrangement of A such that A[1]≤A[2] ≤… ≤A[n]
BUBBLE-SORT (A)
/* Sort by bubbling the smallest
element to current position. */
1. j = n
2. while j ≥ 2
/* Bubble up the smallest
element to its correct position */
3. for i = 1 to j - 1
4.if A[i] > A[i + 1]
5. temp = A[i]
6. A[i] = A[i + 1]
7. A[i + 1] = temp
8.j = j - 1

97. 97
Bubble Sort
INPUT : A[1..n], array of integers
OUTPUT: Rearrangement of A such that A[1]≤A[2] ≤… ≤A[n]
BUBBLE-SORT (A)
/* Sort by bubbling the smallest
element to current position. */
1. j = n
2. while j ≥ 2
/* Bubble up the smallest
element to its correct position */
3. for i = 1 to j - 1
4.if A[i] > A[i + 1]
5. temp = A[i]
6. A[i] = A[i + 1]
7. A[i + 1] = temp
8.j = j - 1
•Best case:
•Worst case:
•Average case:
2
1 2 3
( )T n bn b n b  
2
1 2 3
( )T n an a n a  
2
1 2 3
( )T n An An A  
a
1
, a
2
and a
2
are constants
b
1
, b
2
and b
3
are constants
A
1
, A
2 and A
3
are constants

98. Readings
•Read Chapter 1 and 2 in Corman book
•Read Chapter 6 in Tenenbaum book
98