## Randomness

Randomness is an important computational resource, just as running time and memory space. Randomness sometimes is essential for designing algorithms. Randomness is useful! Quick Select In quick sort, a random pivot selection has the property that, for any input data, …

## Quick Sort

Quick sort is to partition the array around one element and then sort each part recursively. Pick up one element as the pivot Move all elements less than the pivot to the left, and all elements greater than the pivot …

## Merge Sort

Consider the problem of sorting an array of numbers in order. Merge sort is to recursively divide the array in half, and then recombine the sorted subarrays. Divide the array in half. Recursively divide until each subarray has only one …

## Linear and Binary Search

Searching is to find a target in a collection of elements, or determine the target does not exist. Here we consider data in arrays stored in the memory; while in real problems data may be stored in disk files, databases, …