{"assignment":{"_schema_version":2,"course_id":37,"date_created":"2022-06-28T19:00:00+00:00","date_modified":"2023-09-10T14:21:49.846605+00:00","extra_instructor_files":"","extra_starting_files":"","forked_id":null,"forked_version":null,"hidden":false,"id":1136,"instructions":"## Sorting and Searching\n\n- **Sorting:** Putting elements in ascending order\n- **Searching:** Finding a specific element in a list\n\nIn this chapter, we will be looking at sorting and searching, two important operations on a list.\nThese operations have been exhaustively studied by computer scientists over the year, and they have some interesting characteristics.\nSo, although we study them partially because they are useful, we also will study them because they are educational.\n\n## Simple Sorting\n\n```python simple-sorting\ndata = [5, 4, 9, 7, 3, 6]\n\nin_order = sorted(data)\n\nprint(in_order)\n```\n\nOne of the most fundamental operations to perform on a list is to sort the elements.\nFor a list of numbers like the in the following example, this puts them into ascending order.\nYou can sort elements of any type if they support ordering comparisons; this includes strings and floats, but does not include lists or dataclasses (at least not normally.)\nSorting is so useful that Python provides a built-in `sorted` function to make it easy to sort a given list.\nBefore we talk about how the `sorted` function works, let's study a different problem: searching.\n\n## Iterative Search\n\n```python iterate-search\ndef linear_search(target: int, data: list[int]) -> int:\n    for number in data:\n        print(number, target, data)\n        if target == number:\n            return target\n    return None\n\nprint(linear_search(3, [1, 2, 9, 5, 7, 8, 3]))\n```\n\nPreviously, we learned how the find pattern would let us determine if an element was in a list.\nThat pattern had us use a `for` loop to walk through each number in the list and check if it was the target.\nIf we find the target, we can immediately return.\nBut in the worst possible case, the element could be at the very end or not even in the list.\nIn that case, we would have to go check every single element.\nIf there were a million elements, we would potentially need to do a million checks! This is known as _linear search_, or sometimes _iterative search_, and it is easy to understand but can be unfortunately slow.\nFortunately, there is a faster way to search that we can use _if_ we have a sorted list.\n\n## Binary Search\n\n```python binary-search\ndef binary_search(target: int, data: list[int]) -> int:\n    midpoint = len(data)//2\n    while target != data[midpoint]:\n        print(midpoint, target, data)\n        if target < data[midpoint]:\n            data = data[:midpoint]\n        else:\n            data = data[midpoint+1:]\n        midpoint = len(data)//2\n        if not data:\n            return None\n    return target\n\nprint(binary_search(3, [1, 2, 5, 7, 8, 9]))\n```\n\nShown here is the classic binary search algorithm that can find an element in a list more quickly than a linear search if the list is already sorted.\nThe algorithm works by repeatedly dividing the list in half to find a target.\n\nFirst, the function calculates the midpoint of the list using the `len` function.\nIf the `target` is equal to the value at the middle index of the list, then we stop looping and return the `target`.\nHowever, if not, then instead we check whether the `target` is less or greater than the value at the midpoint.\nIf less than, we trim `data` to be only the first half of the list.\nIf it is greater than, we trim `data` to be the second half of the list, skipping over the midpoint element.\nThen, we recalculate the new midpoint of this smaller, half-sized list.\nIf we run out of list, then we stop the function and return `None`. Otherwise, we loop back and check whether we have found our target.\nTry experimenting with different values for `target` and `data` to see the effect on the iteration.\n\n## Binary Search Time Complexity\n\n- `log\u2082(8 elements)` is 3 divisions (8 \u2192 4 \u2192 2 \u2192 1)\n- `log\u2082(1024 elements)` is 10 divisions (1024 \u2192 512 \u2192 256 \u2192 128 \u2192 64 \u2192 32 \u2192 16 \u2192 8 \u2192 4 \u2192 2 \u2192 1)\n- `log\u2082(1 million elements)` is 20 divisions\n\n\nThis binary search algorithm, which repeatedly divides a search space in half, is one of the most remarkable algorithms in computer science.\nYou will see that its approach is much faster than a simple iterative search.\nThe time complexity of binary search is said to be \"logarithmic on the size of the input\".\nLogarithmic refers to how we repeatedly divide the input into two.\nThe logarithm of a number is the number of times that number can be divided by a given base until you reach 1.\nShown here are some some examples of base-2 logarithm (log\u2082) for different sized lists.\nLogarithmic relationships are significantly better than linear relationships (doing 20 checks instead of a million!), although they do not beat constant time.\nStill, being faster than linear is a wonderful accomplishment and we should be proud of this little algorithm.\nKeep in mind, however, that this faster search is only possible because we knew the list was sorted.\n\n## Some Sorting Algorithms\n\n* Bubble Sort\n* Selection Sort\n\nSo, since sorting is so useful, we need to understand how it works.\nIn the rest of this section, we will quickly go over the code of two different sorting algorithms just to give you an idea of what is possible.\nThis may not be sufficient to help you learn how the algorithms work, but we will provide some links at the end of this lesson to good websites that have helpful visualizations of these sorting algorithms in more depth.\n\n## Bubble Sort\n\n```python bubble-sort\ndef bubble_sort(data: list[int]) -> list[int]:\n    length = len(data)\n    # Iterate through each list index\n    for i in range(length):\n        # Iterate through all remaining indexes at this point\n        for j in range(length - i - 1):\n            # If right element is bigger than left element\n            if data[j] > data[j+1]:\n                data[j], data[j+1] = data[j+1], data[j]\n    return data\n\nprint(bubble_sort([5, 4, 9, 7, 3, 6]))\n```\n\nOne of the simplest classic sorting algorithms is _bubble_ _sort_, which operates by repeatedly swapping pairs of adjacent elements until all elements are in the right order.\nNote the most-indented line of the function, which does a swap of two adjacent list elements, but only if the first element is greater than the second element.\nThat conditional swap is inside of a nested `for` loop.\nThe outer loop is guaranteed to run a linear number of times, once for each element of the list.\nEvery inner loop requires an additional linear number of steps.\nAlthough we do one fewer step each time, we are still going to have to do a linear number in total.\nNesting a linear loop inside of a linear loop actually causes quadratic growth, which is very slow indeed.\nBubble sort is fairly easy to code but does not work very well in practice.\n\n## Insertion Sort\n\n```python insertion-sort\ndef insertion_sort(data: list[int]) -> list[int]:\n    # Iterate through each list index\n    for i, current in enumerate(data):\n        j = i - 1\n        # Go back through the list to find next smallest\n        while j >= 0 and data[j] > current:\n            # Swap element backwards\n            data[j+1] = data[j]\n            j -= 1\n        # Swap that element into the target index\n        data[j+1] = current\n    return data\n\nprint(insertion_sort([5, 4, 9, 7, 3, 6]))\n```\n\nAn improvement to bubble sort is _insertion sort_, which also works by swapping adjacent elements.\nHowever, the difference is in the inner loop, which no longer iterates through all of the elements.\nInstead, the inner loop is a `while` loop that swaps the current element backwards through the list until it encounters a smaller element.\nAt any given point in time, the elements prior to the `current` element are in sorted order.\nWe are merely dragging elements from the back of the list to the front and placing them in the appropriate spot.\nIn the best case, the list is already sorted, and we only must walk through to confirm this.\nBut in the worst case, we may be dragging each element all the way from the back to our current position as we walk through the list.\nThis makes insertion sort an even more interesting sorting algorithm because suddenly the runtime depends on more than just the size of the input: the value of the input also affects the time complexity.\nStill, the fact that sometimes when the sorting algorithm performs poorly, it just means we should find a better one.\n\n## Other Sorts\n\n- Selection sort\n- Merge sort\n- Quick sort\n- Counting sort\n- ...\n\nThere are a huge number of other sorting algorithms out there, each with their own advantages and disadvantages.\nWe have only looked at two simple ones, bubble sort and insertion sort.\nIf you would like to learn more sorting algorithms, we recommend you check out a website like [VisualGo](https://visualgo.net/en/sorting) (https://visualgo.net/en/sorting) for interactive visualizations.\nThere are many more resources on the web for learning about sorting algorithms.\nYou might go and learn more about other sorting algorithms like selection sort, merge sort, or quick sort.\n\n## Summary\n\n- Searching a list is the problem of determining if an element exists inside of a list.\n- Linear Search iterates through all the elements of the list, taking time proportionate to the number of elements.\n- Binary Search is faster, working by repeatedly dividing a sorted list in half, taking only a logarithmic amount of time to the number of elements.\n- Sorting a list is the problem of ordering the elements of the list so that they are in ascending value.\n- Bubble Sort is a sorting algorithm that swaps adjacent pairs of elements until all elements are in sorted order.\n- Insertion Sort is a sorting algorithm that repeatedly drags elements from the back of the list to the front (in sorted order).\n- There are many ways to sort a list.","ip_ranges":"","name":"11A2) Sorting Reading","on_change":"","on_eval":"","on_run":"","owner_id":1,"owner_id__email":"acbart@udel.edu","points":0,"public":true,"reviewed":false,"sample_submissions":[],"settings":"{\n  \"header\": \"Sorting and Searching\",\n  \"youtube\": {\n    \"Bart\": \"AwM62lQAqJM\",\n    \"Amy\": \"_4Eheef8jYs\"\n  },\n  \"video\": {\n    \"Bart\": \"https://blockpy.cis.udel.edu/videos/bakery_time_sorting-Bart.mp4\",\n    \"Amy\": \"https://blockpy.cis.udel.edu/videos/bakery_time_sorting-Amy.mp4\"\n  },\n  \"summary\": \"\",\n  \"small_layout\": true\n}","starting_code":"","subordinate":true,"tags":[],"type":"reading","url":"bakery_time_sorting_read","version":11},"ip":"216.73.216.157","submission":{"_schema_version":3,"assignment_id":1136,"assignment_version":11,"attempts":0,"code":"","correct":false,"course_id":37,"date_created":"2026-05-20T14:01:40.370575+00:00","date_due":"","date_graded":"","date_locked":"","date_modified":"2026-05-20T14:01:40.370575+00:00","date_started":"","date_submitted":"","endpoint":"","extra_files":"","feedback":"","grading_status":"NotReady","id":2036899,"score":0.0,"submission_status":"Started","time_limit":"","url":"submission_url-f549bb8c-8e2d-45f8-81b6-1a6759dad53e","user_id":2044668,"user_id__email":"","version":0},"success":true}