Algorithms, Part 1 Course from Princeton —Sorting and Week 3 assignment Collinear Points

Introduction

Algorithms, Part 1 is a solid course for IT or software engineers to learn algorithms which are provided by Princeton. Of course, we still have to take time to clarify the concepts after completing the class.

Sorting is fundamental algorithm for software engineering and it’s essential for the technical interviews. In this article, we will focus different sorting algorithms and implementations.

About this Series

This series aims to wrap up contents of Algorithms, Part 1.

• week 1: Union-find and Week 1 assignment Percolation
• week 2: Stack, Queue, and Week 2 Assignment Deques and Randomized Queues
• week 3: this article
• week 4: Binary Tree, Binary Heaps, and Week 4 Assignment 8 puzzle
• week 5: Hash table and Week 5 Assignment KD-Tree

Agenda

It includes the following topics in this article.

• Comparable and Comparator
• Selection sort
• Insertion sort
• Shell sort
• Merge sort
• Merge sort practical improvements
• Quick sort
• Quick sort practical improvements
• Dijkstra 3-way partitioning/3-way quick sort
• Week 3 Programming Assignment: Collinear points

Overview

• Compare-based sorting algorithm must use at least Log N! ~ N Log N compares in the worst-case
• Lower bound may not hold if the algorithm has information about - The initial order of the input - The distribution of key values - The description of the keys
• Stability means the order will still be correct after sorting by different properties

1. Comparable and Comparator

There are two ways to compare objects in Java.

Comparable interface

• When: for the custom object, it can implement Comparable interface
• How: implement the compareTo function

Comparator interface

• When: if we’re unable to customize the object, we still can use Comparator
• How: implement the compare function

2. Selection sort

Description

• In iteration i, find index min of the smallest remaining entry
• Swap a[i] and a[min] (compared-based sorting)

Proposition

• compare: (N — 1) + (N — 2) + ... + 1 + 0 ~ N^2
• exchange: N

Implementation in Java (from the official video)

Related LeetCode questions

• 75. Sort Colors (medium)

3. Insertion sort

Description

• In iteration i, swap a[i] with larger entry to its left

Proposition

• compare: ~ N^2 / 4
• exchange: ~ N^2 / 4

Implementation in Java (from the official video)

Related LeetCode questions

• 148. Sort List (medium)

4. Shell sort

Description

• Move entries more than one position at a time by h-sorting the array
• h-sorting: insertion sort, with stride length h

Proposition

• The worst-case number of compares used by shellsort with the 3x + 1 increments is N ^ 3/2

Implementation in Java (from the official video)

5. Merge sort

Description

• Given two sorted sub-arrays a[lo] to a[mid] and a[mid + 1] to a[hi], replace with sorted sub-array a[lo] to a[hi]

Basic plan

1. Divide array into two halves
2. Recursively sort each half
3. Merge two haves

Proposition

• If D[N] satisfies D[N] = 2D[N/2] + N for N > 1, with D(1) = 0, then D[N] = N log N
• Use extra space proportional to N
• Stable
• With duplicate keys, always between 1/2N Log N and N Log N compares

1. Top-down merge sort

• Visualization

• Implementation in Java (from the official video)

2. Bottom-up merge sort

• Implementation in Java (from the official video)

Related LeetCode questions

• 88. Merge Sorted Array

6. Merge sort practical improvements

1. Use insertion sort for small sub-arrays

cutoff to insertion sort for ~ 7 items

2. Stop if already sorted

helps for partially-ordered arrays

3. Eliminate the copy to the auxiliary array

7. Quick sort

Quick sort is an in-place sorting algorithm.

Basic plan

1.Shuffle the array

StdRandom.shuffle(a);

2. Partitioning

3. Sort each piece recursively

Proposition

• Best case: ~ N Log N
• Average case: ~ 1.39N Log N (39% more compares than merge sort but faster than merge sort in practice because of less data movement)
• Worst case: ~ 1/2 N ^ 2 - Is sorted or reverse sorted - Has many duplicates (even if randomized)
• Use less memory than the merge sort
• Not stable

1. Random shuffle

• Probabilistic guarantee against worst case
• Basis for math model that can be validated with experiments

2. Partitioning

• phase 1. repeat until i and j pointer cross - Scan i from left to right so long as (a[i] < a[lo]) - Scan j from right to left so long as (a[j] > a[lo]) - Exchange a[i] with a[j]
• phase 2. when pointers cross - Exchange a[lo] with a[j]

• Implementation in Java (from the official video)

3. Completed Quick sort

• Implementation in Java (from the official video)

8. Quick sort practical improvements

1. Use insertion sort for small sub-arrays

cutoff to insertion sort for ~ 70items

2. Median of sample

• Best choice of pivot item = median
• Estimate true median by taking median of sample
• Median-of-3 (random) items

9. Dijkstra 3-way partitioning/3-way quick sort

For performing good performance when having duplicated keys (~N Log N!), putting all items equal to the partitioning item in place.

• 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

Implementation in Java (from the official video)

Week 3 Programming Assignment: Collinear points

Given a set of n distinct points in the plane, find every (maximal) line segment that connects a subset of 4 or more of the points.

There are a few requirements.

1. Line segmentation with Brute force
2. Line segmentation with the sort-based solution
3. client program

Requirements in detail

Solutions

• BruteCollinearPoints.java

• FastCollinearPoints.java

• Point.java

Grades

References

• 10.5 斷言（Assertion）
• princeton algorithms part 1 第三周作业题
• Comparable 與 Comparator
• Merge Sort Algorithm
• [演算法] 希爾排序法(Shell Sort)
• 常見的排序演算法
• Stable Sorting

Summary

Thanks for your patient. I am Sean. I work as a software engineer.

This article is my note. Please feel free to give me advice if any mistakes. I am looking forward to your feedback.

• Subscribe me

• The Facebook page for articles

• The latest side project: Daily Learning

Related topics

How to use the two-way binding in Knout.js and ReactJS?

Learn how to use SignalR to build a chatroom application

My reflection of :

IT & Network: