Sorting and searching procedure for computer science and technology

Sorting and Searching Sorting and Searching Pepper

Common Collection and Array Common Collection and Array Actions Actions  Sort in a certain order ◦ Max ◦ Min  Shuffle  Search ◦ Sequential (contains) ◦ Binary Search –  assumes sort, faster

Static Method Tools Classes Static Method Tools Classes  Arrays ◦ binarySearch (array, value) ◦ sort(array)  Collections ◦ binarySearch (list, value) ◦ shuffle(list) ◦ sort(list) ◦ max(list) ◦ min(list)

Sorting – need order Sorting – need order  Comparable interface ◦ Only one order – chosen as natural order ◦ Implemented inside order  Implements Comparable<T> ◦ int compareTo (SelfType o)  int compareTo (Object o)  Compare this item to the parm ◦ Used automatically by Collections sort ◦ Used automatically by TreeMap and TreeSet

Sorting – Custom Order Sorting – Custom Order  Comparator ◦ Custom order ◦ Independent of the object's definition  Uses 2 objects and compares them  int compare (Selftype s1, Selftype s2)  No this  just 2 input objects to compare ◦ Implements comparator<T>  Outside the class being sorted ◦ Why  Collections sort can use it  TreeSet can use it  TreeMap can use it

The Comparator Interface The Comparator Interface  Syntax to implement ◦ public class lengthCom implements Comparator<String>{  public int compare(String s1, String s2){  Return s1.length() = s2.length(); }}  Sorted list: dog, cat, them, bunnies

How to use the Comparator How to use the Comparator  Collections sort can take in a comparator ◦ Passed to methods as an extra parm ◦ Object passed into Collections.sort ◦ Ex: Collections.sort(myarray, new myArraySorter())  Use ◦ Arrays.sort(stringArray, new lengthCom()); ◦ Collections.sort(stringList, new lengthCom()); ◦ new TreeSet<String> (new lengthCom());

Stock Comparators Stock Comparators  String ◦ CASE_INSENSITIVE_ORDER  Collections ◦ reverseOrder() – returns comparator ◦ reverseOrder(comparator object)  Returns opposite order of comparator  Use ◦ Collections.sort(myStringList, CASE_INSENSITIVE_ORDER) ◦ Collections.sort(myStringList, Collections.reverseOrder(new lengthCom()))

Searching and Sorting Searching and Sorting  Complexity measuring  Search algorithms  Sort algorithms

Complexity Measurements Complexity Measurements  Empirical – log start and end times to run ◦ Over different data sets  Algorithm Analysis ◦ Assumed same time span (though not true):  Variable declaration and assignment  Evaluating mathematical and logical expressions  Access or modify an array element  Non-looping method call

How many units – worst case: How many units – worst case:  Sample code – find the largest value var M = A[ 0 ]; //lookup 1, assign 1 for ( var i = 0; i < n; i++) { // i = o 1; test 1 // retest 1; i++ 1; if ( A[ i ] >= M ) { // test 1 ; lookup 1 M = A[ i ];}} // lookup 1, assign 1 4 + 2n + 4n F(n) = 4 + 2n + 4n = 4 + 6n Fastest growing term with no constant: F(n) = n (n is your array size) http://discrete.gr/complexity/

Practice with asymptote finding – Practice with asymptote finding – no constant no constant  f( n ) = n2 + 3n + 112 gives f( n ) = n2  f( n ) = n + sqrt(n) gives f( n ) = n  F(n) = 2n + 12 gives f(n) = 2n  F(n) = 3n + 2n gives f(n) = 3n  F(n) = 3n + 2n gives f(n) = 3n ◦ Just test with large numbers

Practice with asymptote finding Practice with asymptote finding (dropping constant) (dropping constant)  f( n ) = 5n + 12 gives f( n ) = n. ◦ Single loop will be n; ◦ called linear  f( n ) = 109 gives f( n ) = 1. ◦ Need a constant 1 to show not 0 ◦ Means no repetition ◦ Constant number of instructions

Determining f(n) for loops Determining f(n) for loops for (i = 0; i < n; i++) for (j = 0; j < n; j++) for (k = 0; k < n; k++) System.out.println(a[i][j] [k]);}}} F(n) = n3

Big O Notation – Growth Rate Big O Notation – Growth Rate  F(n) = n3 gives Big O Notation of O( n3 )  Which will be slower than O(n)  Which will be slower than O(1)

Searching Searching  Sequential : ◦ Go through every item once to find the item ◦ Measure worst case ◦ 0(N)

Binary Search Binary Search  First Sorted  Dictionary type search – keep looking higher or lower  Takes 0 seconds, but cannot be O(1) because it has a loop  As input grows, number of times to divide min-max range grows as: ◦ 2repetitions is approximately the Number of elements in the array ◦ So, repetitions = log2N - O(log2 N)

Binary Search code Binary Search code public static int findTargetBinary(int[] arr, int target){ int min = 0; int max = arr.length - 1; while( min <= max) { int mid = (max + min) / 2; if (arr[mid] == target){ return mid; } else if (arr[mid] < target) { min = mid + 1; } else { max = mid - 1; } } return -1; }

Selection Sort Selection Sort  Find the smallest value's index  Place the smallest value in the beginning via swap  Repeat for the next smallest value  Continue until there is no larger value  Go through almost every item in the array for as many items as you have in the array ◦ Complexity: O (N2 )

Bubble Sort Bubble Sort  Initial algorithm Check every member of the array against the value after it; if they are out of order swap them. As long as there is at least one pair of elements swapped and we haven’t gone through the array n times: If the data is in order, it can be as efficient as O(n) or as bad as O(n2 )

Merge Sort Merge Sort  Two sorted subarrays can quickly be merged into a sorted array.  Divide the array in half and sort the halves.  Merge the halves.  Picture: http://www.java2novice.com/java-sorting- algorithms/merge-sort/  Video: http://math.hws.edu/TMCM/java/xSortLab

Merge Sort Complexity Merge Sort Complexity  Split array in half repeatedly until each subarray contains 1 element. ◦ 2repetitions is approximately the Number of elements in the array ◦ So, repetitions of division= log2N ◦ O(log N)  At each step, do a merge, go through each element once ◦ O(N)  Together: O (N log2 N)

Comparison speed Comparison speed  Sequential Search - O(N)  Binary Search - O(log2 N)  Selection Sort - O(N2)  Bubble Sort - O(N2)  Merge Sort - O (N log2 N)  https://www.ics.uci.edu/~eppstein/161/960116.html

Summary Summary  Relative complexity – O Notation  Arrays and Collections class  Different Search methods ◦ Sequential Search – keep looking one by one ◦ Binary Search – dictionary type split search  Different Sort methods ◦ Selection Sort – look through all to find smallest and put it at the beginning – repeatedly ◦ Bubble Sort – continual swapping pairs – repeatedly ◦ Merge Sort - continually divide and sort then merge

Sorting and searching procedure for computer science and technology

More Related Content

Similar to Sorting and searching procedure for computer science and technology

Recently uploaded

Sorting and searching procedure for computer science and technology