Sorting

Sorting data

Quadratic algorithms

• Average speed: O(n^2)
• Worst case: O(n^2)
• Good when n is small: < 1000

Examples (in order of increasing speed)

• Bubble sort
• Insertion sort
• Selection sort
• Shell sort

Logartithmic algorithms

• Average speed: O(n log n)
• Worst case: O(n log n) (*see notes below)
• Good when n is large: > 10,000

Examples (in order of increasing speed)

• Heap sort
• Merge sort
• Quick sort

Notes

• If quick sort is used on data that's already sorted, it runs at O(n^2); otherwise, it's almost always faster than heap sort and merge sort.

Searching

Examples (in order of increasing speed)

• Binary trees

• B-Trees
• Hash tables

Notes

• Binary trees, while simple in structure, are poorly suited for large amounts of data.  To ensure reasonable speed for moderate amounts of data, binary trees must be kept well-balanced, which significantly increases the difficulty of building them.

Simple searching

Binary search

• For simple, non-changing data in a sorted array.
• Start in the middle of the array, and take a halfway jump in the desired direction until the target data is found (each jump being half the size of the previous one).
• If a group of strings are stored in a single array, a binary search is only possible if the same number of bytes (characters) is set aside for each string (i.e. the strings are located at position [0], [10], [20], [30], ...; or [0], [8], [16], [24], ...; etc.)