algos

Question 1

Bubble Sort

Answer 1

Compares an element to its neighbor, if the element is larger that its neighbor, they swap places. The largest elements “bubble up” to the end with each pass of the loop. Complexity: Time: O(n²), Space: O(1)

Question 2

Selection Sort

Answer 2

Complexity: Time: O(n²), Space: O(n)

Compares an element against all the elements of the array until it finds the smallest, then they swap places. Small elements get pushed to the beginning with each pass of the loop.

Question 3

Insertion Sort

Answer 3

Complexity: Time: O(n²), Space: O(n)

Iterate over items 2 to n in the list, inserting each in the correct place in the left sublist

Question 4

Quick Sort

Answer 4

Quick sort is a divide and conquer algorithm. Quick sort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quick sort can then recursively sort the sub-arrays.

Quick sort’s steps:

Pick an element, called a pivot, from the array.

Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Question 5

Heap Sort

Answer 5

Complexity: O(n log n)

In computer science, heap sort is a comparison-based sorting algorithm. Heap sort can be thought of as an improved selection sort.

Heap sort’s steps:

Divides its input into a sorted and an unsorted region

Iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

The improvement on selection sort consists of the use of a heap data structure rather than a linear-time search to find the maximum.

Question 6

Merge Sort

Answer 6

Complexity: O(n log n)

Merge Sort is a divide and conquer algorithm that is an efficient, general-purpose, comparison-based sorting algorithm.

Merge sort’s steps:

Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.