Big O

Question 1

List four common sorting algorithms

Answer 1

• Bubble
• Merge
• Quick
• Insertion
• Selection
• Heap
• Shell
• Radix

Question 2

Discuss code implementation for bubble sort

Answer 2

Bubble sort sorts by

• Looping through the list
• Comparing the current value of each item with the value in the list.
• Swap values if needed.

Question 3

Discuss time complexity of bubble sort

Answer 3

• Time complexity: O(n^2)
• Complexity is directly related to the size of the input
• Bubble sort goes through the list twice

Question 4

Identify the following sorting algorithm

Answer 4

• Bubble sort

Question 5

Describe the difference between insertion and selection sort

Answer 5

• Insertion builds a new sorted list
• Selection sorts the array in place
• Insertion places the current value in the right order as it loops
• Selection loops to find the next value and swaps it to the correct location

Question 6

Discuss the time complexity of selection sort

Answer 6

• Time complexity: O(n^2)
• The complexity is directly related to the size of the input
• Selection sort goes through the list twice

Question 7

Discuss common uses of sorting algorithms in programming

Answer 7

• Presentation - Data is commonly viewed in a sorted manner
• Searching - It is more efficient to search through a list when it is sorted
• Element uniqueness - It is easier to find duplicate data when a list is sorted
• Data analysis - sorting is used to figure out frequency, median, etc

Question 8

Describe quick sort

Answer 8

• Implements in-place sorting.
• Picks a pivot from the list and it partitions the values, placing lower values to one side and higher values on the other. It repeats the process recursively for the sub lists left and right of the pivot.
• Similar to selection sort.

Question 9

Discuss the time complexity of quick sort

Answer 9

• Time complexity: O(n log(n))
• Quick sort will partition the list into 2 equal pieces repeatedly, each time called on a list half the size (log(n) complexity).
• The process of partitioning (moving items left or right of the pivot) at each level will require operations the size of the list ‘n’ in the worst case scenario, making the sorting algorithm O(n * log(n))

Question 10

Which sorting algorithm is most efficient to sort a nearly sorted array in ascending order, such as [1,2,8,3,4,5,6,7,9,10]

Answer 10

• Either Bubble or Insertion sort
• Since most items are in the right order, insertion sort will require fewer swaps and comparisons as it loops through the list
• Since most items are in the right order, bubble sort will require to swap only a few items and ignore the items already in place
• Quick and merge sort will perform a similar operation regardless of how sorted the list is.

Question 11

Describe merge sort

Answer 11

• A divide and conquer algorithm.
• It divides the list into ‘n’ sublists (‘n’ being the size of the input). It merges two sublists together in a sorted manner. It then repeats the process recursively until there is one sorted sublist left.
• Similar to quick sort

Question 12

Discuss the time complexity of merge sort

Answer 12

• Time complexity: O(n log(n))
• Merge sort will divide the list into sublists at a log(n) complexity since it is half-ing the list every iteration. The merging of ‘n’ sublists items takes O(n) time, making the sorting complexity O(n * log(n))