Sorting algorithms

Sorting algorithms in C++
An introduction to sorting algorithm, with details on bubble sort and merge sort algorithms
Computer science principles course

1. Sorting algorithms Eleonora Ciceri , Politecnico di Milano Email: [email protected]

2. What is sorting Sorting is any process of arranging items systematically , with two distinct meanings: Ordering : arranging items in a sequence ordered by some criterion Categorizing : grouping items with similar properties

3. What is a sorting algorithm A sorting algorithm is an algorithm that puts elements of a list in a certain order 78 26 4 12 90 Sorting algorithm 4 12 26 78 90

4. Why do we need to sort? Sorted lists / sequences are useful in the following cases: 1) Efficient lookup and search 56 31 2 47 54 19 64 85 23 56 31 2 47 54 19 64 85 23 56 31 2 47 54 19 64 85 23 56 31 2 47 54 19 64 85 23 56 31 2 47 54 19 64 85 23 56 31 2 47 54 19 64 85 23 Finding “19” Non-ordered list: 6 accesses

5. Why do we need to sort? Sorted lists / sequences are useful in the following cases: 1) Efficient lookup and search 2 19 23 31 47 54 56 64 85 2 19 23 31 47 54 56 64 85 Finding “19” Ordered list: 2 accesses

6. Why do we need to sort? Sorted lists / sequences are useful in the following cases: 2) Merge sequences 2 5 9 13 20 1 4 8 21 1 2 4 5 8 9 13 20 21

7. What do we sort? “Workers sort parcels in a postal facility” (from: Wikipedia, the free encyclopedia)

8. What do we sort? We are going to order collections of data A couple of examples: Arrays Linked lists

9. Compare and swap to sort elements

10. Common building block of sorting algorithms There are several algorithms one could use to order a list of elements Although they are all different, they share a common building block: T hey compare pairs of elements to decide which is their relative order W hen needed, they swap the elements to restore their order 6 8 3 5 9 Compare: 6 5 3 8 9 Swap:

11. How to compare elements: Lexicographic order Elements are usually ordered according to the lexicographic (or, equivalently, lexicographical ) order Also known as dictionary order The lexicographic order is a generalization of the way the alphabetical order of words is based on the alphabetical order of their component letters

12. How to compare elements: Some examples Some examples Order numbers from the smallest to the largest Order words alphabetically Order people ( implemented using a struct that contains name, surname, age ) alphabetically by surname People having the same surname are ordered according to their name People having the same name and surname are ordered according to their age Thus: this proves that comparisons could be based on complex rules that sort out what to do in case of ties

13. Sorting algorithms time complexity

14. Which is the difference between sorting algorithms? Each sorting algorithm is characterized by a particular sorting strategy Are they all equal? NO ! Some of them are naïve, some of them aren’t Naïve algorithms require a larger number of comparisons A larger number of comparisons amount to a larger time frame spent to order elements in the collection

15. (Time) complexity of an algorithm In computer science, the time complexity of an algorithm quantifies the amount of time taken by the algorithm to run The time complexity: is expressed as a function of the length of the input is commonly expressed using big-O notation

16. Big-O notation “The big-O notation describes the limiting behavior of a function when the number of elements it has to process tends to infinity” We’ll try to simplify the concept in this way: number of elements complexity N O ( N 2 ) e.g., the number of elements in the array we want to order e.g., the number of comparisons we need to perform to order the array

17. Big-O notation: Which algorithm is “the best”? To us, an algorithm is “good” if it allows us to save time Let N be the number of elements we want to process E.g., number of elements in an array What if we have four algorithms whose time complexities are as follows? Algorithm 1 O(N) Algorithm 2 O(N 2 ) Algorithm 3 O(log(N)) Algorithm 4 O(N*log(N))

18. Big-O notation: Which algorithm is “the best”? Time complexity can be treated as if it were a mathematical function Being mathematical functions, these curves can be drawn on a graph Algorithm 1 O(N) f(N) = N Algorithm 2 O(N 2 ) f(N) = N 2 Algorithm 3 O(log(N)) f(N) = log(N) Algorithm 4 O(N*log(N)) f(N) = N*log(N)

19. Big-O notation: Which algorithm is “the best”? 2

20. Big-O notation: Which algorithm is “the best”? 2 The higher the number of required operation, the more the time, the worse the algorithm!

21. So, how do we select a sorting algorithm? We can identify several “families” of algorithms: Simple sorts Efficient sorts BubbleSort and variants Distribution sorts

22. So, how do we select a sorting algorithm? We can identify several “families” of algorithms: Simple sorts Efficient sorts BubbleSort and variants Distribution sorts Simple sorting algorithms are efficient on small data amounts (due to low overhead), but generally do not perform well on large lists Insertion sort Selection sort

23. So, how do we select a sorting algorithm? We can identify several “families” of algorithms: Simple sorts Efficient sorts BubbleSort and variants Distribution sorts Efficient sorting algorithms are those algorithms whose average complexity is the best you can find ( O(N*log(N)) ) Merge sort Heap sort Quick sort

24. So, how do we select a sorting algorithm? We can identify several “families” of algorithms: Simple sorts Efficient sorts BubbleSort and variants Distribution sorts Bubble sort algorithm is very simple, and the same characteristics is inherited by all its variants. However, it is highly inefficient (i.e., its time complexity is very high: O(N 2 ) ) Bubble sort Shell sort Comb sort

25. So, how do we select a sorting algorithm? We can identify several “families” of algorithms: Simple sorts Efficient sorts BubbleSort and variants Distribution sorts These algorithms distribute the input to intermediate structures, which are gathered and placed on the output. They are useful in case of very large data sets that do not fit in memory (since the intermediate structures can be deployed on different machines ) Counting sort Bucket sort Radix sort

26. One of the most inefficient algorithms ( O(N 2 ) ) One of the most efficientalgorithms ( O(N*log(N)) )

27. A quick note on time complexity A n algorithm performance may vary with different input of the same sizes [1 2 3 4 5] does not require any swap [5 4 3 2 1] requires a lot of swaps! We commonly attribute to each algorithm: A worst-case complexity (maximum amount of time it may require) An average-case complexity (averaged on all possible inputs) We won’t go into the details, since this is just an introduction to sorting algorithms 

28. An inefficient sorting algorithm: the Bubble Sort algorithm

29. Bubble sort: the idea The bubble sort algorithm repeatedly steps through the list of elements to be sorted: Comparing each pair of adjacent elements Swapping them if they are in wrong order The algorithm stops when, by going through the whole array, we do not require any swap (i.e., the array is fully ordered)

30. Bubble sort: the running example Array: [ 5 1 4 2 8] 5 > 1, thus: swap required Swapped something? False End of iteration? False

31. Bubble sort: the running example Array: [1 5 4 2 8] 5 > 4, thus: swap required Swapped something? Yes End of iteration? False

32. Bubble sort: the running example Array: [1 4 5 2 8] 5 > 2, thus: swap required Swapped something? Yes End of iteration? False

33. Bubble sort: the running example Array: [1 4 2 5 8 ] 5 < 8 , thus: swap not required Swapped something? Yes End of iteration? Yes

34. Bubble sort: the running example Array: [1 4 2 5 8] We need to proceed, since in the current iteration we swapped something Following operations: Exclude “8” from next iteration Restart with a new iteration Swapped something? Yes End of iteration? Yes

35. Bubble sort: the running example Array: [ 1 4 2 5 8] 1 < 4, thus: swap not required Swapped something? No End of iteration? No

36. Bubble sort: the running example Array: [1 4 2 5 8] 4 > 2, thus: swap required Swapped something? No End of iteration? No

37. Bubble sort: the running example Array: [1 2 4 5 8] 4 < 5, thus: swap not required Swapped something? Yes End of iteration? Yes

38. Bubble sort: the running example Array: [1 2 4 5 8] We need to proceed, since in the current iteration we swapped something Following operations: Exclude “5” from next iteration Restart with a new iteration Swapped something? Yes End of iteration? Yes

39. Bubble sort: the running example Array: [ 1 2 4 5 8] 1 < 2, thus: swap not required Swapped something? No End of iteration? No

40. Bubble sort: the running example Array: [1 2 4 5 8] 2 < 4, thus: swap not required Swapped something? No End of iteration? Yes

41. Bubble sort: the running example Array: [1 2 4 5 8] In the current iteration nothing was swapped The algorithm terminates Swapped something? No End of iteration? Yes

42. Bubble sort: the pseudo-code procedure bubbleSort ( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do if A[i-1] > A[ i ] then swap (A[i-1], A[i]) swapped = true end if end for n = n - 1 until not swapped end procedure (from: Wikipedia, the free encyclopedia)

43. Bubble sort in C+ +: Iterate over the array We will use the concept of iterators over the array To iterate over the array: int * first int * last while (first < last) { // do what you want first++; }

44. Bubble sort in C+ +: The algorithm void bubble_sort_int ( int * first, int * last) { bool swapped; do { swapped = false ; int * current = first + 1 ; while ( current < last ) { if (*(current- 1 ) > *current) { swap(current- 1 , current); swapped = true ; } current++; } last--; } while (swapped); }

45. Bubble sort in C++: Swapping elements void swap ( int * first, int * second) { int temp = *first; *first = *second; *second = temp; }

46. An efficient sorting algorithm: the Merge Sort algorithm

47. Merge sort: the idea The merge sort is a divide-and-conquer algorithm where: The unsorted list of N elements is divided into N sub-lists , each containing one element Sub-lists are repeatedly merged to produce new sorted sub-lists

48. How to merge two sub-lists Sub-lists are merged so as produce a longer sorted sub-list At each step, we: compare the first element of sub-list A and the first element of sub-list B select the smallest element insert it into the resulting list

49. How to merge two sub-lists: An example How to merge these: to obtain this? 1 6 10 4 5 27 1 4 5 6 10 27

50. How to merge two sub-lists: An example 1 6 10 4 5 27 1 1)

51. How to merge two sub-lists: An example 1 6 10 4 5 27 1 6 10 4 5 27 1 4 1) 2 )

52. How to merge two sub-lists: An example 1 6 10 4 5 27 1 6 10 4 5 27 1 4 6 10 5 27 1 4 5 1) 2 ) 3 )

53. How to merge two sub-lists: An example 1 6 10 4 5 27 1 6 10 4 5 27 1 4 6 10 5 27 1 4 5 6 10 27 1 4 5 6 1) 2 ) 3 ) 4 )

54. How to merge two sub-lists: An example 1 6 10 4 5 27 1 6 10 4 5 27 1 4 6 10 5 27 1 4 5 6 10 27 1 4 5 6 10 27 1 4 5 6 10 1) 2 ) 3 ) 4 ) 5 )

55. How to merge two sub-lists: An example 1 6 10 4 5 27 1 6 10 4 5 27 1 4 6 10 5 27 1 4 5 6 10 27 1 4 5 6 10 27 1 4 5 6 10 27 / 1 4 5 6 10 27 1) 2 ) 3 ) 4 ) 5 ) 6 )

56. How to merge two sub-lists: The pseudocode function merge(left, right) // merge lists until at least one of them is empty while notempty (left) and notempty (right) if first(left) <= first(right) append first(left) to result left = rest( left ) else append first(right) to result right = rest(right ) // left has elements left while notempty (left) append first(left) to result left = rest( left ) / / right has elements left while notempty (right) append first(right) to result right = rest(right ) return result (from: Wikipedia, the free encyclopedia)

57. Merge sort: the step-by-step algorithm We start with this list… …and, according to the algorithm, we need to keep dividing it in “ left sub-list ” and “ right sub-list ”…

58. Merge sort: the step-by-step algorithm …and split again, since sub-lists length is greater than 1…

59. Merge sort: the step-by-step algorithm … and again.

60. Merge sort: the step-by-step algorithm Now it’s time to merge the lists, in pairs, so that the resulting list is ordered We start from the bottom, i.e., from the shorter sub-lists we extracted before This is now ordered

61. Merge sort: the step-by-step algorithm Merge… This is now ordered

62. Merge sort: the step-by-step algorithm …and merge. This is now ordered

63. Trying to generalize: Which operations are needed at each iteration? Split phase: If the current list has length 1, stop with the split phase If the current list has length > 1, split it in two parts (left, right) Merge phase: Merge the left and right parts into a unique, ordered list

64. Trying to generalize: What happens to a list? Given a list: Split in two parts (left and right) 1 Split in two parts (left and right) 1 Do something to order the sub-list Do something to order the sub-list 2 2 Merge the parts in a single list 3 Merge the parts in a single list 3

65. Trying to generalize: What happens to a list? Algorithmically : [left, right] = split(list) left = order(left) right = order(right) list = merge(left, right)

66. Trying to generalize: What happens to a list? Algorithmically : [left, right] = split(list) left = mergeSort (left) right = mergeSort (right) list = merge(left, right) This is a recursive call to the merge sort function

67. Trying to generalize: What happens to a list? Now we finalize the algorithm : function mergeSort (list) { if (length(list) == 1) return list [left, right] = split(list) left = mergeSort (left) right = mergeSort (right) list = merge(left, right) return list }

68. Trying to generalize: What happens to a list? Now we finalize the algorithm : function mergeSort (list) { if (length(list) == 1) return list [left, right] = split(list) left = mergeSort (left) right = mergeSort (right) list = merge(left, right) return list } This function splits the list in two parts having the same length This function merges the sub-lists so that the result is ordered

69. Merge sort in C+ +: Iterate over the array We will use the concept of iterators over the array To iterate over the array: int * first int * last while (first < last) { // do what you want first++; }

70. Merge sort in C+ +: Iterate over the array We will use the concept of iterators over the array To iterate over the array: int * first int * last while (first < last) { // do what you want first++; } Remember: last always points outside the array

71. Merge sort in C++: Split the array in two parts If the length of the array is even: The sub-lists are as follows: Left: from first (included) to middle (excluded) Right: from middle (included) to last (excluded) int * first int * last int * middle

72. Merge sort in C++: Split the array in two parts If the length of the array is even: The sub-lists are as follows: Left: from first (included) to middle (excluded) Right: from middle (included) to last (excluded) int * first int * last int * middle LEFT

73. Merge sort in C++: Split the array in two parts If the length of the array is even: The sub-lists are as follows: Left: from first (included) to middle (excluded) Right: from middle (included) to last (excluded) int * first int * last int * middle RIGHT

74. Merge sort in C++: Split the array in two parts If the length of the array is odd: The sub-lists are as follows: Left: from first (included) to middle (excluded) Right: from middle (included) to last (excluded) In this case: right is longer than left int * first int * last int * middle

75. Merge sort in C++: The recursive algorithm void merge_sort_int ( int * first, int * last) { int N = last - first; if (N <= 1 ) return ; int * middle = first + N/ 2 ; merge_sort_int ( first, middle); merge_sort_int ( middle, last); merge (first, middle, last); }

76. Merge sort in C++: The merge function void merge ( int * first, int * middle, int * last) { std :: size_t N = last - first; int *result = new int [N], * result_current = result, * left_current = first, * right_current = middle; while ( left_current < middle && right_current < last) { if (* left_current <= * right_current ) { * result_current = * left_current ; left_current ++; } else { * result_current = * right_current ; right_current ++; } result_current ++; } fill_with_remaining_elements ( result_current , left_current , middle ); fill_with_remaining_elements ( result_current , right_current , last); for ( std :: size_t i = ; i < N; i++) first[i] = result [i]; delete [] result ; }

77. Merge sort in C++: The merge function void merge ( int * first, int * middle, int * last) { std :: size_t N = last - first; int *result = new int [N], * result_current = result, * left_current = first, * right_current = middle; while ( left_current < middle && right_current < last) { if (* left_current <= * right_current ) { * result_current = * left_current ; left_current ++; } else { * result_current = * right_current ; right_current ++; } result_current ++; } fill_with_remaining_elements ( result_current , left_current , middle ); fill_with_remaining_elements ( result_current , right_current , last); for ( std :: size_t i = ; i < N; i++) first[i] = result [i]; delete [] result ; } result is a temporary buffer that contains the ordered array At the end of the function, result is restored in the original array and deleted

78. Merge sort in C++: The merge function void fill_with_remaining_elements ( int *& result_current , int * sub_list_current , int * sub_list_last ) { while ( sub_list_current < sub_list_last ) { * result_current = * sub_list_current ; sub_list_current ++; result_current ++; } }

79. References

80. References https://en.wikipedia.org/wiki/ Sorting https://en.wikipedia.org/wiki/ Sorting_algorithm https://en.wikipedia.org/wiki/ Time_complexity https://en.wikipedia.org/wiki/ Big_O_notation https://en.wikipedia.org/wiki/ Bubble_sort https://en.wikipedia.org/wiki/ Merge_sort

81. References http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c