Sorting & Searching

Question 1

CommonSortingAlgorithms

Answer 1

Bubble Sort
Selection Sort
Merge Sort
Quick Sort
Radix Sort

Question 2

Bubble Sort I Runtime: 0( n2 ) average and worst case. Memory: 0( 1) .

Answer 2

In bubble sort, we start at the beginning of the array and swap the first two elements if the first is greater than the second. Then, we go to the next pair, and so on, continuously making sweeps of the array until it is sorted. In doing so, the smaller items slowly”bubble” up to the beginning of the list.

Question 3

SelectionSort I Runtime: 0(n2) average and worst case. Memory:0(1).

Answer 3

Selection sort is the child’s algorithm: simple, but inefficient. Find the smallest element using a linear scan and move it to the front (swapping it with the front element). Then, find the second smallest and move it, again doing a linear scan. Continue doing this until all the elements are in place.

Question 4

Merge Sort I Runtime: 0 ( n log ( n)) average and worst case. Memory: Depends.

Answer 4

Merge sort divides the array in half, sorts each of those halves, and then merges them back together. Each of those halves has the same sorting algorithm applied to it. Eventually, you are merging just two single­ element arrays.

Question 5

Quick Sort I Runtime: O(n log(n)) average, O(n2 ) worst case. Memory: 0( log(n)).

Answer 5

In quick sort we pick a random element and partition the array, such that all numbers that are less than the partitioning element come before all elements that are greater than it. The partitioning can be performed efficiently through a series of swaps.

Question 6

Radix Sort I Runtime: 0(kn)

Answer 6

Radix sort is a sorting algorithm for integers (and some other data types) that takes advantage of the fact that integers have a finite number of bits. In radix sort, we iterate through each digit of the number, grouping numbers by each digit.