"General"
set number "Show line numbers"
set linebreak "Break lines at word (requires Wrap lines)"
set showbreak=+++ "Wrap-broken line prefix"
set textwidth=100 "Line wrap (number of cols)"
set showmatch "Highlight matching brace"
set visualbell "Use visual bell (no beeping)"
set hlsearch "Highlight all search results"
set smartcase "Enable smart-case search"
set ignorecase "Always case-insensitive"
set incsearch "Searches for strings incrementally"
set autoindent "Auto-indent new lines"
set shiftwidth=4 "Number of auto-indent spaces"
set smartindent "Enable smart-indent"
set smarttab "Enable smart-tabs"
set softtabstop=4 "Number of spaces per Tab"
"Advanced"
set ruler "Show row and column ruler information"
set undolevels=1000 "Number of undo levels"
set backspace=indent,eol,start "Backspace behaviour"
Bubble is the most common algorithm to sort an array. It based on the idea of repeatedly comparing adjacent element and then swapping their value if exist in the wrong order
1 2 3 4 5 6 7 8
voidbubbleSort(vector<int> &nums){ for (int i = 0; i < nums.size(); ++i) { for (int j = i + 1; j < nums.size(); ++j) { if (nums[i] > nums[j]) swap(nums[i], nums[j]); } } }
Selection sort
The selection sort is based on finding the minimum or maximum in an unsorted array and putting it to a sorted array
1 2 3 4 5 6 7 8 9 10
voidselectionSort(vector<int> &nums){ for (int i = 0; i < nums.size(); ++i) { intmin = i; for (int j = i + 1; j < nums.size(); ++j) { if (nums[min] > nums[j]) min = j; } swap(nums[i], nums[min]); } }
Insertion sort
From left to right, find each element’s correct position
1 2 3 4 5 6 7 8 9 10 11 12 13
voidinsertSort(vector<int> &nums){ for (int i = 1; i < nums.size(); ++i) { int v = nums[i]; int j = i; while(j > 0) { nums[j] = nums[j - 1]; if (nums[j] <= v) break; --j; } nums[j] = v; } }
Merge sort
Merge sort is a divide-and-conquer algorithm based on repeatedly breaking down an array to two sub-array and then merge them
voidmerge(vector<int> &nums, int b, int e){ int m = (b + e) / 2; int q = m + 1, p = b; vector<int> v; for (int i = b; i <= e; ++i) { if (p > m) v.push_back(nums[q++]); elseif (q > e) v.push_back(nums[p++]); elseif (nums[q] > nums[p]) v.push_back(nums[p++]); else v.push_back(nums[q++]); }
for (auto val : v) nums[b++] = val; }
voidmergeSort(vector<int> &nums, int b, int e){ if (b >= e) return;
mergeSort(nums, b, (e + b) / 2); mergeSort(nums, (e + b) / 2 + 1, e); merge(nums, b, e); }
Quick sort
Quick sort is also a divide-and-conquer algorithm. But it reduces the space complexity and removes the use of auxiliary array that is used in merger sort One of the most important factors to influence performance is the pivot. I chose the pivot from the middle, front, and back of the array. Sometimes will improve performance
intpartion(vector<int> &nums, int b, int e){ int p = e; int m = (b + e) / 2; if (nums[b] > nums[m]) swap(nums[b], nums[m]); if (nums[b] > nums[e]) swap(nums[b], nums[e]); if (nums[m] > nums[e]) swap(nums[m], nums[e]);
int piv = nums[m]; swap(nums[e--], nums[m]); while (b < e) { while (b < e && nums[b] < piv) ++b; while (b < e && nums[e] >= piv) --e; if (b >= e) break;
swap(nums[b], nums[e]); } swap(nums[p], nums[b]);
return b; }
voidquickSort(vector<int> &nums, int b, int e){ if (b >= e) return;
int p = partion(nums, b, e); quickSort(nums, b, p - 1); quickSort(nums, p + 1, e); }
Heap sort
Heap sort uses a structure called heap to sort the array. Heap is a complete binary tree. left sub-tree index = 2 * root index + 1 right sub-tree index = 2 * root index + 2
voidshellSort(vector<int> &v){ int h = 0; while (h < v.size() / 3) h = h * 3 + 1; while (h >= 1) { for (int j = h; j < v.size(); ++j) { for (int i = j; i >= h && v[i] < v[i - h]; i -= h) swap(v[i], v[i - h]); } h /= 3; } }
bottom-up sort
bottom-up sort is a down-top method based on merge sort.
voidquickSort(vector<int> &nums, int b, int e){ if (b >= e) return;
// if element too little, insertSort more effective than quickSort if (e - b < QS_MIN_LENGTH) insertSort(nums, b, e);
// meduim of three can get more effetive pivot int m = (b + e) / 2; if (nums[b] > nums[m]) swap(nums[b], nums[m]); if (nums[b] > nums[e]) swap(nums[b], nums[e]); if (nums[m] > nums[e]) swap(nums[m], nums[e]);
int pivot = nums[m]; // skip elements equal pivot int lt = b + 1, eq = lt, gt = e - 1; while (eq <= gt) { if (nums[eq] < pivot) swap(nums[lt++], nums[eq++]); elseif (nums[eq] > pivot) swap(nums[eq], nums[gt--]); else eq++; }
