How to Ace the Job Interview? - Sort Algorithms

Posted by Tariq Abughofa on September 25, 2019 · 5 mins read #interview

Sorting algorithms are used to apply a specific order according by a comparison operator on a list. The list doesn’t have to contain numbers. It can have strings or objects as long as there is a defined comparison criteria. For example, sorting employees by salary or by hiring date.

In this article, I will explain the famous algorithms and show their complexity. For simplicity we assume that all the items are positive numbers so that we can compare using the arithmetic operators >, <, and = and that we need an ascending order.

Selection Sort

This algorithm sorts the list by finding the smallest item in the unordered part of the list and put it before that part. This way the algorithm divide the list into two parts: one that is ordered at the beginning and one that is not at the end. It starts with the whole list unordered and keep adding elements to the ordered part until the whole list is ordered.

function selectionSort(list):
    n = length(list)
    for (i = 0; i < n-1; i++):
        min_idx = i;
        for (j = i+1; j < n; j++):
            if list[j] < list[min_idx]:
                min_idx = j;
        swap(list, min_idx, i);

The swap algorithm will be something like this:

function swap(list, i, j):
    temp = list[i];
    list[i] = list[j];
    list[j] = temp;

Complexity:

  • worst-case: O(n2) comparisons + O(n) swaps.
  • best-case: O(n2) comparisons + O(n) swaps.
  • Average: O(n2) comparisons + O(n) swaps.

Bubble Sort

It’s a simple algorithm that repeatedly swap adjacent items in the list if they are in the wrong order:

function bubleSort():
    n = length(list);
    for (i = 0; i < n-1; i++):
        for (j = 0; j < n-i-1; j++):
            if (arr[j] > arr[j+1]):
                swap(list, j, j+1);

Complexity:

  • worst-case: O(n2) comparisons + O(n2) swaps.
  • best-case: O(n) comparisons + O(1) swaps.
  • Average: O(n2) comparisons + O(n2) swaps.

Insertion Sort

This algorithm goes through the list and put each item in it’s place in the sorted part in the beginning. It works exactly the way we sort a hand of cards.

function insertionSort(list):
    n = length(list);
    for (i = 1; i < n; i++):
        item = list[i];
        j = i - 1;
        while (j >= 0 && list[j] > item):
            swap(list, j, j+1);
            j = j - 1;

Complexity:

  • worst-case: O(n2) comparisons + O(n2) swaps.
  • best-case: O(n) comparisons + O(1) swaps.
  • Average: O(n2) comparisons + O(n2) swaps.

Merge Sort

Merge sort is a Divide-and-Conquer algorithm. It divide the list into two halves, call itself on each half and then merge the tow sorted halves.

function mergeSort(list):
    if (length(list) <= 1):
        return list
    middle = length(list) / 2;
    left = slice(list, 0, middle)
    right = slice(list, middle, length(list))
    return merge(mergeSort(left), mergeSor(right))
} 

The slice function returns a part of the list passed as the first argument. That part starts at an index specified by the first argument (inclusive) and ends at an index specified by the second argument (exclusive). The second part of the algorithm is the merge function which takes two lists and merges them sorting the result in the process. It looks like this:

function merge(left, right):
    output = []
    i = 0
    j = 0
    while (i < length(left) && j < length(right)):
        if (left[i] < right[j]):
            push(output, left[i]
            i += 1
        else
            push(output, right[j]
            j += 1
   return output

The push function inserts an element to the end of the list.

Complexity:

  • worst-case: O(n log n).
  • best-case: O(n log n).
  • Average: O(n log n).

Quick Sort

Same as in Merge Sort, Quick Sort follows a Divide-and-Conquer strategy. For this algorithm you have to choose an element from the array as a pivot. There are some different strategies to do so. You can choose the first element (implemented here), choose the last element, or choose a random element.

function quickSort(list):
    if (length(list) == 0)
        return list;

    left = []
    right = []
    pivot = list[0];

    for (i = 1; i < length(list); i++):
        if (array[i] < pivot)
            push(left, list[i])
        else
            push(right, list[i])

    return quicksort(left) + pivot + quicksort(right)

Complexity:

  • worst-case: O(n2).
  • best-case: O(n log n).
  • Average: O(n log n).

Card image cap
How to Ace the Job interview? - Search Algorithms

Search algorithms are designed to check or retrieve an element from a data structure. The...

Card image cap
The "FooBar" Interview Question

I was asked this question at the interview that got me my first job and...