Sorting of arrays, types in c++ .IST .ppt

Sorting of arrays

1. Programming Language
INSTRUCTOR: Dr. Benish Amin

2. Sorting
Sorting takes an unordered collection and makes it an ordered
one.
2
512354277 101
1 2 3 4 5 6
5 12 35 42 77 101
1 2 3 4 5 6

3. What is Bubble Sort
Idea:
•Repeatedly pass through the array
•Swaps adjacent elements that are out of order
Easier to implement, but slower…
1329648
j
n1 2 3

4. "Bubbling Up" the Largest Element
Traverse a collection of elements
•Move from the front to the end
•“Bubble” the largest valueto the end using pair-wise comparisons and
swapping
4
512354277 101
1 2 3 4 5 6

5. "Bubbling Up" the Largest Element
Traverse a collection of elements
•Move from the front to the end
•“Bubble” the largest value to the end using pair-wise comparisons and
swapping
5
512354277 101
1 2 3 4 5 6
Swap
42 77

6. "Bubbling Up" the Largest Element
Traverse a collection of elements
•Move from the front to the end
•“Bubble” the largest value to the end using pair-wise comparisons and
swapping
6
512357742 101
1 2 3 4 5 6
Swap
35 77

7. "Bubbling Up" the Largest Element
Traverse a collection of elements
•Move from the front to the end
•“Bubble” the largest value to the end using pair-wise comparisons and swapping
7
512773542 101
1 2 3 4 5 6
Swap
12 77

8. "Bubbling Up" the Largest Element
Traverse a collection of elements
•Move from the front to the end
•“Bubble” the largest value to the end using pair-wise comparisons and
swapping
8
577123542 101
1 2 3 4 5 6
No need to swap

9. "Bubbling Up" the Largest Element
Traverse a collection of elements
•Move from the front to the end
•“Bubble” the largest value to the end using pair-wise comparisons and swapping
9
577123542 101
1 2 3 4 5 6
Swap
5 101

10. "Bubbling Up" the Largest Element
Traverse a collection of elements
•Move from the front to the end
•“Bubble” the largest value to the end using pair-wise comparisons and swapping
10
77123542 5
1 2 3 4 5 6
101
Largest value correctly placed

11. Items of Interest
Notice that only the largest value is correctly placed
All other values are still out of order
So, we need to repeat this process
11
77123542 5
1 2 3 4 5 6
101
Largest value correctly placed

12. Repeat “Bubble Up” How Many Times?
If we have N elements…
And if each time we bubble an element, we place it in its correct
location…
Then we repeat the “bubble up” process N –1 times.
This guarantees we’ll correctly place all N elements.
12

13. “Bubbling” All the Elements
13
77123542 5
1 2 3 4 5 6
101
5421235 77 101
4253512 77 101
4235512 77 101
4235125 77 101
N
-
1
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6

14. Reducing the Number of Comparisons
14
12354277 101
1 2 3 4 5 6
5
77123542 5
1 2 3 4 5 6
101
5421235 77
1 2 3 4 5 6
101
4253512 77
1 2 3 4 5 6
101
4235512 77
1 2 3 4 5 6
101

15. Reducing the Number of Comparisons
On the N
th
“bubble up”, we only need to do MAX -N comparisons.
For example:
•This is the 4
th
“bubble up”
•MAX is 6
•Thus, we have 2 comparisonsto do
15
4253512 77
1 2 3 4 5 6
101

16. 16
#include <iostream>
usingnamespace std;
// perform bubble sort
voidbubbleSort(intarray[], intsize) {
// loop to access each array element
for(intstep = 0; step < size; ++step) {
// loop to compare array elements
for (inti= 0; i< size -step; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i+ 1]) {
// swapping elements if elements
// are not in the intended order
inttemp = array[i];
array[i] = array[i+ 1];
array[i+ 1] = temp;
}
}
}
}

17. 17
// print array
voidprintArray(intarray[], intsize) {
for (inti= 0; i< size; ++i) {
cout<< " " << array[i];
}
cout<< "\n";
}
intmain() {
intdata[] = {-2, 45, 0, 11, -9};
// find array's length
intsize = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout<< "Sorted Array in Ascending Order: \n";
printArray(data, size);
return0;
}

18. Already Sorted Array?
What if the array was already sorted?
What if only a few elements were out of place and after a couple
of “bubble ups,” the collection was sorted?
We want to be able to detect this and “stop early”!
18
4235125 77
1 2 3 4 5 6
101

19. An Animated Example
19
674523 14 6 3398 42
1 2 3 4 5 6 7 8
to_do
index
7
N 8 did_swap true

20. An Animated Example
20
674523 14 6 3398 42
to_do
index
7
1
N 8 did_swap false
1 2 3 4 5 6 7 8

21. An Animated Example
21
674523 14 6 3398 42
to_do
index
7
1
N 8
Swap
did_swap false
1 2 3 4 5 6 7 8

22. An Animated Example
22
674598 14 6 3323 42
to_do
index
7
1
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

23. An Animated Example
23
674598 14 6 3323 42
to_do
index
7
2
N 8 did_swap true
1 2 3 4 5 6 7 8

24. An Animated Example
24
674598 14 6 3323 42
to_do
index
7
2
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

25. An Animated Example
25
679845 14 6 3323 42
to_do
index
7
2
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

26. An Animated Example
26
679845 14 6 3323 42
to_do
index
7
3
N 8 did_swap true
1 2 3 4 5 6 7 8

27. An Animated Example
27
679845 14 6 3323 42
to_do
index
7
3
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

28. An Animated Example
28
671445 98 6 3323 42
to_do
index
7
3
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

29. An Animated Example
29
671445 98 6 3323 42
to_do
index
7
4
N 8 did_swap true
1 2 3 4 5 6 7 8

30. An Animated Example
30
671445 98 6 3323 42
to_do
index
7
4
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

31. An Animated Example
31
671445 6 98 3323 42
to_do
index
7
4
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

32. An Animated Example
32
671445 6 98 3323 42
to_do
index
7
5
N 8 did_swap true
1 2 3 4 5 6 7 8

33. An Animated Example
33
671445 6 98 3323 42
to_do
index
7
5
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

34. An Animated Example
34
981445 6 67 3323 42
to_do
index
7
5
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

35. An Animated Example
35
981445 6 67 3323 42
to_do
index
7
6
N 8 did_swap true
1 2 3 4 5 6 7 8

36. An Animated Example
36
981445 6 67 3323 42
to_do
index
7
6
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

37. An Animated Example
37
331445 6 67 9823 42
to_do
index
7
6
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

38. An Animated Example
38
331445 6 67 9823 42
to_do
index
7
7
N 8 did_swap true
1 2 3 4 5 6 7 8

39. An Animated Example
39
331445 6 67 9823 42
to_do
index
7
7
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

40. An Animated Example
40
331445 6 67 4223 98
to_do
index
7
7
N 8
Swap
did_swap true
1 2 3 4 5 6 7 8

41. After First Pass of Outer Loop
41
331445 6 67 4223 98
to_do
index
7
8
N 8
Finished first “Bubble Up”
did_swap true
1 2 3 4 5 6 7 8

42. The Second “Bubble Up”
42
331445 6 67 4223 98
to_do
index
6
1
N 8 did_swap false
1 2 3 4 5 6 7 8

43. The Second “Bubble Up”
43
331445 6 67 4223 98
to_do
index
6
1
N 8 did_swap false
No Swap
1 2 3 4 5 6 7 8

44. The Second “Bubble Up”
44
331445 6 67 4223 98
to_do
index
6
2
N 8 did_swap false
1 2 3 4 5 6 7 8

45. The Second “Bubble Up”
45
331445 6 67 4223 98
to_do
index
6
2
N 8 did_swap false
Swap
1 2 3 4 5 6 7 8

46. The Second “Bubble Up”
46
334514 6 67 4223 98
to_do
index
6
2
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

47. The Second “Bubble Up”
47
334514 6 67 4223 98
to_do
index
6
3
N 8 did_swap true
1 2 3 4 5 6 7 8

48. The Second “Bubble Up”
48
334514 6 67 4223 98
to_do
index
6
3
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

49. The Second “Bubble Up”
49
33614 4567 4223 98
to_do
index
6
3
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

50. The Second “Bubble Up”
50
33614 4567 4223 98
to_do
index
6
4
N 8 did_swap true
1 2 3 4 5 6 7 8

51. The Second “Bubble Up”
51
33614 4567 4223 98
to_do
index
6
4
N 8 did_swap true
No Swap
1 2 3 4 5 6 7 8

52. The Second “Bubble Up”
52
33614 4567 4223 98
to_do
index
6
5
N 8 did_swap true
1 2 3 4 5 6 7 8

53. The Second “Bubble Up”
53
33614 4567 4223 98
to_do
index
6
5
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

54. The Second “Bubble Up”
54
67614 4533 4223 98
to_do
index
6
5
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

55. The Second “Bubble Up”
55
67614 4533 4223 98
to_do
index
6
6
N 8 did_swap true
1 2 3 4 5 6 7 8

56. The Second “Bubble Up”
56
67614 4533 4223 98
to_do
index
6
6
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

57. The Second “Bubble Up”
57
42614 4533 6723 98
to_do
index
6
6
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

58. After Second Pass of Outer Loop
58
42614 4533 6723 98
to_do
index
6
7
N 8 did_swap true
Finished second “Bubble Up”
1 2 3 4 5 6 7 8

59. The Third “Bubble Up”
59
42614 4533 6723 98
to_do
index
5
1
N 8 did_swap false
1 2 3 4 5 6 7 8

60. The Third “Bubble Up”
60
42614 4533 6723 98
to_do
index
5
1
N 8 did_swap false
Swap
1 2 3 4 5 6 7 8

61. The Third “Bubble Up”
61
42623 4533 6714 98
to_do
index
5
1
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

62. The Third “Bubble Up”
62
42623 4533 6714 98
to_do
index
5
2
N 8 did_swap true
1 2 3 4 5 6 7 8

63. The Third “Bubble Up”
63
42623 4533 6714 98
to_do
index
5
2
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

64. The Third “Bubble Up”
64
42236 4533 6714 98
to_do
index
5
2
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

65. The Third “Bubble Up”
65
42236 4533 6714 98
to_do
index
5
3
N 8 did_swap true
1 2 3 4 5 6 7 8

66. The Third “Bubble Up”
66
42236 4533 6714 98
to_do
index
5
3
N 8 did_swap true
No Swap
1 2 3 4 5 6 7 8

67. The Third “Bubble Up”
67
42236 4533 6714 98
to_do
index
5
4
N 8 did_swap true
1 2 3 4 5 6 7 8

68. The Third “Bubble Up”
68
42236 4533 6714 98
to_do
index
5
4
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

69. The Third “Bubble Up”
69
42236 3345 6714 98
to_do
index
5
4
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

70. The Third “Bubble Up”
70
42236 3345 6714 98
to_do
index
5
5
N 8 did_swap true
1 2 3 4 5 6 7 8

71. The Third “Bubble Up”
71
42236 3345 6714 98
to_do
index
5
5
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

72. The Third “Bubble Up”
72
45236 3342 6714 98
to_do
index
5
5
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

73. The Third “Bubble Up”
73
45236 3342 6714 98
to_do
index
5
6
N 8 did_swap true
Finished third “Bubble Up”
1 2 3 4 5 6 7 8

74. The Fourth “Bubble Up”
74
45236 3342 6714 98
to_do
index
4
1
N 8 did_swap false
1 2 3 4 5 6 7 8

75. The Fourth “Bubble Up”
75
45236 3342 6714 98
to_do
index
4
1
N 8 did_swap false
Swap
1 2 3 4 5 6 7 8

76. The Fourth “Bubble Up”
76
452314 3342 676 98
to_do
index
4
1
N 8 did_swap true
Swap
1 2 3 4 5 6 7 8

77. The Fourth “Bubble Up”
77
452314 3342 676 98
to_do
index
4
2
N 8 did_swap true
1 2 3 4 5 6 7 8

78. The Fourth “Bubble Up”
78
452314 3342 676 98
to_do
index
4
2
N 8 did_swap true
No Swap
1 2 3 4 5 6 7 8

79. The Fourth “Bubble Up”
79
452314 3342 676 98
to_do
index
4
3
N 8 did_swap true
1 2 3 4 5 6 7 8

80. The Fourth “Bubble Up”
80
452314 3342 676 98
to_do
index
4
3
N 8 did_swap true
No Swap
1 2 3 4 5 6 7 8

81. The Fourth “Bubble Up”
81
452314 3342 676 98
to_do
index
4
4
N 8 did_swap true
1 2 3 4 5 6 7 8

82. The Fourth “Bubble Up”
82
452314 3342 676 98
to_do
index
4
4
N 8 did_swap true
No Swap
1 2 3 4 5 6 7 8

83. The Fourth “Bubble Up”
83
452314 3342 676 98
to_do
index
4
5
N 8 did_swap true
Finished fourth “Bubble Up”
1 2 3 4 5 6 7 8

84. The Fourth “Bubble Up”
84
452314 3342 676 98
to_do
index
3
1
N 8 did_swap false
1 2 3 4 5 6 7 8

85. The Fifth “Bubble Up”
85
452314 3342 676 98
to_do
index
3
1
N 8 did_swap false
No Swap
1 2 3 4 5 6 7 8

86. The Fifth “Bubble Up”
86
452314 3342 676 98
to_do
index
3
2
N 8 did_swap false
1 2 3 4 5 6 7 8

87. The Fifth “Bubble Up”
87
452314 3342 676 98
to_do
index
3
2
N 8 did_swap false
No Swap
1 2 3 4 5 6 7 8

88. The Fifth “Bubble Up”
88
452314 3342 676 98
to_do
index
3
3
N 8 did_swap false
1 2 3 4 5 6 7 8

89. The Fifth “Bubble Up”
89
452314 3342 676 98
to_do
index
3
3
N 8 did_swap false
No Swap
1 2 3 4 5 6 7 8

90. After Fifth Pass of Outer Loop
90
452314 3342 676 98
to_do
index
3
4
N 8 did_swap false
Finished fifth “Bubble Up”
1 2 3 4 5 6 7 8

91. Finished “Early”
91
452314 3342 676 98
to_do
index
3
4
N 8 did_swap false
We didn’t do any swapping, so all of the other
elements must be correctly placed.
We can “skip” the last two passes of the outer loop.
1 2 3 4 5 6 7 8

92. Using a Boolean “Flag”
We can use a boolean variable to determine if any swapping occurred
during the “bubble up.”
If no swapping occurred, then we know that the array is already
sorted!
This boolean “flag” needs to be reset after each “bubble up.”
92

93. 93
#include <iostream>
usingnamespace std;
// perform bubble sort
voidbubbleSort(intarray[], intsize) {
// check if swapping occurs
intflag= 0;
// loop to access each array element
for(intstep = 0; step < size; ++step) {
// loop to compare array elements
for (inti= 0; i< size -step; ++i) {
// compare two adjacent elements
// change > to < to sort in descending order
if (array[i] > array[i+ 1]) {
// swapping elements if elements
// are not in the intended order
inttemp = array[i];
array[i] = array[i+ 1];
array[i+ 1] = temp;
flag= 1;
}
}
// no swapping means the array is already sorted
// so no need of further comparison
if(flag== 0)
break;
}
}

94. 94
// print array
voidprintArray(intarray[], intsize) {
for (inti= 0; i< size; ++i) {
cout<< " " << array[i];
}
cout<< "\n";
}
intmain() {
intdata[] = {-2, 45, 0, 11, -9};
// find array's length
intsize = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
cout<< "Sorted Array in Ascending Order: \n";
printArray(data, size);
return0;
}

95. Selection Sort
Idea:
•Find the smallest element in the array
•Exchange it with the element in the first position
•Find the second smallest element and exchange it with the element in the
second position
•Continue until the array is sorted
Disadvantage:
•Running time depends only slightly on the amount of order in the file
95

96. Example
96
1329648
8329641
8349621
8649321
8964321
8694321
9864321
9864321

97. Selection Sort
Alg.:SELECTION-SORT(A)
n ← length[A]
for j ← 1 to n -1
do smallest ← j
for i ← j + 1 to n
do if A[i] < A[smallest]
then smallest ← i
exchange A[j] ↔ A[smallest]
97
1329648

98. Assignment # 1
•Perform selection sort on user defined data and implement the code
in C++.
•Deadline: 4
th
March, 2024
98