Sorting

Chapter 8: Sorting • One of the most important concepts and common applications in computing. 23 78 45 8 32 56

8 23 32 45 78 56

1

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.

2

General Sort Concepts Sorts

External

Internal

Insertion

Selection

Exchange

• Insertion • Shell

• Selection • Heap

• Bubble • Quick

• Natural • Balanced • Polyphas e

3

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

4

General Sort Concepts • Sort efficiency: a measure of the relative efficiency of a sort = number of comparisons + number of moves

5

General Sort Concepts • 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.

unsorte d 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

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 )

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 2

3

current = 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 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 K=3

Segment 1 Segment 2 Segment 3

[1 ]

[2 ]

[3 ]

[1 ]

[4 ]

[5 ]

[6 ]

[1 + K]

[2 ]

[7 ]

[9 [10] ]

[1 + 2*K]

[2 + K]

[3 ]

[8 ]

[3 + K]

[1 + 3*K]

[2 + 2*K]

[3 + 2*K]

17

Shell Sort 23 78 45 8 32 56

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 )

Sorts list[1..last] using shell sort Pre Post 1 2

3

list must contain at least one element last is index to last element in the list list has been rearranged

K = last/2 loop (K not 0) 1 seg = 1 2 loop (seg <= K) 1 sortSegment (seg) 2 seg = seg + 1 3 K = K/2 return

End

shellSort

20

Shell Sort Algorithm

shellSort (ref list <array>, val last )

Sorts list[1..last] using shell sort Pre

list must contain at least one element last is index to last element in the list list has been rearranged

Post 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

Shell Sort Algorithm

shellSort (ref list <array>, val last )

Sorts list[1..last] using shell sort Pre Post 1 2

3

list must contain at least one element last is index to last element in the list list has been rearranged

incre = last/2 loop (incre not 0) 1 current = 1 + incre 2 loop (current <= last) 1 hold = list[current] 2 walker = current - incre 3 loop (walker >= 1 AND hold.key < list[walker].key) 1 list[walker + incre] = list [walker] 2 walker = walker - incre 4 list[walker + incre] = hold 5 current = current + 1 3 incre = incre/2 return

End

shellSort 22

Insertion Sort Efficiency • Straight insertion sort: f(n) = n(n + 1)/2

= O(n2)

23

Insertion Sort Efficiency • Shell sort: O(n1.25)

Empirical study

24

General Sort Concepts Sorts

External

Internal

Insertion

Selection

Exchange

• Insertion • Shell

• Selection • Heap

• Bubble • Quick

• Natural • Balanced • Polyphas e

25

Selection Sorts • In each pass, the smallest/largest item is selected and placed in a sorted list.

26

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.

unsorte d 27

Straight Selection Sort 23 78 45 8 32 56

28

Straight Selection Sort 23 78 45 8 32 56

8 78 45 23 32 56

29

Straight Selection Sort 23 78 45 8 32 56

8 78 45 23 32 56

8 23 45 78 32 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

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

32

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 33

Straight Selection Sort Algorithm

selectionSort (ref list <array>, val last )

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 2

3

current = 1 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 return

End

selectionSort 34

Heap Sort • 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 35

Heap Sort 23 78 45 8 32 56

23

[0 ]

78 8

[3 ]

[1 ]

45

32

56

[4 ]

[5 ]

[2 ]

36

Heap Sort 23 78 45 8 32 56 build heap

23

[0 ]

78 8

[3 ]

[1 ]

78 32 56 8 23 45

32

56

[4 ]

[5 ]

78

45

32

[2 ]

[1 ]

8

[3 ]

[0 ]

56

23

45

[4 ]

[5 ]

[2 ]

37

Heap Sort 78 32 56 8 23 45

45 32 56 8 23 78

45

78

[0 ]

32 8

[3 ]

[1 ]

23

45

[4 ]

[5 ]

56

32

[2 ]

[1 ]

8

[3 ]

[0 ]

56

23

78

[4 ]

[5 ]

[2 ]

38

Heap Sort Algorithm

heapSort (ref heap <array>, val last )

Sorts list[0..last] using heap sort Pre

array is filled last is index to last element in the list Post array 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 39

Selection Sort Efficiency • Straight selection sort: O(n2)

40

Selection Sort Efficiency • Heap sort: O(n log2n)

41

General Sort Concepts Sorts

External

Internal

Insertion

Selection

Exchange

• Insertion • Shell

• Selection • Heap

• Bubble • Quick

• Natural • Balanced • Polyphas e

42

Exchange Sorts • In each pass, elements that are out of order are exchanged, until the entire list is sorted. • Exchange is extensively used.

43

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.

unsorte d 44

Bubble Sort 23 78 45 8 56 32

45

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

46

Bubble Sort Algorithm

bubbleSort (ref list <array>, val last )

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 2 3

4

current = 1 sorted = false 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 return

End

bubbleSort

47

Quick Sort • Developed by C. A. Hoare (1962). • In each pass, a pivot element is selected and the list is divided into three groups: < pivot, = pivot, > pivot Quick sort is continued for the first and third groups. pivo t
k >k 48

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. 49

Quick Sort

pivo t

pivo t

50

Quick Sort 78 21 14 97 87 62 74 85 76 45 84 22

51

78 21 14 97 87 62 74 85 76 45 84 22

78 21 14 97 87 62 74 85 76 45 84 22

78 21 14 22 87 62 74 85 76 45 84 97

78 21 14 22 87 62 74 85 76 45 84 97

78 21 14 22 45 62 74 85 76 87 84 97

78 21 14 22 45 62 74 85 76 87 84 97

78 21 14 22 45 62 74 76 85 87 84 97

52

Quick Sort • D.E. Knuth suggested that when the sort partitions becomes small, straight insertion sort should be used to complete the sorting. pivo t k
>k

53

Quick Sort Algorithm

quickSort (ref list <array>, val left , val right )

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 1 2 3 4 5

if (right - left > minsize) quick sort medianLeft (list, left, right) pivot = list[left] sortLeft = left + 1 sortRight = right 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 54

Quick Sort

2

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 ) else 1 insertionSort (list, left, right)

End

quickSort

55

Quick Sort Algorithm )

medianLeft (ref sortData <array>, val left , val right

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 2 3 4 5 6

mid = (left + right)/2 if (sortData[left].key > sortData[mid].key) 1 exchange (sortData, left, mid) if (sortData[left].key > sortData[right].key) 1 exchange (sortData, left, right) if (sortData[mid].key > sortData[right].key) 1 exchange (sortData, mid, right) exchange (sortData, left, mid) return

End

medianLeft 56

Exchange Sort Efficiency • Bubble sort: f(n) = n(n + 1)/2

= O(n2)

57

Exchange Sort Efficiency • Quick sort: O(n log2n)

58

General Sort Concepts Sorts

External

Internal

Insertion

Selection

Exchange

• Insertion • Shell

• Selection • Heap

• Bubble • Quick

• Natural • Balanced • Polyphas e

59

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.

60

Merging Ordered Files 1 1

2

2

3

3

4

5

4

6

5

8

6

10

8 10 61

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 2 3 4

5

open files read (file1 into record1) read (file2 into record2) 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 = +∝ close files

End

mergeFiles

62

File Sorting Process • Sort phase. • Merge phase.

63

Sort Phase 2,300 records Input file

Sort

records 1-500

1,001-1,500

2,001-2,300

Merge 1 501-1,000 Merge 2

1,501-2,000 64

Merge Phase • Natural merge • Balanced merge • Polyphase merge

65

natural two-way merge records 1-500 records 1,0011,500 records 2.0012,300

records 1-1000 records 2,0012,300

input sort phase mrg 1

merge mrg 3 distribution

mrg 1

merge mrg 3 distribution

records 1-2,000

mrg 1

mrg 2

merge mrg 3

records 501-1000 records 1,5012000

records 1-1000 records 1,0012000 records 2.0012,300 mrg records 1,0012 2,000 records 1-2000 records 2,0012,300 mrg 2

records 2,0012,300

records 1-2,300

66

balanced two-way merge input

records records 1,500 records records 2,300 records 2,300

1-500 1,0012.0011-1000 2,001-

records 1-2,000

sort phase mrg 1 mrg 1 mrg 1

mrg 2

records 501-1000 records 1,5012000

mrg 2

records 1,0012,000

merge

merge mrg 2 merge mrg 3

records 2,0012,300

records 1-2,300

67

polyphase merge records 1-500 records 1,0011,500 records 2.0012,300

records 2,0012,300

input sort phase mrg 1

merge mrg 3

mrg 1

records 1-2,300

merge

mrg 3

records 1-1,000 2,0012,300

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

merge

records 501-1000 records 1,5012000

records 1-1000 records 1,0012000 mrg 2

mrg 3

mrg 1

mrg 2

records 1-1,000 2,0012,300

records 1,0012,000

68