Nothing special here. It’s just a blog post for summarising my algorithm learning course. Probably this was taught in the University but I don’t remember anything, I have no idea about its definition and applications until I take this course. Part 1 here Binary Heap & Heapsort Summary - Part 1 - Binary Heap

The Idea

Heapsort has two phases: build a max-heap from the array, then repeatedly remove the maximum to fill the array from the back. We use the array S O R T E X A M P L E (N = 11) as the example.

• Start with array of keys in arbitrary order

• Create a max-heap with all N keys

• Repeatedly remove the maximum key (in place) to create a sorted array

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Probably this was taught in the University but I don’t remember anything, I have no idea about its definition and applications until I take this course.

Heap-ordered Binary Tree

• Each node represents a key
• Parent’s key is not smaller than children’s keys

Array Representation

Taking the tree above in level order gives the array below. Index 0 is left unused so that the parent/child arithmetic stays simple:

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although this was already taught in the University, I remember nothing about it because I haven’t touched it for the long time.

• Part 1 - Basic Implementation
• Part 2 - Selection Problems
• Part 3 - 3-way Partitioning

Quick Sort - Duplicate Keys Problem

• Quick Sort goes quadratic unless partitioning stops on equal keys!
• ~½N² compares when all keys equal.
• B A A B A B B B C C C
• A A A A A A A A A A A
• Solve by using 3-way partitioning

3-way Partitioning

Partition array into 3 parts so that:

• Entries between lt and gt equal to partition item v
• No larger entries to left of lt
• No smaller entries to right of gt

While scanning with pointer i, the array is kept in these four regions:

• Let v be partitioning item a[lo]
• Scan i from left to right.
  • (a[i] < v): exchange a[lt] with a[i]; increment both lt and i
  • (a[i] > v): exchange a[gt] with a[i]; decrement gt
  • (a[i] == v): increment i

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although this was already taught in the University, I didn’t even know that it can be used for Selection Problem

• Part 1 - Basic Implementation
• Part 2 - Selection Problems
• Part 3 - 3-way Partitioning

Selection Problem

Given an array of N items, find a k^th smallest item. For example, an array A = [5, 2, 9, 4, 10, 7], the 3rd smallest item is 5, the 2nd smallest item is 4 and the smallest item is 2

The idea

• Based on Quick Sort
• Partition the array so that
  • Entry a[j] is in place.
  • No larger entry to the left of j
  • No smaller entry to the right of j
• Repeat in one sub-array, depending on j, finished when j equals k

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although this was already taught in the University, I remember nothing about it because I haven’t touched it for the long time.

• Part 1 - Basic Implementation
• Part 2 - Selection Problems
• Part 3 - 3-way Partitioning

Quick Sort

The Idea

• Shuffle the array.
• Select one item, can be the first item or last item as the pivot (the partitioned item).
• Partition the array into 2 parts, so that
  • The pivot entry is in the right place
  • No larger entry to the left of the pivot item
  • No smaller entry to the right of pivot item
• Sort each piece recursively.

After one partitioning step, the array is arranged around the pivot like this:

The pivot is now in its correct final spot, so we only need to recursively apply the same idea to the left and right sub-arrays:

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Here are some questions related to merge sort.

Merging with smaller auxiliary array

Question

Suppose that the subarray a[0] to a[n-1] is sorted and the subarray a[n] to a[2*n-1] is sorted. How can you merge the two subarrays so that a[0] to a[2*n-1] is sorted using an auxiliary array of length n (instead of 2n)?

Answer

Instead of copying the whole array into the auxiliary array, copy only the left half to that auxiliary array (a[0] to a[n-1]). At this time, the first half of the original array is free to overwrite any value. Apply merge sort and write the result back to the original array, from the first position. You will always have enough space in the original array to do that.

Counting inversions

Question

An inversion in an array a[] is a pair of entries a[i] and a[j] such that i<j but a[i]>a[j]. Given an array, design a linearithmic algorithm to count the number of inversions.

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although this was already taught in the University, it’s still good to summarise here

Merge Sort

• Divide array into two halves.
• Sort each half.
  • For each half, continue dividing into 2 halves and do merge sort.
• Merge two halves.

Here is the sample implementation from the Coursera course. Actually, I’m more familiar with the while version.

public class Merge {
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }
}

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although some of them were already taught in the University, it’s still good to summarise here

1. Selection Sort

• In iteration i, find index min of smallest remaining entry.
• Swap a[i] and a[min]

function selectionSort(a: number[]): void {
  const n = a.length;
  for (let i = 0; i < n; i++) {

    let min: number = i;
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[min]) {
        min = j;
      }
    }

    swap(a, i, min); // swap the 2 items
  }
}

Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although this was already taught in the University, it’s still good to summarise here

1. Stacks

Last In First Out

Linked-list Implementation

Maintain a pointer to the first item of the linked-list. Add or remove are simply to update that pointer.

class Node {
  item: string;
  next: Node;

  constructor(item: string, next: Node) {
    this.item = item;
    this.next = next;
  }
}

class Stack {
  first: Node;

  push = (item: string): void => {
    const oldFirst = this.first;
    this.first = new Node(item, oldFirst);
  }

  pop = (): string => {
    const item = this.first.item;
    this.first = this.first.next;
    return item;
  }
}

So, my friend gave me this exercise and asked me to solve it. Sometimes it’s fun to solve algorithm problem… sometimes…

Given an array A of n integer numbers, find all the (i,j) pairs such that A[i] + A[i+1] + A[i+2] + … + A[j] = 6. For example, A = [1, 5, 4, -2, 4, 8, 7, 9, 0], these pairs are valid i,j (0,1) and (2,4) because sum(A[0->1])=6 and sum(A[2->4])=6

Of course, the worst solution is to perform n² operations. For each number in A, do another loop inside that to find the sub-sequence having the sum = 6.

Surely there should be a better solution. And here is the O(n) solution.