Data calculatio. Algorithms by Charlotte.pptx

A brief tutorial

1. Algorithms By: Suhani Patni & Charlotte Sutcliffe

2. WHAT ARE ALGORITHMS ? A set of precise instructions to solve a problem or get something done. Also a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer. ALGORITHMS & COMPUTERS Programmers write algorithms to instruct the computer how to solve a problem or perform a task in the most efficient way possible.

3. SEARCHING ALGORITHMS Used to retrieve an item in a data structure. - There are two different types of ways to search a tree/graph: Breadth first and Depth first. LINEAR BINARY TREE/GRAPH - Best for small lists of items - Go through each item in the data set to find the desired item. - Only works if list is pre-sorted. - Finds the median then divides the list and determines if desired item is larger or smaller than the median and repeats until the item is found. - Trees are ways to illustrate sorted items, with nodes (pathway) . Root Parent Parent Child Child Child

4. BREADTH-FIRST VS DEPTH-FIRST BREADTH FIRST SEARCH Starts at root and goes layer by layer searching for the item. Moves from left to right through each layer. DEPTH FIRST SEARCH Starts at root and goes as far down on each branch before backtracking . Moves left to right through the branches. 5 9 6 2 3 4 1 BFS: 5, 9, 6, 2, 1, 4, 3 5 9 6 2 3 4 1 D FS: 5, 9, 1, 6, 2, 4, 3

5. SORTING ALGORITHMS QUICK SORT BUBBLE SORT INSERTION SORT SELECTION SORT MERGE SORT An algorithm that puts items in a list or array in order.

6. QUICK SORT Starts by picking a pivot (any value in the list) and then moving the other values left or right depending on if they’re smaller or larger than the pivot. A new pivot is chosen and the other the process repeats until all the items are in order. 9 6 3 7 2 11 5 3 2 5 6 9 7 11 2 7 11 3 5 6 9 2 3 5 6 7 9 11 Pivot Smaller Larger Pivot Pivot In many scenarios quicksort is the fastest and most efficient sorting algorithm, especially with short lists or arrays.

7. BUBBLE SORT Starts with the first two items in list and compare them. If the larger item is on the wrong side swap the two numbers and compare. The loop continues until all the items are sorted least to greatest. Ex: The contact list on your phone is sorted in alphabetical order using bubble sort. 7 6 4 3 SWAP First Pass 6 7 4 3 SWAP 6 4 7 3 SWAP 6 4 3 7 SWAP Second Pass 4 6 3 7 SWAP 4 3 6 7 SWAP 3 4 6 7 Final List

8. INSERTION SORT Start with any value in the list ( except the first value). Compare it to the value on its left and if the value on the left is larger swap the two. Continue to move the value left until meet with a value that is less than it or the beginning of the list. The process starts again with a different value and repeats until list is sorted. 8 3 5 2 9 3 < 8 3 8 5 2 9 5 < 8 & 5 > 3 3 5 8 2 9 2 < 3 2 3 5 8 9 Most efficient when the input list is already mostly sorted.

9. SELECTION SORT Find the minimum value in the list, then swap that item with the first item in the list. Then go to the next smallest number. Continue this process until the list is sorted least to greatest. Ex: In scenarios where you need to check all values selection sort is the best. 6 2 7 3 8 2 6 7 3 4 2 3 7 6 8 2 3 7 6 8 2 3 6 7 8 2 3 6 7 8

10. MERGE SORT 14 7 3 12 14 7 3 12 DIVIDE DIVIDE DIVIDE 7 14 3 12 LEAST GREATEST 3 7 12 14 Divide the list into sublists, each should only contain one element, repeatedly merge the list back together while sorting the sublists . Similar to a divide and conquer algorithm. Works very efficiently with large lists or arrays without taking up a lot of space. 7 14 3 12 Combine Combine

11. EFFICIENCY OF SORTING ALGORITHMS THE COMPLEXITY OF SORTING ALGORITHMS MEASURES THE RUNNING TIME OF A FUNCTION. THE CHOICE OF SORTING METHOD DEPENDS ON EFFICIENCY FOR DIFFERENT SITUATIONS. MOST IMPORTANT CONSIDERATIONS ARE: AMOUNT 0F TIME SPENT BY PROGRAMMER IN CODING DIFFERENT KINDS OF SORTING PROGRAMS. AMOUNT OF MACHINE TIME NECESSARY FOR RUNNING THE PROGRAM. THE AMOUNT OF MEMORY (STORAGE) NECESSARY FOR RUNNING THE PROGRAM.

12. ANY QUESTIONS? THANK YOU. #ARTEMIS2023