CIS 150 Sorting

• Implement a simple sort algorithm.
• Discuss algorithm run time (order).

// Assume that the data is in an array for each element p from the first to the next to last for each element q from just after p to the last if p and q are out of order, then swap them

void sort(int ar[], int len) { int temp, i, j; for (i=0; i<len-1; i++) { for (j=i+1; j<len; j++) { if (ar[j] < ar[i]) { temp = ar[j]; ar[j] = ar[i]; ar[i] = temp; } } } }

• Algorithms are analyzed by calculating the resources they use (memory, runtime).
• The order of an algorithm is used to estimate runtimes and is based on the number of data items being processed.
• Some common sorts (with their orders) are:
  • bogosort (also called robsort, stupidsort, slowsort) (n * n!)
  • bubble sort (n²)
  • the sort example in this web page (n²)
  • Wold sort (n²)
  • selection (n²)
  • insertion sort (n²)
  • shell sort (n (log n)²)
  • heap sort (n log n)
  • quick sort (n log n)
• The fastest sorts have order: n log n