Algorithms in Computing: Searching, Sorting, and Merging Examples
Understanding algorithms in computing is crucial for efficient problem-solving. This content delves into examples of algorithms including searching for the highest card, finding the maximum and minimum cards, and sorting a deck of cards. Through step-by-step explanations, you will grasp the concepts of algorithm design in computing.
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
15-110: Principles of Computing Lecture 2: Examples of Algorithms August 02, 2022 Mohammad Hammoud and Eduardo Feo Flushing Carnegie Mellon University in Qatar
Today Last session: What are algorithms? Today s session: Examples of algorithms: searching, sorting, and merging Announcement: Quiz I will take place on Thursday, August 4 during the lab session All the material in this and past lectures are included
Searching Suppose you are holding a set of cards in your hand, numbered 1 to 100, but they are not sorted How can you find the highest card in this set? 1. Check if the first card is 100: a. If yes: halt (the card is found) b. If no: remove that card and go back to step 1 What if you are given a subset of those 100 cards (say, 80) and asked to find the highest card; how will you proceed?
Finding Max 1. Take the first card, if any (this is the highest card so far) 2. Take the next card, if any 3. Check if it is greater than the highest card so far a. If yes: a. Make the current card as the highest card so far b. Go back to step 2 b. If no: a. Discard the current card b. Go back to step 2 When there are no more cards to take in step 2, the highest card so far will be the highest (or the maximum) card in the deck
Finding Min How can you find the lowest (or minimum) card?
Sorting Let us assume you have the same set of cards, but now you need to put them in order (i.e., you need to sort them) If you have ALL the cards, you know exactly what will be the first card, the second card, the third card, etc., In this case, you can find the card with number 1 and place it on a new pile, then the card with number 2 and place it on the pile, and so on Do you know how to find a card with a specific number? Yes, through searching!
Sorting The sequence of steps could be something like: 1. Check if the first card is 1: a. If yes: put the card at the end of the new pile b. If no: place the card at the end of the deck. Go back to step 1 2. Check if the first card is 2: a. If yes: put the card at the end of the new pile b. If no: place the card at the end of the deck. Go back to step 2 3. Check if the first card is 3: a. If yes: put the card at the end of the new pile b. If no: place the card at the end of the deck. Go back to step 3 ... Very long and boring sequence of steps!
Sorting There is a great deal of repeated steps, with only one thing changing, that is, the number we are searching for As such, we can abbreviate the sequence of steps as: 1. For all numbers from 1 to 100, repeat the following steps: a. Check if the first card has that number: i. If yes: put the card at the end of the new pile ii. If no: place the card at the end of the deck. Go back to step a. How to sort the cards in the reverse order? Simply, change in step 1 from 1 to 100 to "from 100 to 1
Sorting What if not all the cards are there? If you do not know the numbers, it is impossible to tell what is going to be the first card, the second card, etc., How would you sort the cards then? 1. While the unsorted pile is not empty: a. Find the min card in it (we know how to do this!) b. Remove the card and put it at the end of the new pile Can you do better?
Sorting You can sort cards by using three piles: unsorted, sorted, and temp You can then define the steps of a sorting algorithm roughly as follows: 1. Place all cards in the unsorted pile 2. As long as there are cards in the unsorted pile: a. Take a card from the unsorted pile b. Find its appropriate place in the sorted pile (for this you need a temp pile) c. Go back to step 2 But, how to do step 2-b?
Sorting Unsorted Pile Sorted Pile Temporary Pile
Sorting 18 3 7 1 2 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 3 7 1 2 19 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 3 7 1 2 Is 3 > 18? 19 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 3 7 1 2 Is 3 > 18? 19 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 7 1 2 3 19 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 7 1 18 2 3 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 7 1 Is 7 > 18? 18 2 3 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 7 1 Is 7 > 18? 2 3 18 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 7 1 2 Is 7 > 03? 3 18 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 1 7 2 3 18 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 18 1 7 2 3 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting Is 1 > 18? 18 1 7 2 3 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting Is 1 > 18? 1 7 2 18 3 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 1 Is 1 > 07? 7 2 18 3 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 1 Is 1 > 07? 2 7 18 3 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 1 2 7 Is 1 > 03? 18 3 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 1 3 2 7 Is 1 > 03? 18 19 Unsorted Pile Sorted Pile Temporary Pile
Sorting 3 2 7 18 19 1 Unsorted Pile Sorted Pile Temporary Pile
Sorting 2 3 7 18 19 1 Unsorted Pile Sorted Pile Temporary Pile
Sorting 7 2 3 18 19 1 Unsorted Pile Sorted Pile Temporary Pile
Sorting 18 7 2 3 19 1 Unsorted Pile Sorted Pile Temporary Pile
Sorting Is 2 > 18? 18 7 2 3 19 1 Unsorted Pile Sorted Pile Temporary Pile
Sorting Is 2 > 18? 7 2 3 19 1 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting Is 2 > 07? 7 2 3 19 1 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting Is 2 > 07? 2 3 7 19 1 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting Is 2 > 03? 2 3 7 19 1 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 3 Is 2 > 03? 2 7 19 1 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 3 2 7 Is 2 > 01? 19 1 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 3 2 7 19 1 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 3 2 7 19 1 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 7 3 2 19 1 18 Unsorted Pile Sorted Pile Temporary Pile
Sorting 18 7 3 2 19 1 Unsorted Pile Sorted Pile Temporary Pile
Sorting Is 19 > 18? 18 7 3 2 19 1 Unsorted Pile Sorted Pile Temporary Pile
Sorting 19 18 7 3 2 1 Unsorted Pile Sorted Pile Temporary Pile
1. Check if the unsorted pile is empty a. If yes: halt b. If no: take a card from the unsorted pile to place it on the sorted pile Check if the sorted pile is empty a. If yes: i. Place the card on the sorted pile ii. Go back to step 1 b. If no: i. Check if the card is greater than the first card on the sorted pile A. If yes: I. Place the card at the top of the sorted pile II. If the temp pile is not empty, flip it up and place it back on the top of the sorted pile III. Go back to step 1 B. If no: I. Take the card from the top of the sorted pile and place it at the top of the temp pile II. Go back to step 2-b-i 2.
Reverse the Sorted Pile 1. This algorithm will produce a sorted pile in an increasing order 2. Can you modify it to produce a sorted pile in a decreasing order?
Merging Let us say you have two friends who can help you in sorting the cards If you split the cards into two subsets and assign each subset to each of your friends, they can apply your sorting algorithm and return to you two sorted piles How can you merge these two sorted piles into a single sorted pile? Premise: the lowest (or highest) card across the two piles is the lowest (or highest) card overall Action: take this card and place it as the first card in the single sorted pile Repeat!
Merging 19 > 18 18 19 3 7 1 2 Sorted Pile 1 Sorted Pile 2 Final Sorted Pile
