Sorting Algorithms in C

• Study notes on sorting algorithms and data structures in C

Sorting Algorithms

• There are several sorting algorithms will be covered
• These include bubble sort, selection sort, insertion sort, heap sort, quicksort, and shell sort.
• Visualizations of different sorting algorithms can be found at:
  • https://www.toptal.com/developers/sorting-algorithms/
  • http://www.bluffton.edu/homepages/facstaff/nesterd/java/SortingDemo.html
• The usefulness of each algorithm can vary based on the data being sorted, such as size, randomness, or existing order
• All algorithms perform the same task to sort the data

Bubble Sort

• This is one of the easiest sorting methods to implement
• It continually swaps adjacent values within a list to order it
• The largest value will bubble to the end of the list after the first pass
• The sort completes after a pass where no swaps occur
• Bubble sort is likely the worst sort in terms of performance, with O(n²) time complexity,
• it typically induces a significant number of swaps
• This method is fast if the list is nearly sorted, potentially performing at O(n)

Selection Sort

• Similar to bubble sort it is easy to implement
• It finds the smallest number in the list and moves it to the beginning
• Then repeats the process for the remain list
• Essentially, it finds the next smallest number and puts it next in the sorted list
• Each time, the largest number could be found and moved to the end
• Regarding performance, it is almost as bad as bubble sort
• Although it does very few swaps, selection sort always runs in O(n²) time
• On the same data, selection sort is usually faster than bubble sort due to fewer swaps, the difference isn't significant
• They are both O(n²)

Insertion Sort

• Insertion sort involves inserting each number into its correct position within a partially sorted list
• It iterates through the list to insert each number where it needs to go
• Very similar to performing a selection sort
• One possible implementation is to find an element that's out of order and then move existing elements to make room for it
• Insertion sort also runs in O(n²) worst-case time
• This can be useful if the data set is nearly sorted.
• It sometimes acts as a recursive base case for quicksort or merge sort divide-and-conquer algorithms
• If the data is nearly sorted, insertion sort may take O(n) time, but this is uncommon by itself

Heap Sort

• Heap sort is interpreting data as a complete binary tree
• A max heap is a binary tree where the root is greater than or equal to its children, which are also heaps
• The data is organized without particular order, starting at the root, then the left and right children in order
• Starting from the last nonleaf node, convert the partial tree rooted there to a max-heap, which may require swaps
• The max-heap has the largest number as root
• Next, go to the next non-leaf node to the left and make the partial tree there a max-heap
• Once the left side of the tree is reached, start over on the right at the level above and repeat the process
• If that wasn’t tricky enough, move the node at the root (top) to the last node in the heap
• It could also just remove it, move it to a list or queue
• Re max-heap the new tree
• Place the new root in the next node to the left and re max-heap, etc
• It runs in order O(n log(n)), but is considered quite good
• In a nearly sorted case, heap sort could destroy the original order
• In a reversed case, heap sort is as fast as possible
• Requires first loop to put data in heap order
• Second loop re-heaps the data repeatedly after extracting the maximum each time
• If a computer processes one million comparisons per second and needs to sort one million items, a selection sort takes approximately 12 days
• With a heap sort, this process takes about 20 seconds

Quicksort

• Algorithm that works by partitioning a list with regard to a selected pivot
• The pivot is a number in the list used to organize the other values
• The pivot can be the last, middle or a random number.
• Numbers smaller than the pivot are moved to the front, followed by the pivot, then the larger numbers.
• The list is then split at the pivot's new position
• Recursive calls are then made using the same process on the 2 halves
• Each number in the array is looked at up to the pivot
• Bigger numbers are left alone, smaller numbers are swapped with the split position
• The split position starts at zero, and increments by one as numbers are swapped
• There is then one more swap between the pivot and the number at the split position
• Divide the list at the split position and perform quicksort on each part recursively
• The computational complexity and performance of Quicksort can be unclear
• Technically, its O(n log(n)), but its performance relies on how you choose the pivot
• If the smallest number is the initial pivot, then it will perform nearly as badly as a selection sort, O(n²)
• Pivot can be a random number, median number, or have a dual pivot.
• What works well depends on the properties of data and how it is sorted

Shell Sort

• Donald Shell named this sort that divides elements by certain number of steps while swapping if needed
• Initiate with larger steps that turn into smaller ones
• With an example comparison between all elements that have 103 elements for their gap (gap of 103)

Shell Sort Complexity

• Difficult algorithm to analyze, shell sort is not as fast as a heap sort or quick sort
• However, shell sort is easier to implement and requires less memory
• The idea of shell sort is that after each incremental sort, the list will be in a "closer-to-sorted" order
• Next steps in shell sort will take less time overall
• Given code uses "not so good" gap sequence, first gap sixe is half the data size, and next gap is half that, and so on
• The overall computational complexity of Shell Sort depends on the gap sequence
• O(n²) is the complexity for simple gap sequence
• Better gap sequence such as Tokuda's has unknown but better complexity of O(n4/3).
• This is not as good as O(n log(n))

Other Topics

• Bubble sort: O(n²), requires many swaps and is slow
• Selection sort: O(n²), requires very few swaps
• Insertion sort: O(n²), fast with nearly sorted list
• Heap sort: O(nlog(n)) always, but is complex
• Quicksort: O(n log(n)) but sometimes O(n²), efficient
• Shell sort: ~ O(n4/3) with good gap sequence, needs very little memory
• In general, if data nature unknown, sort with quicksort
• If the data nature is known, research and find the best algorithm
• For programmers, avoid writing sorting Algorithms
• Sorting functions are often made available as part of the language library
• Java has Arrays.sort()
• Is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch that can have O(n log(n)) performance
• C uses qsort() function and is implemented differently on different systems
• Usually uses Quicksort with good way to choose pivot, e.g Cygwin while Linux uses a Merge Sort algorithm
• Code is also here
• C: lets you pass function pointers as parameters to functions -The closest thing in Java is Lambda expressions

C library qsort function

• The Function prototype for qsort:
  • void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*));
• base points to start of an array
• nmemb is the number of values in an array
• size is the size in bytes of each element of the array
• compar is a comparison function that takes two parameters to compare and has returns
• When using qsort a function must be written to compare two of the values

C Code Information

• An integer must be returned by the comparison function
• Negative number when parameter 1 is less than 2
• Zero when parameters are equal
• A Positive Number when parameter one is larger than two
• Name of the function should be placed as the last perimeter to qsort with no parenthesizes.

Sorting a linked list

• Sorting linked data structures is efficient when the size of each node structure is large
• There is no need to copy the node contents as with an array, just change next pointers
• Other sort algorithms are possible, but would be even more complicated
• To sort a linked list that swaps elements like bubble sort, need to adjust next pointers to swap adjacent nodes