Sorting
This implementation is different than the ones in the referenced books, which are different from each other.
It uses methods and functions that do iteration versus for-loops. Just remember it's still O(n^2).
"""
from collections.abc import MutableSequence
from src.typehints import T
def selection_sort_iter(seq: MutableSequence[T]) -> None:
"""Use selection sort iteratively on a list in-place."""
for i, val in enumerate(seq):
min_val = min(seq[i:])
min_val_i = seq.index(min_val, i) # First index of min_val at or after i
seq[i] = min_val
seq[min_val_i] = val# insertion sort
my_book = {'title': 'Food for thought', 'author': 'jon jones', 'genre': 'food'}
class Book:
def __init__(self, title, author, genre):
self.title = title
self.author = author
self.genre = genre
def __str__(self):
return f'{self.genre}: {self.title} by {self.author}'
b1 = Book('Food for thought', 'jon jones', 'food')
b2 = Book('My life in reality', 'don davis', 'life')
b3 = Book('Apples, how you like them?', 'stan simpson', 'food')
b4 = Book('Just Do It', 'shia le boeuf', 'inspirational')
b5 = Book('What is this code anyway', 'tom jones', 'programming')
books = [b1, b2, b3, b4, b5]
def in_sort(books):
# loop through len - 1 elements
for i in range(1, len(books)):
# code up some logic
# save current i to a temp var
temp = books[i]
j = i
while j > 0 and temp.title < books[j - 1].title:
# shift left until correct tile is found
books[j] = books[j - 1]
j -= 1
# insert book in correct position
books[j] = temp
return books
# for b in books:
# print(b)
# print('---------------------')
# in_sort(books)
# for b in books:
# print(b)
"""
- **Insertion Sort** is an _in-place_ algorithm, meaning that it
does not require any additional memory to perform the sort operation.
- It works by conceptually dividing the array into _sorted_ and _unsorted_ pieces.
1. Consider element at index 0 to be our _sorted_ piece. The rest of the array is our _unsorted_ piece.
2. Save the 1st element in the _unsorted_ piece in a temp variable.
3. Shift elements in the _sorted_ piece over to the right until we find where the element
from step 2 should go.
4. Insert the element from step 2 into its correct index within the _sorted_ piece.
5. Repeat steps 2-4 until all elements have been processed.
"""
def in_sort2(lst):
# loop over n - 1 elements
for i in range(1, len(lst)):
# save initial element to temp variable
temp = lst[i]
# set inner loop index to current index
j = i
# inner loop
while j > 0 and temp < lst[j - 1]:
# shift left until correct position found
lst[j] = lst[j - 1]
# decrement inner index
j -= 1
# insert temp at correct position
lst[j] = temp
# return our list
return lst
my_nums = [23, 34, 60, 1, 4, 5, 2]
my_names = ['Dave', 'Steve', 'Bob']
print(my_nums)
in_sort2(my_nums)
print(my_nums)
print(my_names)
in_sort2(my_names)
print(my_names)
JavaScript:
Bubble Sort
Script Name
Bubble Sort Algorithm.
Aim
To write a program for Bubble sort.
Purpose
To get a understanding about Bubble sort.
Short description of package/script
It is a python program of Bubble sort Algorithm.
It is written in a way that it takes user input.
Workflow of the Project
First a function is written to perform Bubble sort.
Then outside the function user input is taken.
Detailed explanation of script, if needed
Start with the first element, compare the current element with the next element of the array. If the current element is greater than the next element of the array, swap both of them. If the current element is less than the next element, move to the next element. Keep on comparing the current element with all the elements in the array. The largest element of the array comes to its original position after 1st iteration. Repeat all the steps till the array is sorted.
Example
Setup instructions
Just clone the repository .
Output
Insertion Sort
Divide and Conquer
Divide and conquer is when we take a problem, split it into the same type of sub-problem, and run the algorithm on those sub-problems.
If we have an algorithm that runs on a list, we could break the list into smaller lists and run the algorithm on those smaller lists. We will divide the data into more manageable pieces.
We break down our algorithm problems into base cases -- the smallest possible size of data we can run our algorithm upon to determine the basic way our algorithm should work.
These solutions can give us better time complexity solutions; however, they wouldn't work if a portion of the algorithm's data is dependent upon the rest. If we broke the list into two halves, and one half is required to work on the other half, we could not use recursion.
Recursion requires independent sub-data.
Let's apply recursion to breaking down what a list is. The sum of a list is equal to the first element plus the rest of the list. We could write that like in this add_list function found in this file:
This should print 10, or the sum of the items in our list.
On each pass, the add_list function is taking the first item and adding the sum of the rest of the list, found by calling add_list on the remainder of the list. This would loop through the rest of the list in this manner, only adding together the elements once the final element was reached.
Finding a sum like this is not the most time efficient -- it would be better to do iteratively. But this allows us to understand how recursion works.
Often, iterative solutions are easier to read and more performant.
If we add a print statement into the add_list function:
The terminal would print:
Add 1 to the sum of [2, 3, 4] Add 2 to the sum of [3, 4] Add 3 to the sum of [4] Add 4 to the sum of [] 10
This helps us understand what is happening at each recursive step.
Our base case is an empty list or 0, which is what we handle at the beginning of our function with returning 0 if the list is empty. By filling that in, it gives us our first return, so that each previous add_list call can be resolved based on the sum of the next.
When we use recursion, it uses a lot of memory, so each recursive calls allocates an amount of memory. We have a pre-set recursion limit in case we write an infinitely recursive algorithm to prevent our computer needing to reboot to end the algorithm.
With Big O, we're interested in the number of times we have to run an operation. add_list just runs basic addition, which is a single operation, and it is being called one time for every element in the list, so this is O(n).
Quick Sort
Quick sort is a great example use case of a recursive appropriate solution.
We need to include a base case and then call itself.
Quick sort sorts a list using partitioning. The partitioning process involves splitting up data around the pivot.
If our list is [5, 3, 9, 4, 8, 1, 7].
We'll choose a pivot point to split the list. Let's say we choose 5 as the pivot. One list will contain all the numbers less than 5, and the other will contain all the numbers greater than or equal to 5. This results in two lists like so:
[3, 4, 1] 5 [9, 8, 7]
5 is already sorted into the correct place that it needs to be. All the numbers to the right and left of it are in the area they need to, just not yet sorted.
This process is partitioning.
Our next step is to repeat this process until we hit our base case, which is an empty list or a list with just one element. When everything is down to one element lists, then we know they are properly sorted.
3 and 9 are our next pivots: [1] 3 [4] 5 [8, 7] 9 Next, 8 is our pivot: [1] 3 [4] 5 [7] 8 [] 9 1 3 4 5 7 8 9
The number of sorted items doubles with each pass through this algorithm, and we have to make one complete pass through the data on each loop. That means each pass is O(n), and we have to make log n passes.
It takes O(log n) steps to pass through, with each pass taking O(n), so the average case is O(n log n), the fastest search we can aim for.
What would be a bad case for quick sort?
[1, 2, 3, 4, 5, 6, 7]
If we look at the order of this on each loop:
[] 1 [2, 3, 4, 5, 6, 7] 1 [] 2 [3, 4, 5, 6, 7] 1 2 [] 3 [4, 5, 6, 7] 1 2 3 [] 4 [5, 6, 7] 1 2 3 4 [] 5 [6, 7] 1 2 3 4 5 [] 6 [7] 1 2 3 4 5 6 7
This took a full 7 passes, for 7 elements, because there was only one sorted item being added with each pass.
Already sorted lists are the worst case scenario which results in an order O(n^2).
Quick sort shines when the first pivot chosen is roughly the median value of the list. Now, since we can't always choose the median value with the traditional quick sort.
We could use quick select to find the median at each step -- but this slows down our algorithm to O(n) run time on average.
If we choose a random pivot point, we generally do not pick the worst case pivot with each pass. Randomly selecting a pivot point results in the most time efficient average.
Implementing Quick Sort
If we were to write out our quick sort algorithm in a basic way, it would look something like this:
Let's define our partition function next:
Let's test out a bunch of possible cases like so:
We already know off the tops of our heads that we have not setup our algorithm to handle edge cases like an input that is not a list, or is a list full of strings, etc.
Our terminal returns back:
So we can see that it handles all of our tests well.
It's important to analyze what you know about your incoming data before choosing a type of algorithm. If you know that your list is almost completely sorted, bubble sort would handle that the quickest. If the list is completely garbled, quick sort would be best.
Even when we aren't handling sort, we need to customize our algorithmic choices to the data anticipated, especially when dealing with large sets of data where time performance can have a huge impact.
In Place Sorting
The quick sort function we wrote is not an in-place solution. When we sort that list, we're actually returning an entirely new list. It's not returning the same list.
This isn't time or space efficient because it takes time and data to copy lists over to newly allocated spots in memory. It would be more efficient to move items around within the original given list.
This is in-place sorting -- using the original list to sort items within it and returning that same original list, but now sorted. We mutate the original list rather than making new lists.
To do in-place sorting, we need to be able to pass into the function the bounds of the current part of the list that we're working on, to ensure that we are only working on certain segments of the list at a time.
We can give it a low index, and a high index, to indicate the start and stop points of the section of the list to work on.
As we keep going, the low and high indices will change. Our base case should now change to where if the low and high are the same, then our list is sorted.
Let's try it:
We're iterating through the list and checking if the item at list[i] is less than the item at list[pivot_index]. If it is, then we need to swap these items.
That has to happen in two steps. First we swap i with an item one beyond the pivot index. Then we swap the pivot with the item after the pivot.
Then we update the pivot index to search for the next item to sort in the array.
In order to call this function without passing in three parameters, we can write a short helper function:
Now we can run this function and it sorts our lists without allocating extra memory.
Let's add some print statements just to see exactly what is happening at each step on one of the sorts:
This helps us visualize why we go through each swapping step and how the list is slowly being sorted, and split apart into smaller sorting lists.
ArrayBinary Search TreeLinked ListExtra-ArrayStackBinary TreeRecursionHash TableSearchingSortingQueue SandboxHash TableDouble Linked ListGraphsExoticHeapLast updated
Was this helpful?