Java Tutorial: Sorting and Searching
Posted 2020/06/02
Time Complexity
Time complexity is how many steps are required to complete an algorithm. When measuring time complexity, we make an average, best, and worst time complexities. The average time complexity is roughly how many steps are performed on average. The best and worst time complexities are how many steps it takes in the algorithm’s best and worstcase scenarios. Time complexity is expressed using BigO notation, where n represents the input size or array length. For example a time complexity of O(n) means that the algorithm will take the same amount of steps as the array size.
Sorting
Sorting is the process of putting items of a list in a certain order. Most times, sorting is done to order a list in numerical or lexicographical order. There are many different algorithms for sorting with varying levels of simplicity and efficiency.
Bubble Sort
Bubble sort is one of the simplest sorting algorithms. This algorithm looks at adjacent values in the list and compares them and swaps if that pair is in the wrong order. It repeats this until the list is sorted.
Time Complexity
Worstcase: O(n^{2})
Average: O(n^{2})
Bestcase: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

Insertion Sort
Insertion sort builds the sorted list one item at a time. It creates two sublists and takes the next item of the unsorted sublist and inserts it in its proper position in the sorted sublist. It repeats until all items have been placed in their proper position in the sorted sublist.
Time Complexity
Worstcase: O(n^{2})
Average: O(n^{2})
Bestcase: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 

Selection Sort
Selection sort also builds the sorted list one item at a time. It creates two sublists and scans the unsorted sublist for the next item to place at the end of the sorted sublist. It repeats until all items have been moved from the unsorted sublist to the sorted sublist.
Time Complexity
Worstcase: O(n^{2})
Average: O(n^{2})
Bestcase: O(n^{2})
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 

Merge Sort
Merge sort is a divide and conquer sorting algorithm. The algorithm splits the list into sublists of just one element each and merges the sorted sublists together to make the final sorted list. This algorithm is a recursive algorithm.
Time Complexity
Worstcase: O(n log n)
Average: O(n log n)
Bestcase: O(n log n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 

Searching
Searching is the process of fetching data stored in data structures like arrays or lists. Most search algorithms are used to find the location of an item in a data structure.
Linear/Sequential Search
Linear or sequential search is a bruteforce algorithm that scans the list or array looking for a match to the search term. This search algorithm is not time efficient and is very slow when used on large lists.
Time Complexity
Worstcase: O(n)
Average: O(n)
Bestcase: O(1)
1 2 3 4 5 6 

Binary/Logarithmic Search
Binary or logarithmic search is a divide and conquer algorithm that requires the data structure to be already sorted. The algorithm splits the data set in half and compares the search term with the item in the middle. Using this comparison it knows which half to search for the item. It then repeats this process on the half until the item has been found.
Time Complexity
Worstcase: O( log n)
Average: O( log n)
Bestcase: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
