• Register
300 points
8 4 2

1. How Bubble Sort works?

Bubble Sort is based on the idea of repeatedly comparing pairs of adjacent elements and then swapping their positions if they are in the wrong order. Bubble sort is a stable, in-place sort algorithm.

How it works:

  • In an unsorted array of n elements, start with the first two elements and sort them in ascending order. (Compare the element to check which one is greater).
  • Compare the second and third element to check which one is greater, and sort them in ascending order.
  • Compare the third and fourth element to check which one is greater, and sort them in ascending order.
  • ...
  • Repeat steps 1–n until no more swaps are required.

Complexity Analysis

Time: O(n^2)

Space: O(1)

Bubble sort has a worst-case and average complexity of O(n2), where n is the number of items being sorted. When the list is already sorted (best-case), the complexity of bubble sort is only O(n). The space complexity for Bubble Sort is O(1), because only single additional memory space is required (for temp swap element).

 

2. Insert an item in a sorted linked list maintaining order

The add() method below walks down the list until it finds the appropriate position. Then, it splices in the new node and updates the start, prev, and curr pointers where applicable.

Note that the reverse operation, namely removing elements, doesn't need to change, because you are simply throwing things away which would not change any order in the list.

Implementation

public void add(T x) {
    Node newNode = new Node();
    newNode.info = x;

    // case: start is null; just assign start to the new node and return
    if (start == null) {
        start = newNode;
        curr = start;
        // prev is null, hence not formally assigned here
        return;
    }

    // case: new node to be inserted comes before the current start;
    //       in this case, point the new node to start, update pointers, and return
    if (x.compareTo(start.info) < 0) {
        newNode.link = start;
        start = newNode;
        curr = start;
        // again we leave prev undefined, as it is null
        return;
    }

    // otherwise walk down the list until reaching either the end of the list
    // or the first position whose element is greater than the node to be
    // inserted; then insert the node and update the pointers
    prev = start;
    curr = start;
    while (curr != null && x.compareTo(curr.info) >= 0) {
        prev = curr;
        curr = curr.link;
    }

    // splice in the new node and update the curr pointer (prev already correct)
    newNode.link = prev.link;
    prev.link = newNode;
    curr = newNode;
}

 

3. What are the key advantages of Insertion Sort, Quicksort, Heapsort and Mergesort? Discuss best, average, and worst case time and memory complexity.

Insertion sort has an average and worst runtime of O(n^2), and a best runtime of O(n). It doesn’t need any extra buffer, so space complexity is O(1). It is efficient at sorting extremely short arrays due to a very low constant factor in its complexity. It is also extremely good at sorting arrays that are already “almost” sorted. A common use is for re-sorting arrays that have had some small updates to their elements.

The other three algorithms have a best and average runtime complexity of O(n log n). Heapsort and Mergesort maintain that complexity even in worst case scenarios, while Quicksort has worst case performance of O(n^2).

Quicksort is sensitive to the data provided. Without usage of random pivots, it uses O(n^2) time for sorting a full sorted array. But by swapping random unsorted elements with the first element, and sorting afterwards, the algorithm becomes less sensitive to data would otherwise cause worst-case behavior (e.g. already sorted arrays). Even though it doesn’t have lower complexity than Heapsort or Merge sort, it has a very low constant factor to its execution speed, which generally gives it a speed advantage when working with lots of random data.

Heapsort has reliable time complexity and doesn’t require any extra buffer space. As a result, it is useful in software that requires reliable speed over optimal average runtime, and/or has limited memory to operate with the data. Thus, systems with real time requirements and memory constraints benefit the most from this algorithm.

Merge sort has a much smaller constant factor than Heapsort, but requires O(n) buffer space to store intermediate data, which is very expensive. Its main selling point is that it is stable, as compared to Heapsort which isn’t. In addition, its implementation is very parallelizable.

4. Sort a stack using recursion

Problem

Note we can’t use another stack or queue.

Answer

The idea of the solution is to hold all values in system stack unitll the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order.

Complexity Analysis

Time: O(n^2)

Space: O(n)

Implementation

void sort(stack s) {
    if (!IsEmpty(s)) {
        int x = Pop(s);
        sort(s);
        insert(s, x);
    }
}

void insert(stack s, int x) {
    if (!IsEmpty(s)) {  
        int y = Top(s);
        if (x < y) {
            Pop(s);
            insert(s, x);
            Push(s, y);
        } else {
            Push(s, x);
        }
    } else {
        Push(s, x); 
    }
}

5. What are Divide and Conquer algorithms? Describe how they work. Can you give any common examples of the types of problems where this approach might be used?

Divide and Conquer algorithms are a paradigm for solving problems that involve several basic steps. First, we divide the problem into smaller pieces and work to solve each of them independently. Once we’ve solved all of the pieces, we take all of the resulting smaller solutions and combine them into a single integrated comprehensive solution.

This process can be performed recursively; that is, each “sub problem” can itself be subdivided into even smaller parts if necessary.. This recursive division of the problem is performed until each individual problem is small enough to become relatively trivial to solve.

Some common examples of problems that lend themselves well to this approach are binary search, sorting algorithms (e.g., Merge Sort, Quicksort), optimization of computationally complex mathematical operations (Exponentiation, FFT, Strassen’s algorithm), and others.

 

6. When is quicksort better than mergesort?

Problem
They're both O(n log n) and yet most people use Quicksort instead of Mergesort. Why is that?

Answer

  • Quicksort has O(n2) worst-case runtime and O(n log n) average case runtime. However, it’s superior to merge sort in many scenarios because many factors influence an algorithm’s runtime, and, when taking them all together, quicksort wins out.
  • Quicksort in particular requires little additional space (it's in-place and MergeSort requires extra memory linear to number of elements to be sorted) and exhibits good cache locality (does half as many reads as the other algorithms), and this makes it faster than merge sort in many cases. In addition, it’s very easy to avoid quicksort’s worst-case run time of O(n2) almost entirely by using an appropriate choice of the pivot – such as picking it at random (this is an excellent strategy).

The average case performance for quicksort is faster than mergesort. But this is only true if you are assuming constant time to access any piece of memory on demand. In RAM this assumption is generally not too bad (it is not always true because of caches, but it is not too bad). However if your data structure is big enough to live on disk, then quicksort gets killed by the fact that your average disk does something like 200 random seeks per second.

if data has to be sorted on disk, you really, really want to use some variation of mergesort.

 

 

Sources Used

www.fullstack.cafe

soshace.com

toptal.com

300 points
8 4 2