Sorting Algorithms
For all examples, assume a dummy array, like x = [-5,-3,2,1,-3,-3,7,2,2] This could be any array, but this is simply an example to work with. We are sorting this array in ASCENDING order.
Bubble Sort
Think of this as a bubbling effect that goes through the entire dataset and makes elements bubble into their appropriate positions.
Example:
- A way to think about this algorithm is having a deck of 10 cards
- You want them in ascending order, so you run bubble sort
- You loop throught the entire array, starting with the second card, and comparing it to the first(if a swap is neccesary, you do it)
- After you're done looping through it once, if any swaps occured, you want to run the above step again(to make sure it's completely sorted)
- After ALL the loops are done, you turn off the loop, and you're done!
Algorithm:
- Start at index
i, and elements from left to right - Loop through the entire array by incrementing i, and swap the positions for ascending order
- Repeat the above 2 steps, using a flag variable, until the entire dataset is ordered in ascending order
Complexity:
- Time Complexity: O(n²), which means it takes a long time(bad)
- Space Complexity: O(1) - takes basically no memory(good)
- This is known as an in-place sort because you're not creating a new array
Python code for bubble sort:
x = [-5,-3,2,1,-3,-3,7,2,2] # dummy array
flag = True # variable to see if we should keep looping
while flag: # keep looping through array, to fully sort
flag = False # set false after no more switches are made, exit loop
for i in range(1, len(x)): # for indexs 1 through length - 1 (we don't want 0 because we are subtracting by one)
if(x[i] < x[i-1]): # if the last index is bigger than the current index
x[i], x[i-1] = x[i-1], x[i] # swap the values
flag = True # a swap occurred, so continue the loop
print(x)