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

JavaScript:

// Implement Bubble Sort

function swap(array, idx1, idx2) {
  let temp = array[idx1];
  array[idx1] = array[idx2];
  array[idx2] = temp;
}

function bubbleSort(array) {
  let swapped = true;

  while (swapped) {
    swapped = false;

    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        swap(array, i, i + 1);

        swapped = true;
      }
    }
  }

  return array;
}

let array1 = [2, -1, 4, 3, 7, 3];
bubbleSort(array1);
console.log(" bubbleSort(array): ", bubbleSort(array1));
module.exports = { bubbleSort: bubbleSort, swap: swap };
def partition(A, lo, hi):
    pivot = A[lo + (hi - lo) // 2]
    i = lo - 1
    j = hi + 1

    while True:

        i += 1
        while A[i] < pivot:
            i += 1

        j -= 1
        while A[j] > pivot:
            j -= 1

        if i >= j:
            return j
        A[i], A[j] = A[j], A[i]


def quicksort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)
    return A


if __name__ == "__main__":
    arr = [8, 3, 5, 1, 7, 2]
    quicksort(arr, 0, len(arr) - 1)
    #  >>> [1, 2, 3, 5, 7, 8]

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

Consider an array a=[5,4,3,2,1]
Iteration 1:-
         |5|4|3|2|1|
          |___________5>4 therefore we swap both of them.
         |4|5|3|2|1|
            |_________5>3 therefore we swap both.
         |4|3|5|2|1|
              |_______5>2 therefore we swap.
         |4|3|2|5|1|
                |_____5>1 therefore we swap.
         |4|3|2|1|5| Now 5 is placed at its original position

Iteration 2:-
         |4|3|2|1|5|
          |__________4>3 therefore we swap both.
         |3|4|2|1|5|
            |________4>2 therefore we swap both.
         |3|2|4|1|5|
              |______4>1 therefore we swap both.
         |3|2|1|4|5|
                 |__ 4 is placed at its original position.

Iteration 3:-
         |3|2|1|4|5|
          |_________3>2 we swap.
         |2|3|1|4|5|
            |_______3>1 we swap.
         |2|1|3|4|5|- 3 is placed at original position.

Iteration 4:-
          |2|1|3|4|5|
           |_________2>1 we swap.
          |1|2|3|4|5| the array is sorted.

Setup instructions

Just clone the repository .

Output

#Link to problem:- 
#Bubble sort is a sorting algorithm. Sorting algorithms are used to arrange the array in particular order.In,Bubble sort larger elements are pushed at the end of array in each iteration.It works by repeatedly swapping the adjacent elements if they are in wrong order.

def bubbleSort(a): 
    n = len(a) 
    # Traverse through all array elements 

    for i in range(n-1): 
        # Last i elements are already in place 
        for j in range(0, n-i-1): 

            # traverse the array from 0 to n-i-1 
            # Swap if the element found is greater 
            # than the next element 
            if arr[j] > arr[j + 1] : 
                arr[j], arr[j + 1] = arr[j + 1], arr[j] 

arr = []
n=int(input("Enter size of array: "))
for i in range(n):
    e=int(input())
    arr.append(e)
bubbleSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
     print(arr[i])
     
#Time complexity - O(n^2)
#Space complexity - O(1)

Insertion Sort

# Insertion Sort

## Aim

The main aim of the script is to sort numbers in list using insertion sort.

## Purpose

The main purpose is to sort list of any numbers in O(n) or O(n^2) time complexity.

## Short description of package/script

Takes in an array. <br>
Sorts the array and prints sorted array along with the number of swaps and comparisions made.
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

## Detailed explanation of script, if needed

To sort an array of size n in ascending order: <br>
1: Iterate from a[1] to a[n] over the array. <br>
2: Compare the current element (val) to its predecessor. <br>
3: If the val is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element. <br>

## Setup instructions

Download code and run it in any python editor. Latest version is always better.

## Compilation Steps

1.Edit array a and enter your array/list you want to sort. 2. Run the code

## Sample Test Cases

### Test case 1:

input:<br>
a = [34,5,77,33] <br>

output :<br>

5, 33, 34, 77 along with <br>
no. of swaps = 3 <br>
no. of comparisons=5<br>

### Test case 2

input<br>
a=[90,8,11,3,2000,700,478] <br>

Output:<br>

No. of swaps= 8 <br>
No. of comparisions=12 <br>
Sorted Array is: <br>
3 8 11 90 478 700 2000<br>

### Test case 3

input<br>
a=[0,33,7000,344,-88,2000]<br>

output:<br>

No. of swaps= 6<br>
No. of comparisions=10<br>
Sorted Array is:<br>
-88 0 33 344 2000 7000<br>

## Output

<img width = 221 height = 27 src="../Insertion Sort/Images/input.png">
<img width = 385 height = 188 src="../Insertion Sort/Images/sort_output1.png">

Divide and Conquer

When would we use recursive solutions? Tree traversals and quick sort are instances where recursion creates an elegant solution that wouldn't be as possible iteratively.

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:

def add_list(l):
    # The sum of an empty list is 0
    if l == []:
        return 0

    return l[0] + add_list(l[1:])


l = [1,2,3,4]

print(add_list(l)) # Should print 10

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:

    print(f'Add {l[0]} to the sum of {l[1:]}')
    return l[0] + add_list(l[1:])

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:

def quicksort(list):
    # One of our base cases is an empty list or list with one element
    if len(list) == 0 or len(list) == 1:
        return list

    # If we have a left list, a pivot point and a right list...
    left, pivot, right = partition(list)

    # Our sorted list looks like left + pivot + right, but sorted.
    # Pivot has to be in brackets to be a list, so python can concatenate all the elements to a single list
    return quicksort(left) + [pivot] + quicksort(right)

Let's define our partition function next:

def partition(list):
    left = []
    pivot = list[0] # Or make random, as a stretch
    right = []

    for v in list[1:]:
        if v < pivot:
            left.append(v)
        else:
            right.append(v)

    return left, pivot, right

Let's test out a bunch of possible cases like so:

print(quicksort([]))
print(quicksort([1]))
print(quicksort([1,2]))
print(quicksort([2,1]))
print(quicksort([2,2]))
print(quicksort([5,3,9,4,8,1,7]))
print(quicksort([1,2,3,4,5,6,7]))
print(quicksort([9,8,7,6,5,4,3,2,1]))

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:

[]
[1]
[1, 2]
[1, 2]
[2, 2]
[1, 3, 4, 5, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

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:

def quicksort2(l, low, high):
    if len(l) == 0 or len(l) == 1:
        return l

    if low >= high:
        return l

    pivot_index = low

    # Partitioning
    for i in range(low, high):

        if l[i] < l[pivot_index]:
            # If i is less than pivot, we need to swap it with the item after the pivot
            l[i], l[pivot_index + 1] = l[pivot_index + 1], l[i]

            # Then we'll swap the pivot with the item after the pivot
            l[pivot_index], l[pivot_index + 1] = l[pivot_index + 1], l[pivot_index]

            # Update the pivot index:
            pivot_index += 1

    # Sort from low to the pivot index
    quicksort2(l, low, pivot_index)
    # Sort from the pivot index to high
    quicksort2(l, pivot_index + 1, high)

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:

def in_place_quicksort(l):
    return quicksort2(l, 0, len(l))

print(in_place_quicksort([]))
print(in_place_quicksort([1]))
print(in_place_quicksort([1,2]))
print(in_place_quicksort([2,1]))
print(in_place_quicksort([2,2]))
print(in_place_quicksort([5,3,9,4,8,1,7]))
print(in_place_quicksort([1,2,3,4,5,6,7]))
print(in_place_quicksort([9,8,7,6,5,4,3,2,1]))

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:

Our starting list is [5,3,9,4,8]. 

Checking against 5. Current list is [5, 3, 9, 4]. 

Checking against 3. Current list is [5, 3, 9, 4]. 

3 is less than 5, so we need to swap l[i] (3) with l[pivot_index + 1] (3).
Next, we will swap 5 with 3 and increase the pivot index from 0 to 1.
Now the current list is [3, 5, 9, 4] 

Checking against 9. Current list is [3, 5, 9, 4]. 

Checking against 4. Current list is [3, 5, 9, 4]. 

4 is less than 5, so we need to swap l[i] (4) with l[pivot_index + 1] (9).
Next, we will swap 5 with 4 and increase the pivot index from 1 to 2.
Now the current list is [3, 4, 5, 9] 


Splitting list to check quicksort([3, 4, 5, 9], 0, 2) and quicksort([3, 4, 5, 9], 3, 4). 


Checking against 3. Current list is [3, 4, 5, 9]. 

Checking against 4. Current list is [3, 4, 5, 9]. 



Splitting list to check quicksort([3, 4, 5, 9], 0, 0) and quicksort([3, 4, 5, 9], 1, 2). 

Checking against 4. Current list is [3, 4, 5, 9]. 



Splitting list to check quicksort([3, 4, 5, 9], 1, 1) and quicksort([3, 4, 5, 9], 2, 2). 

Checking against 9. Current list is [3, 4, 5, 9]. 



Splitting list to check quicksort([3, 4, 5, 9], 3, 3) and quicksort([3, 4, 5, 9], 4, 4). 

Our final sorted list is [3, 4, 5, 9]

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 ListGraphsExoticHeap

Last updated