Sorting Algorithms

Question 1

describe linear search

Answer 1

search list by inspecting each element

Question 2

describe quicksort

Answer 2

partition array around pivot such that: Left side of pivot contains all the elements that are less than the pivot element Right side contains all elements greater than the pivot

Question 3

describe merge sort

Answer 3

It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

Question 4

describe insertion sort

Answer 4

builds the final sorted array (or list) one item at a time

Question 5

what does in place mean

Answer 5

transforms input using no auxiliary data structure

Question 6

what does stable mean

Answer 6

maintain the relative order of records with equal keys

Question 7

give the merge sort complexities

Answer 7

worst O(n log n)
best O(n log n)
average O(n log n)
space O(n)

Question 8

give the insertion sort complexities

Answer 8

worst O(n^2)
best O(n)
average O(n^2)
space O(n)