basic data structures and algorithms questions

Heapsort and Mergesort maintain that complexity even in worst case scenarios, while Quicksort has worst case performance of O(n^2). The other three algorithms have a best and average runtime complexity of O(n log n). A common use is for re-sorting arrays that have had some small updates to their elements. It is also extremely good at sorting arrays that are already “almost” sorted. It is efficient at sorting extremely short arrays due to a very low constant factor in its complexity. It doesn’t need any extra buffer, so space complexity is O(1). The process is repeated on pairs of adjacent subarrays until we arrive at the starting array, but sorted.Ĭheck out the visualization of these sorting algorithms here: Insertion sort has an average and worst runtime of O(n^2), and a best runtime of O(n). Merging takes the smallest element between two adjacent subarrays and repeats that step until all elements are taken, resulting in a sorted subarray.

Once the subarrays reach trivial length, merging begins. Merge sort recursively halves the given array. The recursion is performed until we reach subarrays of 0-1 elements in length. After going through the whole array, we take all points on the left of the pivot and call quicksort on that subarray, and we do the same to all points on the right of the pivot. The moving is performed quickly by swapping that element with the first element after the pivot point, and then swapping the pivot point with the element after it. When we find one that is smaller, we move it to the left. We then compare it to each following element. Quicksort is performed by taking the first (leftmost) element of the array as a pivot point. This is repeated until we empty out the heap, resulting in the smallest element being in the first place, and the following elements being sequentially larger. After that, we take and remove the first element, restore the heap property, thus reducing the heap size by 1, after which we place the max element at the end of that memory. Once the heap is formed, it completely replaces the array. The heap is stored in the same memory in which the original array elements are. A binary max heap is a nearly complete binary tree in which each parent node is larger or equal to its children. It does this by taking an element, finding its correct position in the sorted array, and shifting all following elements by 1, leaving a space for the element to be inserted. Insertion sort takes elements of the array sequentially, and maintains a sorted subarray to the left of the current point.

Basic data structures and algorithms questions