# Lesson 47: The Factorial Algorithm

In mathematics, the factorial of a positive integer n, denoted by n!, is the product of all positive integers less than or equal to n: n!=n*(n-1)(n-2)… For example: 5! = 5 * 4 * 3 * 2 * 1 = 120. The value of 0! is 1, according to the convention for an empty product.

## Implementation

• If num is equal to 0, The factorial is 1. Stop. We have the result. Otherwise…
• Set multiplier to 1
• Set factorial to 1
• While multiplier is not equal to num, do steps 5 and 6
• Multiply factorial by multiplier and assign the result to…

# Lesson 46: The Binary Search Algorithm

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. …

# Lesson 45: The Linear Search Algorithm

In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.

## Characteristics

• A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list.

## Time complexity

Worst-case performance: O(n)
Best-case performance: O(1)
Average performance: O(n)
Worst-case space complexity: O(1) iterative

## Implementation

`final class LinearSearch {    static int search(final int[] in, final int value) {        for (var i = 0; i < in.length; i++) {            if (in[i] == value) {                return i;            }        }        return -1;    }}`

# Lesson 44: The Bucket Sort Algorithm

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. …

# Lesson 43: The Radix Sort Algorithm

In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort.

Radix sort can be applied to data that can be sorted lexicographically, be they integers, words, punch cards, playing cards, or the mail.

## Characteristics

• Makes assumptions about the data
• Data must have same…

# Lesson 42: The Counting Sort Algorithm

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater…

# Lesson 41: The Quick Sort Algorithm

Quicksort is a divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

## Characteristics

• Divide and conquer algorithm
• Recursive algorithm
• Uses a pivot element to partition the array into two parts
• Elements < pivot to its left, elements > pivot to its right
• Pivot will then be in its correct sorted position
• Process is now repeated for the…

# Lesson 40: The Merge Sort Algorithm

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

## Characteristics

• Divide and conquer algorithm
• Recursive algorithm
• Two phases: Splitting and Merging

# Lesson 39: The Shell Sort Algorithm

Shellsort, also known as Shell sort or Shell’s method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959. The running time of Shellsort is heavily dependent on the gap sequence…

# Lesson 38: The Insertion Sort Algorithm

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

## Characteristics

• In-place algorithm
• It will take 100 steps to sort 10 items, 10000 steps to sort 100 items, 1000000 steps to sort 1000 items
• Stable algorithm

## Time complexity

Worst-case performance: О(n²) comparisons and swaps
Best-case performance: O(n) comparisons, O(1) swaps
Average performance: О(n²) comparisons and swaps
Worst-case space complexity: О(n) total, O(1) auxiliary

## Implementation

`static int[] sort(final…` ## Andrey Karazhev

Software Engineer