chapter12r.ppt lecture-10 (1).ppt lecture-10 (1).ppt

lecture-10 (1).ppt

1. Data Structures: A Pseudocode Approach with C, Second Edition 1
Chapter 12Chapter 12
Objectives
Upon completion you will be able to:
• Understand the basic concepts of internal and external sorts
• Discuss the relative efficiency of different sorts
• Recognize and discuss selection, insertion and exchange sorts
• Discuss the design and operation of external sorts
• Recognize natural, balanced, and polyphase merge sorts
SortingSorting

2. Data Structures: A Pseudocode Approach with C, Second Edition 2
12-1 Sort Concepts
Sorts arrange data according to their value. In this chapter, we Sorts arrange data according to their value. In this chapter, we
discuss both internal and external sorts. We divide internal sorts discuss both internal and external sorts. We divide internal sorts
into three categories-insertion, selection, and exchange-and into three categories-insertion, selection, and exchange-and
discuss two different sorts in each classification. At the end of discuss two different sorts in each classification. At the end of
the chapter we discuss natural, balanced, and polyphase external the chapter we discuss natural, balanced, and polyphase external
sorts. We begin with a discussion of several sort concepts in sorts. We begin with a discussion of several sort concepts in
Section 12.1.Section 12.1.
• Sort Order
• Sort Stability
• Sort Efficiency
• Passes
• Sorts and ADTs

3. Data Structures: A Pseudocode Approach with C, Second Edition 3
Sort concepts

Sort

The process through which data are
arranged according to their values.

Sorting is one of the most common
data-processing applications.

4. Data Structures: A Pseudocode Approach with C, Second Edition 4
Sort classifications

5. Data Structures: A Pseudocode Approach with C, Second Edition 5
Sort order

The sort order identifies the sequence
of sorted data, ascending or
descending.

6. Data Structures: A Pseudocode Approach with C, Second Edition 6
Sort order

7. Data Structures: A Pseudocode Approach with C, Second Edition 7
Sort stability

Sort stability is an attribute of a sort,
indicating that data with equal keys
maintain their relative input order in the
output.

8. Data Structures: A Pseudocode Approach with C, Second Edition 8
Sort efficiency

Sort efficiency is a
measure of the
relative efficiency of
a sort.

Quick sort (best)

)log(nnO

9. Data Structures: A Pseudocode Approach with C, Second Edition 9
Passes

During the sorting process, the data
traversed many times.

Each traversal of the data is referred as
a sort pass.

10. Data Structures: A Pseudocode Approach with C, Second Edition 10
12-2 Selection Sorts
In each pass of the selection sort, the smallest element is selected In each pass of the selection sort, the smallest element is selected
from the unsorted sublist and exchanged with the element at the from the unsorted sublist and exchanged with the element at the
beginning of the unsorted list. We discuss two classic selection beginning of the unsorted list. We discuss two classic selection
sorts, straight selection and heap sort.sorts, straight selection and heap sort.
• Straight Selection Sort
• Heap Sort
• Selection Sort Efficiency
• Selection Sort Implementation

11. Data Structures: A Pseudocode Approach with C, Second Edition 11
Selection sorts

Selection sorts are among the most intuitive
of all sorts.

Straight Selection Sort

Heap sort

In each pass of the selection sort, the smallest
element is selected from the unsorted sublist
and exchanged with the element at the
beginning of the unsorted list.

12. Data Structures: A Pseudocode Approach with C, Second Edition 12
Straight selection sort

13. Data Structures: A Pseudocode Approach with C, Second Edition 13
Selection sort

14. Data Structures: A Pseudocode Approach with C, Second Edition 14
Selection sort algorithm

15. Data Structures: A Pseudocode Approach with C, Second Edition 15
Selection sort algorithm

16. Data Structures: A Pseudocode Approach with C, Second Edition 16
Heap sort

The heap sort is an improved version of
the selection sort in which the largest
element (the root) is selected and
exchanged with the last element in the
unsorted list.

17. Data Structures: A Pseudocode Approach with C, Second Edition 17

18. Data Structures: A Pseudocode Approach with C, Second Edition 18
Heap sort exchange process

19. Data Structures: A Pseudocode Approach with C, Second Edition 19
Heap sort process

20. Data Structures: A Pseudocode Approach with C, Second Edition 20

21. Data Structures: A Pseudocode Approach with C, Second Edition 21
Selection sort efficiency

The straight selection sort efficiency is
O(n
2
).

The heap sort efficiency is O(n log n)

22. Data Structures: A Pseudocode Approach with C, Second Edition 22
Selection sort
implementatio
n

23. Data Structures: A Pseudocode Approach with C, Second Edition 23

24. Data Structures: A Pseudocode Approach with C, Second Edition 24
Heap sort
implementatio
n

25. Data Structures: A Pseudocode Approach with C, Second Edition 25

26. Data Structures: A Pseudocode Approach with C, Second Edition 26

27. Data Structures: A Pseudocode Approach with C, Second Edition 27

28. Data Structures: A Pseudocode Approach with C, Second Edition 28

29. Data Structures: A Pseudocode Approach with C, Second Edition 29

30. Data Structures: A Pseudocode Approach with C, Second Edition 30
12-3 Insertion Sorts
In each pass of an insertion sort, one or more pieces of data are In each pass of an insertion sort, one or more pieces of data are
inserted into their correct location in an ordered list. inserted into their correct location in an ordered list.
In this section we study two insertion sorts: the straight insertion In this section we study two insertion sorts: the straight insertion
sort and the shell sort.sort and the shell sort.
• Straight Insertion Sort
• Shell Sort
• Insertion Sort Efficiency
• Insertion Sort Implementation

31. Data Structures: A Pseudocode Approach with C, Second Edition 31
Straight insertion sort

The list at any moment is divided into
sorted and unsorted sublists.

In each pass the first element of the
unsorted sublist is inserted into the
sorted sublist.

32. Data Structures: A Pseudocode Approach with C, Second Edition 32
Straight insertion sort

33. Data Structures: A Pseudocode Approach with C, Second Edition 33
Straight
insertion sort
example

34. Data Structures: A Pseudocode Approach with C, Second Edition 34

35. Data Structures: A Pseudocode Approach with C, Second Edition 35
Shell sort

The shell sort is an improved version of
the straight insertion sort in which
diminishing partitions are used to
sorted the data.

36. Data Structures: A Pseudocode Approach with C, Second Edition 36
Segmented array

N = 10

Increment (K) = 3

37. Data Structures: A Pseudocode Approach with C, Second Edition 37
Diminishing increments in shell
sort

38. Data Structures: A Pseudocode Approach with C, Second Edition 38
Diminishing increments in shell
sort

39. Data Structures: A Pseudocode Approach with C, Second Edition 39
Diminishing increments in shell
sort

40. Data Structures: A Pseudocode Approach with C, Second Edition 40
Diminishing increments in shell
sort

41. Data Structures: A Pseudocode Approach with C, Second Edition 41

42. Data Structures: A Pseudocode Approach with C, Second Edition 42

43. Data Structures: A Pseudocode Approach with C, Second Edition 43
Straight insertion sort
efficiency

O(N
2
)

44. Data Structures: A Pseudocode Approach with C, Second Edition 44
Shell sort efficiency

O(N
1.25
)

45. Data Structures: A Pseudocode Approach with C, Second Edition 45
Comparison of insertion and
selection sorts

46. Data Structures: A Pseudocode Approach with C, Second Edition 46

47. Data Structures: A Pseudocode Approach with C, Second Edition 47

48. Data Structures: A Pseudocode Approach with C, Second Edition 48

49. Data Structures: A Pseudocode Approach with C, Second Edition 49
12-4 Exchange Sorts
• Bubble Sort
• Quick Sort
• Exchange Sort Efficiency
• Sort Summary
• Exchange Sort Implementation

50. Data Structures: A Pseudocode Approach with C, Second Edition 50
Exchanged sort

In exchange sorts we exchange
elements that are out of order until the
entire list is sorted.

51. Data Structures: A Pseudocode Approach with C, Second Edition 51
Bubble sort

52. Data Structures: A Pseudocode Approach with C, Second Edition 52
Bubble sort concept

53. Data Structures: A Pseudocode Approach with C, Second Edition 53
Bubble sort
example

54. Data Structures: A Pseudocode Approach with C, Second Edition 54

55. Data Structures: A Pseudocode Approach with C, Second Edition 55
Quick sort

Quick sort is an exchange sort in which
a pivot key is placed in its correct
position in the array while rearranging
other elements widely dispersed across
the list.

56. Data Structures: A Pseudocode Approach with C, Second Edition 56
Quick sort
Each iteration of the quick sort

selects an element, known as pivot, and

Divides the list into three groups

A partition of elements < the pivot’s key

The pivot element that is placed in its ultimately
correct location in the list

A partition of elements the pivot’s key
≧
The sorting then continues by quick
sorting the left partition followed by
quick sorting the right partition.

57. Data Structures: A Pseudocode Approach with C, Second Edition 57
Quick sort partitions

58. Data Structures: A Pseudocode Approach with C, Second Edition 58
Quick sort algorithm

Straight insertion module

Determine median of three

Quick sort algorithm

59. Data Structures: A Pseudocode Approach with C, Second Edition 59

60. Data Structures: A Pseudocode Approach with C, Second Edition 60

61. Data Structures: A Pseudocode Approach with C, Second Edition 61
Quick
sort
pivot

62. Data Structures: A Pseudocode Approach with C, Second Edition 62
Quick sort operation

63. Data Structures: A Pseudocode Approach with C, Second Edition 63

64. Data Structures: A Pseudocode Approach with C, Second Edition 64

65. Data Structures: A Pseudocode Approach with C, Second Edition 65
Exchange sort efficiency

The bubble sort efficiency is O(n
2
).

The quick sort efficiency is O(n log n).

66. Data Structures: A Pseudocode Approach with C, Second Edition 66
Sort comparisons

67. Data Structures: A Pseudocode Approach with C, Second Edition 67

68. Data Structures: A Pseudocode Approach with C, Second Edition 68

69. Data Structures: A Pseudocode Approach with C, Second Edition 69

70. Data Structures: A Pseudocode Approach with C, Second Edition 70

71. Data Structures: A Pseudocode Approach with C, Second Edition 71

72. Data Structures: A Pseudocode Approach with C, Second Edition 72

73. Data Structures: A Pseudocode Approach with C, Second Edition 73

74. Data Structures: A Pseudocode Approach with C, Second Edition 74

75. Data Structures: A Pseudocode Approach with C, Second Edition 75

76. Data Structures: A Pseudocode Approach with C, Second Edition 76
12-5 External Sorts
In external sorting portions of the data may be stored in In external sorting portions of the data may be stored in
secondary memory during the sorting process. Included in this secondary memory during the sorting process. Included in this
section is a discussion of file merging and three external sort section is a discussion of file merging and three external sort
approaches-natural, balanced, and polyphase.approaches-natural, balanced, and polyphase.
• Merging Ordered Files
• Merging Unordered Files
• The Sorting Process
• Sort Phase Revisited

77. Data Structures: A Pseudocode Approach with C, Second Edition 77

78. Data Structures: A Pseudocode Approach with C, Second Edition 78

79. Data Structures: A Pseudocode Approach with C, Second Edition 79

80. Data Structures: A Pseudocode Approach with C, Second Edition 80

81. Data Structures: A Pseudocode Approach with C, Second Edition 81

82. Data Structures: A Pseudocode Approach with C, Second Edition 82

83. Data Structures: A Pseudocode Approach with C, Second Edition 83

84. Data Structures: A Pseudocode Approach with C, Second Edition 84

85. Data Structures: A Pseudocode Approach with C, Second Edition 85
12-6 Quick Sort Efficiency
We revisit the general approach to analyzing algorithm We revisit the general approach to analyzing algorithm
efficiency with an in-depth discussion of the quick sort's efficiency with an in-depth discussion of the quick sort's
efficiency.efficiency.

86. Data Structures: A Pseudocode Approach with C, Second Edition 86

87. Data Structures: A Pseudocode Approach with C, Second Edition 87

88. Data Structures: A Pseudocode Approach with C, Second Edition 88

89. Data Structures: A Pseudocode Approach with C, Second Edition 89