Loading
Searching and Sorting
carries111
Nov 20, 2015
Download
Map Outline
Searching and Sorting
Implementing Searching and Sorting Algorithms
Sequential Search
average/best/worst case analysis
Binary Search
O(logN)
Recursive Binary Search
Searching Objects
using .equals()
Comparable or Comparator must be implemented
similar to BS
Selection Sort
O(N^2)
using loop to put the min value one by one
Case Study: Implementing Merge Sort
basics
two sorted array=>single sorted array
Splitting and Merge Arrays
split array into two
int[] left = Arrays.copyOfRange(a, 0, a.length/2)
int[] right = Arrays.copyOfRange(a, a.length/2, a.length)
while array, thinking OUTOFBOUNDs
using if to eliminate this error
Recursive Merge Sort
each divided one can be considered as a new array need to be splitted
much better than selection sort
O(NlogN)
logN of split
N of element logN each time
Cost of Java Array Allocation
if computer is asked to auto-initialize an array of length n, then overall algo of merge sort will be O(N^2)
Program Complexity
basics
Complexity
empirical analysis
algorithm analysis
pseudocode
fixed time statement
runtime of a group of statement in sequ order
Empirical Analysis
nested loops
N^2
better algorithm
runtime increases by the algorithm's growth
Complexity Classes
Constant-time, O(1)
convert unit
Logarithmic, O(logN)
divide prob space in half repeatedly
Linear, O(N)
count, sum, average, max, or range of list nums
Log-linear, O(NlogN)
Excuting a logarithmic algo over elements of N
Quadratic, O(N^2)
nested loops
Cubic, O(N^3)
count nums in colinear trios of points
Exponential, O(2^N)
print the power set of a datasheet
In Java Class Libraries
List
indexOf
sequential
not a List
put it in the list
write by yourself
Binary Search
definition
sorted list
divide by half
Java-->Arrays
if(target.trim().length() == 0) {break}
Arrays.binarySearch
Java-->Lists
Collections.binarySearch
sorting
Array
Array.sort
Comparable interface implemented
quick sort
Arrays.sort + primitive data
merge sort
Arrays.sort/Collections.sort + obj
Shuffling
Collections.shuffle
Custom Ordering with Comparators
define public interface Comparator<T> {public int compare(T o1, T o2);}
String.CASE_INSENSITIVE_ORDER
Comparators
implement ordering by length
implement by Point
can be used in sort, BS, Collection.reverseOrder, ...
More Maps From User
Embed Code
Copy the code to embed this map into your article. The embeded map can even be zoomed in / out