Basic Search & Sorting Methods Analyzed

This experiment was performed to analyse the performance of a few basic search and sorting methods with different array sizes. The sorting methods analyzed were: bubble, selection, and insertion sort. The search methods analyzed were: linear and binary. NOTE: (raw data appended to end of document)

This graph shows how three sorting methods (insertion, selection, bubble) performance varies with increasing array sizes. The main differences in performance can be easily seen in the different algorithms used. With Bubble Sort, each element is compared to every other element, because of this, longer lists increase time at an exponential rate. Selection sort simply looks consecutively for the smallest element and moves it to the beginning of the list. This provides a better, but still steadily increasing rate. Insertion sort provides slightly better time complexity than selection because instead of looking over the entire list, it only looks at where each element can be placed in a previously sorted sublist of elements. However, because of the algorithm used (swaps being made at each check vs at end of search for selection) it is slower in implementation.

This graphs shows two search methods: linear and binary. The linear nature of the linear algorithm's results is easily understood because the linear algorithm looks at each element to check for a match. As the number of checks increases, the time increases at the same rate. The binary results can also be understood because (number of elements) ~ 2^(number of queries) or expected time is log2(number of elements) - 1. Because of this, even with increased length, the time changed very little. However, this method requires starting with a sorted list which takes significantly more time to create.

Bubble avg(3) | Selection avg(3) | Insertion avg(3) | Linear avg(3) | Binary avg(3) | |

10 | 0.000016 | 0.000003 | 0.000003 | 0.000002 | 0.000002 |

50 | 0.000033 | 0.000012 | 0.000016 | 0.000002 | 0.000002 |

100 | 0.000081 | 0.000032 | 0.000036 | 0.000003 | 0.000002 |

500 | 0.001877 | 0.000605 | 0.000841 | 0.000004 | 0.000002 |

1000 | 0.00753 | 0.002331 | 0.003329 | 0.000005 | 0.000002 |

5000 | 0.162893 | 0.043847 | 0.064666 | 0.000016 | 0.000002 |

10000 | 0.57739 | 0.175069 | 0.254346 | 0.00003 | 0.000001 |

15000 | 1.298288 | 0.393599 | 0.579489 | 0.000044 | 0.000002 |

20000 | 2.307104 | 0.699391 | 1.040294 | 0.000058 | 0.000002 |