Data operatons & searching and sorting algorithms

Explain The Operation And Performance Of Sorting And Search Algorithms By: J. Anusdika 1 By: J.Anusdika 11

Content • Introduction • What is sorting? • What is searching? • Type of sorting algorithms • Search algorithms • • • By: J. Anusdika 2 By: J.Anusdika 22

Introduction • Algorithm analysis should begin with a clear statement of the task to be performed. • This allows us both to check that the algorithm is correct and to ensure that the algorithms we are comparing perform the same task. • Although there are many ways that algorithms can be compared, we will focus on two that are of primary importance to many data processing algorithms: o Time complexity: how the number of steps required depends on the size of the input o Space complexity: how the amount of extra memory or storage required depends on the size of the input. By: J. Anusdika 3 By: J.Anusdika 33

Sorting • Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order. • The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. • Sorting is also used to represent data in more readable formats. • Following are some of the examples of sorting in real-life scenarios: § Telephone Directory − The telephone directory stores the telephone numbers of people sorted by their names, so that the names can be searched easily. § Dictionary − The dictionary stores words in an alphabetical order so that searching of any word becomes easy. By: J.Anusdika 44

Searching • To finding out whether a particular element is present in the list. • 2 methods: linear search, binary search • The method we use depends on how the elements of the list are organized o unordered list : linear search: simple, slow o an ordered list : binary search or linear search: complex, faster By: J.Anusdika 55

M3.4: Demonstrate the all available sort and search generation methods By: J.Anusdika 66

Type of Sorting Algorithms • Bucket sort • Bubble sort • Insertion sort • Selection sort • Heap sort • Merge sort By: J.Anusdika 77

Bubble Sort • Bubble sort is a simple and well-known sorting algorithm. • It is used in practice once in a blue moon and its main application is to make an introduction to the sorting algorithms. • Bubble sort is stable and adaptive. • Algorithm qCompare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them. qIf at least one swap has been done, repeat step 1. • By: J.Anusdika 88

• Example. Sort {5, 1, 3} using bubble sort. • • • Unsorted • 5 > 1, Swap • 5 > 3, Swap • • Sorted 5 1 3 5 1 3 5 31 1 3 5 By: J.Anusdika 99

Bucket Sort • Bucket sort it’s the perfect sorting algorithm for the sequence above. • We must know in advance that the integers are fairly well distributed over an interval. Then we can divide this interval in N equal sub-intervals. • We’ll put each number in its corresponding bucket. • Finally for every bucket that contains more than one number we’ll use some linear sorting algorithm. By: J.Anusdika 1010

• Example: • • 2 3 3 1 2 4 1 2 3 4 2 3 By: J.Anusdika 1111

Insertion Sort • This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. • An element which is to be 'inserted in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort. • The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). • By: J.Anusdika 1212

How Insertion Sort Algorithm Works? By: J.Anusdika 1313

Heap Sort Algorithm • heapsort is a comparison-based sorting algorithm. • Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. • The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. By: J.Anusdika 1414

Merge Sort • Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being Ο(n log n), it is one of the most respected algorithms. • Merge sort first divides the array into equal halves and then combines them in a sorted manner. By: J.Anusdika 1616

Linear Search • A linear search is the basic and simple search algorithm. • A linear search searches an element or value from an array till the desired element or value is not found and it searches in a sequence order. • It compares the element with all the other elements given in the list and if the element is matched it returns the value index else it return -1. • Linear Search is applied on the unsorted or unordered list when there are fewer elements in a list. By: J.Anusdika 1717

Example; Algorithms Linear Search ( Array A, Value x) Step 1: Set i to 1 Step 2: if i > n then go to step 7 Step 3: if A[i] = x then go to step 6 Step 4: Set i to i + 1 Step 5: Go to Step 2 Step 6: Print Element x Found at index i and go to step 8 Step 7: Print element not found Step 8: Exit By: J.Anusdika 1818

Binary Search • Binary Search is applied on the sorted array or list. • In binary search, we first compare the value with the elements in the middle position of the array. • If the value is matched, then we return the value. • If the value is less than the middle element, then it must lie in the lower half of the array and if it's greater than the element then it must lie in the upper half of the array. By: J.Anusdika 1919

Example With Implementation • To search an element 9 from the sorted array or list. • Code • function findIndex(values, target) { return binarySearch(values, target, 0, values.length - 1); }; function binarySearch(values, target, start, end) { if (start > end) { return -1; } var middle = Math.floor((start + end) / 2) , var value = values[middle]; if (value > target) { return binarySearch(values, target, start, middle-1); } if (value < target) { return binarySearch(values, target, middle+1, end); } return middle; //found! } findIndex([2, 4, 7, 9, 13, 15], 9); • By: J.Anusdika 2020

Tree Search • A Tree Search Only Works If The Data Fits Into A Tree Structure. • The Database Starts At A Root That Goes To A Few Items, Each Of Which Goes To A Few More Items And So On Until You Have A Tree. Binary search tree. Lookup operation • Search algorithm traverses the tree "in-depth", choosing appropriate way to go, following binary search tree property and compares value of each visited node with the one, we are looking for. Algorithm stops in two cases. qA node with necessary value is found qAlgorithm has no way to go By: J.Anusdika 2121

D3.7: Draw conclusions about which one or more of the above methods suitable for real world scenario By: J.Anusdika 2222

Conclusion • I can used merge sort and bubble sort for this scenario. • Selection sort said to be better than bubble sort. So, we used bubble sort. • Selection sort can used qFind the smallest element, and put it to the first position. qFind the next smallest element, and put it to the second position. qRepeat until all elements are in the right positions. • Bubble sort can Scan the array, swapping adjacent pair of elements if they are not in relative order. This bubbles up the largest element to the end. • By: J.Anusdika 2323

Data operatons & searching and sorting algorithms

More Related Content

What's hot

Similar to Data operatons & searching and sorting algorithms

Recently uploaded

Data operatons & searching and sorting algorithms

Editor's Notes