CIS 111 Sorting

• Discuss the order of different sorting algorithms
• Implement an array or list sort

• This is a great opportunity to discuss the order of algorithms. Order refers to expected runtime based on the size of the input data.
• You are not expected to be able to create sorting algorithms out of thin air during the rest of this course, but hopefully some of the concepts will stick.
• You are expected to be able to modify a given sort algorithm to fit new situations you run into - this generally involves changing the data type used and modifying the comparison code (where it is decided which item comes first).
• As we look at sorting algorithms, it is important to note that you usually don't have to write your own algorithms. It does help greatly if you are able to translate a sort algorithm from pseudocode into the language you are using, or more commonly, from one programming language into another.
• Different sorting routines have different advantages and disadvantages. Some are simple to write, but those are often quite inefficient. Examples of these simpler sorts include shell sort, bubble sort, and selection sort. Some are optimized for dealing with files that don't fit into memory all at once, such as mergesort, which is often used together with other sorts. Some sorts use complex data structure concepts to gain efficiency, such as heapsort and quicksort.
• Order of some common sorting algorithms:
  • bubble sort (n²)
  • my sort (n²)
  • Wold sort (n²)
  • selection (n²)
  • insertion sort (n²)
  • shell sort (n (log n)²)
  • heap sort (n log n)
  • quick sort (n log n)
  • rob sort (not usually run due to time constraints on the existence of the universe)

def is_sorted(ar): for i in range(0, len(ar)-1): if ar[i] > ar[i+1]: return False return True def bubble_sort(ar): n = len(ar) swapped = True while swapped: swapped = False for i in range(1, n): if ar[i-1] > ar[i]: ar[i-1], ar[i] = ar[i], ar[i-1] swapped = True n = n - 1 lst = [] import random for i in range(2000): n = random.randint(1, 5000) while n in lst: n = random.randint(1, 5000) lst.append(n) print("List sorted before sort: ", is_sorted(lst)) bubble_sort(lst) print("List sorted after sort: ", is_sorted(lst))