Sorting
1
Sorting
Sorting is the most basic algorithm
Sorting is one of the most commonly used strategy to
deal with data.
Prune, deduplication, etc.
2
Types of Sorting
Comparison based sorting
Bubble sort, insertion sort, selection sort
Quick sort, merge sort, heap sort
Special sorting
Bucket sort
3
Bubble sort
Alway compare adjacent items if they are in the wrong order.
Best: O(n)
Average: O(n^2)
Worst: O(n^2)
https://www.youtube.com/embed/aXXWXz
5rF64?enablejsapi=1
4 . 1
Bubble sort
Alway compare adjacent items if they are in the wrong order.
public void bubbleSort(int[] nums) {
int n = nums.length; Best: O(n^2)
for (int i = 0; i < n; i++) { Average: O(n^2)
for (int j = 1; j < (n - i); j++) {
if (nums[j - 1] > nums[j]) { Worst: O(n^2)
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
}
}
}
4 . 2
Bubble sort
Alway compare adjacent items if they are in the wrong order.
public void bubbleSort(int[] nums) {
int n = nums.length; Best: O(n)
for (int i = 0; i < n; i++) { Average: O(n^2)
boolean swapped = false;
for (int j = 1; j < (n - i); j++) { Worst: O(n^2)
if (nums[j - 1] > nums[j]) {
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
swapped = true;
}
}
if (!swapped) return;
}
}
4 . 3
Insertion Sort
Placing poker cards, insert card to the right place (with swap).
Best: O(n)
Average: O(n^2)
Worst: O(n^2)
https://www.youtube.com/embed/DFG-
XuyPYUQ?enablejsapi=1
5 . 1
Insertion Sort
Placing poker cards, insert card to the right place (with swap).
public void insertSort(int[] nums){
int n = nums.length; Best: O(n)
for (int i = 1; i < n; i++) { Average: O(n^2)
for(int j = i ; j > 0 ; j--) {
if(nums[j] < nums[j-1]) { Worst: O(n^2)
int temp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = temp;
}
}
}
return input;
}
5 . 2
Insertion Sort
Placing poker cards, insert card to the right place (with swap).
public void insertSort(int[] nums){
int n = nums.length; Best: O(n)
for (int i = 1; i < n; i++) { Average: O(n^2)
int tmp = nums[i];
int j = i; Worst: O(n^2)
for (j = i ; j > 0 ; j--) {
if (tmp < nums[j-1]) {
nums[j] = nums[j-1];
} else {
break;
}
}
nums[j] = tmp;
}
return input;
}
5 . 3
Selection Sort
Select minimum for N times.
Best: O(n^2)
Average: O(n^2)
Worst: O(n^2)
https://www.youtube.com/embed/f8hXR_H
vybo?enablejsapi=1
6 . 1
Selection Sort
Select minimum for N times.
public void selectionSort(int[] nums){
int n = nums.length; Best: O(n^2)
for (int i = 0; i < nums.length - 1; i++) { Average: O(n^2)
int min = nums[i];
int minIdx = i; Worst: O(n^2)
for (int j = i+1; j < nums.length; j++) {
if (nums[j] < min) {
min = nums[j];
minIdx = j;
}
}
nums[minIdx] = nums[i];
nums[i] = min;
}
}
6 . 2
Merge Sort
Recursion. Divide and Conquer.
Best: O(nlogn)
Average: O(nlogn)
Worst: O(nlogn)
https://www.youtube.com/embed/es2T6KY
45cA?enablejsapi=1
7 . 1
Merge Sort
Recursion. Divide and Conquer.
public void mergeSort(int[] nums){
mergeSort(nums, 0, nums.length-1); Best: O(nlogn)
}
Average: O(nlogn)
public void mergeSort(int[] nums, int begin, int end) {
if (begin < end) { Worst: O(nlogn)
int mid = (begin + end) / 2;
mergeSort(nums, begin, mid);
mergeSort(nums, mid+1, end);
merge(nums, begin, mid, end);
}
}
public void merge(int[] nums,
int left, int leftEnd, int rightEnd);
7 . 2
QuickSort
Recursion. Divide and conquer. PIVOT.
Best: O(nlogn)
Average: O(nlogn)
Worst: O(n^2)
https://www.youtube.com/embed/aXXWXz
5rF64?enablejsapi=1
8 . 1
QuickSort
Recursion. Divide and conquer. PIVOT.
public void quicksort(int[] nums, int begin, int end) {
if (begin >= end) { Best: O(nlogn)
}
return;
Average: O(nlogn)
int pivotPostion = partition(nums, begin, end);
quicksort(nums, begin, pivotPostion - 1); Worst: O(n^2)
quicksort(nums, pivotPostion + 1, end);
}
8 . 2
QuickSort
Recursion. Divide and conquer. PIVOT.
public int partition(int[] nums, int begin, int end) {
int pivot = nums[begin]; Best: O(nlogn)
while (begin < end) {
while (begin < end && nums[end] >= pivot) { Average: O(nlogn)
}
end--;
Worst: O(n^2)
nums[begin] = nums[end];
while (begin < end && nums[begin] <= pivot) {
begin++;
}
nums[end] = nums[begin];
}
nums[begin] = pivot;
return begin;
}
8 . 3
Bucket Sort
When numbers to be sort are in some specific range, we
can count the times that each number in the range show
up.
Example:
Given range: [1-10],
Given array: [3, 5, 3, 2, 4, 1, 4, 9, 10],
=> Count: [1, 1, 2, 1, 1, 0, 0, 0, 1, 1]
=> Output: [1, 2, 3, 3, 4, 5, 9, 10], sorted
9
Sort Colors
Given an array with n objects colored red, white or blue, sort
them so that objects of the same color are adjacent, with the
colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color
red, white, and blue respectively.
10 . 1
Sort Colors
public void sortColors(int[] A) {
int[] num = {0, 0, 0};
for (int i = 0; i < A.length; i++) {
num[A[i]]++;
}
for (int i = 0; i < num[0]; i++)
A[i] = 0;
for (int i = num[0]; i < num[0]+num[1]; i++)
A[i] = 1;
for (int i = num[0]+num[1]; i < A.length; i++)
A[i] = 2;
}
10 . 2
Merge Intervals
Given a collection of intervals, merge all overlapping
intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
11 . 1
Merge Intervals
public List<Interval> merge(List<Interval> intervals) {
if (intervals.size() == 0)
return new ArrayList<Interval>();
Collections.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval a1, Interval a2) {
return a1.start - a2.start;
}
});
ArrayList<Interval> results = new ArrayList<Interval>();
Interval pre = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
if (intervals.get(i).start <= pre.end) {
pre.end = Math.max(intervals.get(i).end, pre.end);
} else {
results.add(new Interval(pre.start, pre.end));
pre = intervals.get(i);
}
}
results.add(pre);
return results;
}
11 . 2
Sort Algorithms
Best Average Worst
Bubble O(n) O(n^2) O(n^2)
Insertion O(n) O(n^2) O(n^2)
Selection O(n^2) O(n^2) O(n^2)
QuickSort O(nlogn) O(nlogn) O(n^2)
MergeSort O(nlogn) O(nlogn) O(nlogn)
12
Bonus: Insert Sort List
Sort a linked list using insertion sort.
13
Bonus: Insert Sort List
Sort a linked list using insertion sort.
public ListNode insertionSortList(ListNode head) {
if (head == null)
return head;
ListNode dummy = new ListNode(-1);
ListNode cur = head;
while (cur != null) {
ListNode pre = dummy;
while (pre.next != null && pre.next.val <= cur.val) {
pre = pre.next;
}
ListNode next = cur.next;
cur.next = pre.next;
pre.next = cur;
cur = next;
}
return dummy.next;
}
13
