Understanding Algorithms and Sorting Methods
Algorithms are precise instructions used to solve problems efficiently, especially in computer operations. Searching algorithms like tree and graph search are essential, while sorting algorithms such as quick sort and bubble sort help organize data effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Algorithms By: Suhani Patni & Charlotte Sutcliffe
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.
SEARCHING ALGORITHMS Used to retrieve an item in a data structure. TREE/GRAPH LINEAR - Trees are ways to illustrate sorted items, with nodes (pathway). BINARY - 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. Root Parent Parent Child Child Child - There are two different types of ways to search a tree/graph: Breadth first and Depth first.
BREADTH-FIRST VS DEPTH-FIRST BREADTH FIRST SEARCH DEPTH FIRST SEARCH Starts at root and goes as far down on each backtracking. Moves left to right through the branches. Starts at root and goes layer by layer searching for the item. Moves from left to right through each layer. branch before 5 5 9 2 9 2 6 6 1 1 4 3 4 3 DFS: 5, 9, 1, 6, 2, 4, 3 BFS: 5, 9, 6, 2, 1, 4, 3
SORTING ALGORITHMS An algorithm that puts items in a list or array in order. QUICK SORT BUBBLE SORT INSERTION SORT SELECTION SORT MERGE SORT
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. In many scenarios quicksort is the fastest and most efficient sorting algorithm, especially with short lists or arrays. 9 6 3 7 2 11 5 Smaller Larger Pivot 3 2 5 6 9 7 11 Pivot Pivot 2 3 5 6 7 9 11 2 3 5 6 7 9 11
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. First Pass Second Pass Final List 7 6 4 3 6 4 3 7 3 4 6 7 SWAP SWAP 6 7 4 3 4 6 3 7 SWAP SWAP 6 4 7 3 4 3 6 7 SWAP SWAP
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. Most efficient when the input list is already mostly sorted. 8 3 5 2 9 3 5 8 2 9 3 < 8 2 < 3 3 8 5 2 9 2 3 5 8 9 5 < 8 & 5 > 3
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 3 7 6 8 2 6 7 3 4 2 3 6 7 8 2 3 7 6 8 2 3 6 7 8
MERGE SORT 14 7 3 12 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. DIVIDE 14 7 3 12 DIVIDE DIVIDE Works very efficiently with large lists or arrays without taking up a lot of space. 7 14 3 12 Combine Combine 3 12 7 14 3 7 12 14 LEAST GREATEST
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.
ANY QUESTIONS? THANK YOU. #ARTEMIS2023
