Data Structures and Algorithms

Manish Aryal
Sorting

 One of the most important concepts and

common applications in computing.
23 78 45 8 32 56

8 23 32 45 56 78

2
General Sort Concepts

 Internal sort: all data are held in primary memory

during the sorting process.

 External sort: primary memory for data currently

being sorted and secondary storage for data that
do not fit in primary memory.

3
General Sort Concepts
Sorts

Internal External
• Natural
• Balanced
Insertion Selection Exchange • Polyphase

• Straight Insertion • Straight Selection • Bubble

• Shell • Heap • Quick

4
General Sort Concepts

 Sort stability: data with equal keys maintain their

relative input order in the output.
78 8 45 8 32 56

8 8 32 45 56 78

5
General Sort Concepts
 Sort efficiency: a measure of the relative
efficiency of a sort = number of comparisons + number
of moves
 Sort pass: each traversal of the data being
sorted

6
Insertion Sorts

 In each pass, one or more pieces of data are

inserted into their correct location in an ordered
list.

7
Straight Insertion Sort
 The list is divided into two parts: sorted and
unsorted.

 In each pass, the first element of the unsorted

sublist is inserted into the sorted sublist.

unsorted

8
Straight Insertion Sort

23 78 45 8 32 56

9
Straight Insertion Sort

23 78 45 8 32 56

23 78 45 8 32 56

10
Straight Insertion Sort
23 78 45 8 32 56

23 78 45 8 32 56

23 45 78 8 32 56

11
 Straight Insertion Sort

23 78 45 8 32 56

23 78 45 8 32 56

23 45 78 8 32 56

8 23 45 78 32 56

12
 Straight Insertion Sort

23 78 45 8 32 56

23 78 45 8 32 56

23 45 78 8 32 56

8 23 45 78 32 56

8 23 32 45 78 56

13
Straight Insertion Sort

23 78 45 8 32 56

23 78 45 8 32 56

23 45 78 8 32 56

8 23 45 78 32 56

8 23 32 45 78 56

8 23 32 45 56 78

14
Straight Insertion Sort
Algorithm insertionSort (ref list <array>, val last <index>)
Sorts list[1..last] using straight insertion sort
Pre list contains at least one element
last is index to last element in the list
Post list has been rearranged
1 current = 2
2 loop (current <= last)
1 hold = list[current]
2 walker = current - 1
3 loop (walker >= 1 AND hold.key < list[walker].key)
1 list[walker + 1] = list[walker]
2 walker = walker - 1
4 list[walker + 1] = hold
5 current = current + 1
3 return
End insertionSort
15
Shell Sort

 Named after its creator Donald L. Shell (1959).

 Given a list of N elements, the list is divided into K

segments (K is called the increment).

 Each segment contains N/K or more elements.

 Segments are dispersed throughout the list.

16
Shell Sort

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

K=3

[1] [1 + K] [1 + 2*K] [1 + 3*K]

Segment 1

[2] [2 + K] [2 + 2*K]

Segment 2

[3] [3 + K] [3 + 2*K]

Segment 3

17
Shell Sort

K=3 25 57 48 37 12 92 86 33

[1] [1 + K] [1 + 2*K]

Segment 1 25 37 86
[2] [2 + K] [2 + 2*K]

Segment 2 57 12 33

[3] [3 + K] [3 + 2*K]
Segment 3 48 92

18
Shell Sort

 For the value of K in each iteration, sort the K

segments.

 After each iteration, K is reduced until it is 1 in the

final iteration.

19
Shell Sort
Algorithm shellSort (ref list <array>, val last <index>)
Sorts list[1..last] using shell sort
Pre list must contain at least one element
last is index to last element in the list
Post list has been rearranged
1 K = last/2
2 loop (K not 0)
1 seg = 1
2 loop (seg <= K)
1 sortSegment (seg)
2 seg = seg + 1
3 K = K/2
3 return
End shellSort

20
 Shell Sort
Algorithm shellSort (ref list <array>, val last <index>)
Sorts list[1..last] using shell sort
Pre list must contain at least one element
last is index to last element in the list
Post list has been rearranged
1 K = last/2
2 loop (K not 0)
1 seg = 1
2 loop (seg <= K)
1 current = seg + K
2 loop (current <= last)
1 hold = list[current]
2 walker = current - K
3 loop (walker >= 1 AND hold.key < list[walker].key)
1 list[walker + K] = list [walker]
2 walker = walker - K
4 list[walker + K] = hold
5 current = current + K
3 seg = seg + 1
3 K = K/2
3 return
End shellSort 21
Insertion Sort Efficiency

 Straight insertion sort:

f(n) = n(n + 1)/2 = O(n2)

22
Insertion Sort Efficiency

 Shell sort:

O(n1.25) Empirical study

23
General Sort Concepts
Sorts

Internal External
• Natural
• Balanced
Insertion Selection Exchange • Polyphase

• Straight Insertion • Straight Selection • Bubble

• Shell • Heap • Quick

24
Selection Sorts

 In each pass, the smallest/largest item is selected

and placed in a sorted list.

25
Straight Selection Sort

 The list is divided into two parts: sorted and

unsorted.

 In each pass, in the unsorted sublist, the smallest

element is selected and exchanged with the first
element.

unsorted

26
Straight Selection Sort

23 78 45 8 32 56

27
Straight Selection Sort

23 78 45 8 32 56

8 78 45 23 32 56

28
 Straight Selection Sort

23 78 45 8 32 56

8 78 45 23 32 56

8 23 45 78 32 56

29
 Straight Selection Sort

23 78 45 8 32 56

8 78 45 23 32 56

8 23 45 78 32 56

8 23 32 78 45 56

30
 Straight Selection Sort

23 78 45 8 32 56

8 78 45 23 32 56

8 23 45 78 32 56

8 23 32 78 45 56

8 23 32 45 78 56

31
Straight Selection Sort

23 78 45 8 32 56

8 78 45 23 32 56

8 23 45 78 32 56

8 23 32 78 45 56

8 23 32 45 78 56

8 23 32 45 56 78

32
Straight Selection Sort
Algorithm selectionSort (ref list <array>, val last <index>)
Sorts list[1..last] using straight selection sort
Pre list contains at least one element
last is index to last element in the list
Post list has been rearranged
1 current = 1
2 loop (current < last)
1 smallest = current
2 walker = current + 1
3 loop (walker <= last)
1 if (list[walker] < list[smallest])
1 smallest = walker
2 walker = walker + 1
4 exchange (list, current, smallest)
5 current = current + 1
3 return
End selectionSort

33
 Heap Sort
 A heap is a binary tree structure such that:
 The tree is complete or nearly complete
 The key value of each node is >= the key value of each of
its descendents (max-heap)
 The unsorted sublist is organized into a heap.
 In each pass, in the unsorted sublist, the largest
element is selected and exchanged with the last
element.
Then the heap is reheaped.
heap
34
Heap Sort

23 78 45 8 32 56

23

78
[0] 45

[1] [2]
8 32 56

[3] [4] [5]

35
Heap Sort

23 78 45 8 32 56 78 32 56 8 23 45

build heap
23 78

78
[0] 45 32
[0] 56

[1] [2] [1] [2]

8 32 56 8 23 45

[3] [4] [5] [3] [4] [5]

36
Heap Sort

78 32 56 8 23 45 45 32 56 8 23 78

78 45

[0] 32
[0] 56
32 56

[1] [2] [1] [2]

8 23 45 8 23 78

[3] [4] [5] [3] [4] [5]

37
Heap Sort
Algorithm heapSort (ref heap <array>, val last <index>)
Sorts list[0..last] using heap sort
Pre array is filled
last is index to last element in the list
Postarray has been sorted
Creat a heap
1 walker = 1
2 loop (walker <= last)
1 reheapUp (heap, walker)
2 walker = walker + 1
Sort the list
3 sorted = last
4 loop (sorted > 0)
1 exchange (heap, 0, sorted)
2 sorted = sorted - 1
3 reheapDown (heap, 0, sorted)
5 return
End heapSort 38
Selection Sort Efficiency

 Straight selection sort:

O(n2)
 Heap sort:
O(n log2n)

39
General Sort Concepts
Sorts

Internal External
• Natural
• Balanced
Insertion Selection Exchange • Polyphase

• Straight Insertion • Straight Selection • Bubble

• Shell • Heap • Quick

40
Exchange Sorts

 In each pass, elements that are out of order are

exchanged, until the entire list is sorted.

 Exchange is extensively used.

41
Bubble Sort

 The list is divided into two parts: sorted and

unsorted.

 In each pass, the smallest element is bubbled

from the unsorted sublist and moved to the
sorted sublist.

unsorted

42
Bubble Sort

23 78 45 8 56 32

43
 Bubble Sort

23 78 45 8 56 32

23 78 45 8 32 56

23 78 45 8 32 56

23 78 8 45 32 56

23 8 78 45 32 56

8 23 78 45 32 56
44
Bubble Sort
Algorithm bubbleSort (ref list <array>, val last <index>)
Sorts list[1..last] using bubble sort
Pre list must contain at least one element
last is index to last element in the list
Post list has been rearranged
1 current = 1
2 sorted = false
3 loop (current <= last AND sorted false)
1 walker = last
2 sorted = true
3 loop (walker > current)
1 if (list[walker] < list[walker - 1])
1 sorted = false
2 exchange (list, walker, walker - 1)
2 walker = walker -1
4 current = current + 1
4 return
End bubbleSort
45
Quick Sort
 Developed by C. A. Hoare (1962).

 In each pass, a pivot/splitter element is selected

and the list is divided into three groups:
< pivot, = pivot, > pivot

Quick sort is continued

pivot
for the first and third
groups. k

<k >k

46
Quick Sort

 Pivot selection:
 C. A. Hoare (1962): the first element in the list.
 R. C. Singleton (1969): the median of the left, right and
middle elements of the list.

 Pivot location:
 Use left and right walls.
 Exchange the two elements at the left and right wall
positions if they are out of order with respect to the pivot.

47
Quick Sort

pivot

pivot

48
Quick Sort

49
Quick Sort
 D.E. Knuth suggested that when the sort
partitions becomes small, straight insertion sort
should be used to complete the sorting.
pivot
k

<k >k

50
Quick Sort
Algorithm quickSort (ref list <array>, val left <index>, val right <index>)
Sorts list[left..right] using quick sort
Pre list must contain at least one element
left and right are indices to first and last elements in the list
Post list has been rearranged
1 if (right - left > minsize)
quick sort
1 medianLeft (list, left, right)
2 pivot = list[left]
3 sortLeft = left + 1
4 sortRight = right
5 loop (sortLeft <= sortRight)
Find key on left that belongs on right
1 loop (list[sortLeft].key < pivot.key)
1 sortLeft = sortLeft + 1
Find key on right that belongs on left
1 loop (list[sortRight].key >= pivot.key)
1 sortRight = sortRight - 1

51
Quick Sort
Find key on left that belongs on right
1 loop (list[sortLeft].key < pivot.key)
1 sortLeft = sortLeft + 1
Find key on right that belongs on left
2 loop (list[sortRight].key >= pivot.key)
1 sortRight = sortRight - 1
3 if (sortLeft <= sortRight)
1 exchange (list, sortLeft, sortRight)
2 sortLeft = sortLeft + 1
3 sortRight = sortRight - 1
Prepare for next phase
6 list[left] = list[sortLeft - 1]
7 list[sortLeft - 1] = pivot
8 if (left < sortRight)
1 quickSort (list, left, sortRight - 1)
9 if (sortLeft < right)
1 quickSort (list, sortLeft, right )
2 else
1 insertionSort (list, left, right)
End quickSort
52
Quick Sort
Algorithm medianLeft (ref sortData <array>, val left <index>, val right <index>)
Finds the median of an array sortData[left..right], and places it in the location sortData[left]
Pre sortData is an array of at least three elements
left and right are the boundaries of the array
Post median value located and placed at sortData[left]
1 mid = (left + right)/2
2 if (sortData[left].key > sortData[mid].key)
1 exchange (sortData, left, mid)
3 if (sortData[left].key > sortData[right].key)
1 exchange (sortData, left, right)
4 if (sortData[mid].key > sortData[right].key)
1 exchange (sortData, mid, right)
5 exchange (sortData, left, mid)
6 return
End medianLeft

53
Exchange Sort Efficiency

 Bubble sort:
f(n) = n(n + 1)/2 = O(n2)
 Quick sort:
O(n log2n)

54
General Sort Concepts
Sorts

Internal External
• Natural
• Balanced
Insertion Selection Exchange • Polyphase

• Straight Insertion • Straight Selection • Bubble

• Shell • Heap • Quick

55
External Sorts

 Sorts that allow portions of the data to be stored

in secondary memory during the sorting process.

 Most of the work spent ordering files is not

sorting but merging.

56
Merging Ordered Files
File 3
File 1 1 File 2

1 2 2
3 3 4
5 4 6
5 8
6 10
8
10

57
Merging Ordered Files
Algorithm mergeFiles
Merges two files into one file
Pre Input files are ordered
Post Input files sequentially combined in output file
1 open files
2 read (file1 into record1)
3 read (file2 into record2)
4 loop (not end file1 OR not end file2)
1 if (record1.key <= record2.key)
1 write (file3 from record1)
2 read (file1 into record1)
3 if (end of file1)
1 record1.key = +
2 else
1 write (file3 from record2)
2 read (file2 into record2)
3 if (end of file2)
1 record2.key = +
5 close files
End mergeFiles
58
File Sorting Process

 Sort phase.

 Merge phase.

59
Sort Phase

2,300 records

Input file

Sort

records 1-500 1,001-1,500 2,001-2,300

Merge 1
501-1,000 1,501-2,000

Merge 2
60
Merge Phase

 Natural merge

 Balanced merge

 Polyphase merge

61
Polyphase Merge input

sort phase mrg

records 501-1000
records 1-500 mrg records 1,501-2000
1 2
records 1,001-1,500
merge
records 2.001-2,300

mrg
records 1-1000
3 records 1,001-2000
records 2.001-2,300
distribution
mrg mrg records 1,001-2,000
records 1-1000 1 2
records 2,001-2,300 merge

mrg records 1-2000

3 records 2,001-2,300

distribution
mrg mrg
records 1-2,000 records 2,001-2,300
1 2
merge

mrg
3 records 1-2,300 62
Polyphase Merge

input

records 1-500 sort phase records 501-1000

mrg mrg
records 1,001-1,500 2 records 1,501-2000
1
records 2.001-2,300 merge

records 1-1000 mrg mrg records 1,001-2,000

records 2,001-2,300 1 2
merge

mrg mrg
records 1-2,000 2 records 2,001-2,300
1
merge

mrg
3 records 1-2,300

63
Polyphase Merge
input

records 501-1000
records 1-500 sort phase
mrg records 1,501-2000
records 1,001-1,500 mrg
1 2
records 2.001-2,300 merge
records 1-1000
mrg records 1,001-2000
3

mrg mrg records 1-1,000

records 2,001-2,300 1 2 2,001-2,300
merge

mrg
records 1-1000
3 records 1,001-2,000

mrg mrg records 1-1,000

records 1-2,300 1 2 2,001-2,300
merge

mrg
3 records 1,001-2,000 64