# Sorting and Searches

Source: https://wisconsin.twango.dev/fa24-cs300/u3-algorithms/sorting-and-search

# Sorting and Searches
Sorting and searching are two of the most common operations in computer science. Sorting is the process of arranging elements in a specific order, while searching is the process of finding a specific element in a collection of elements.

## Sorts

### Bubble Sort
Bubbles elements to the top of the list by comparing adjacent elements and swapping them if they are in the wrong order.

- Worst Case Time Complexity: $O(N^2)$
- Best Case Time Complexity: $\Omega(N)$

### Selection Sort
Selects the smallest element from the unsorted portion of the list and swaps it with the first unsorted element.

- Worst Case Time Complexity: $O(N^2)$
- Best Case Time Complexity: $\Omega(N^2)$
- Tight Bound Time Complexity: $\Theta(N^2)$

### Insertion Sort
Builds the sorted list one element at a time by inserting elements into their correct position.

- Worst Case Time Complexity: $O(N^2)$
- Best Case Time Complexity: $\Omega(N)$

### Merge Sort
Divides the list into smaller sublists, sorts the sublists, and then merges them back together.

- Worst Case Time Complexity: $O(N \log N)$
- Best Case Time Complexity: $\Omega(N \log N)$

### Quick Sort
Divides the list into smaller sublists based on a pivot element, sorts the sublists, and then combines them.

- Worst Case Time Complexity: $O(N^2)$
- Best Case Time Complexity: $\Omega(N \log N)$

## Searches

### Linear Search

Searches for an element by checking each element in the list sequentially.

- Worst Case Time Complexity: $O(N)$
- Best Case Time Complexity: $\Omega(1)$

### Binary Search

Given a sorted array, searches for an element in a sorted list by repeatedly dividing the search interval in half.

- Worst Case Time Complexity: $O(\log N)$
- Best Case Time Complexity: $\Omega(1)$

## Detailed implementations

- [[u3-algorithms/sorting-and-search/sorting/bogo-sort|Bogo Sort]]
- [[u3-algorithms/sorting-and-search/sorting/bubble-sort|Bubble Sort]]
- [[u3-algorithms/sorting-and-search/sorting/insertion-sort|Insertion Sort]]
- [[u3-algorithms/sorting-and-search/sorting/merge-sort|Merge Sort]]
- [[u3-algorithms/sorting-and-search/sorting/quick-sort|Quick Sort]]
- [[u3-algorithms/sorting-and-search/sorting/selection-sort|Selection Sort]]
- [[u3-algorithms/sorting-and-search/searches/binary-search|Binary Search]]
- [[u3-algorithms/sorting-and-search/searches/linear-search|Linear Search]]

Related: [[u3-algorithms/asymptotic-analysis]], [[u3-algorithms/recursion]], [[p06/README]].

## Source

The existing course note was retained and normalized during the merge.