Basic Sorting Algorithms

Bubble Sort

A sorting algorithm that is based upon comparing pairs of values and swapping their places if necessary.

Overall Idea:

- (L→ List, i→ index, i starts at 1)    
- Look at L[i] and L[i-1] if they are not sorted, swap locations
- Repeat as you increase i and until no swap occurs

Bubble Sort Demonstration:

repeat until swapped is false
	swapped = false
	for i = 1 to N-1 (inclusively)
		if A[i-1] > A[i] then
			swap(A[i-1],A[i])
			swapped = true

# Bubble Sort:
def bubble(array):
    swapped = True

    if not array:
        return []
    elif len(array) == 1:
        return array
    else:
        while swapped:
            swapped = False
            # Execute necessary swaps from array[1] to array[n]
            for i in range(1,len(array)):
                if array[i-1] > array[i]:
                    # swapping; set swapped to True
                    temp = array[i-1]
                    array[i-1] = array[i]
                    array[i] = temp
                    swapped = True
            # end of for
        # end of while
        return array
# end of bubble()

test = [6, 5, 3, 1, 8, 7, 3, 4]
bubble(test) # since it is a list, it will mutate it

print('Sorted:', test)

Sorted: [1, 3, 3, 4, 5, 6, 7, 8]

Insertion Sort

A sorting algorithm that iterates sorts from the bottom one element at a time.

Overall Idea:

Since a singleton list is already sorted, it will grow its “sorted” list with the next value from the list
It grabs the next value, removes it, and places in the correct location
It does this until the list is fully sorted

Insertion Sort Demonstration:

-- Let A be a List, i and j both be indexes

i = 1
while i < length(A)
	j = i
	while j > 0 and A[j-1] > A[j]
		swap A[j] and A[j-1]
		j = j - 1
	i = i + 1

# Insertion Sort

def insertSort(array):
    i = 1

    if not array:
        return []
    elif len(array) == 1:
        return array
    else:
        while i < len(array):
            j = i # setting up j indexer
            while j > 0 and array[j-1] > array[j]:
                # swapping
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp

                # decrease j
                j -= 1
            # end of inner while
            i += 1
        # end of while
        return array
# end of insertSort()

test = [6, 5, 3, 1, 8, 7, 3, 4]
insertSort(test) # since it is a list, it will mutate it

print('Sorted:', test)

Sorted: [1, 3, 3, 4, 5, 6, 7, 8]

Selection Sort

A sorting algorithm that uses two lists: sorted list and unsorted list.

It brings the smallest values to the sorted list then removed the smallest value in the unsorted list .

Overall Idea:

At beginning, sorted list is empty and unsorted list is full
Choose the smaller(or largest) value from the unsorted list, and append it to the sorted list
Repeat until unsorted list is empty

Selection Sort Demonstration:

-- Let A be the unsorted list, and let B be the sorted list; B starts empty

repeat until A is empty
    Target = the smallest value from A
    Append Target to B
    Remove target from A

# Recursive Selection Sort

def selectSort(array, result=[]):
    if not array:
        return result
    else:
        smallest = array[0]
        small_index = 0

        for i in range(1,len(array)):
            if array[i] < smallest:
                smallest = array[i]
                small_index = i
        # end of for
        result.append(array.pop(small_index))

        return selectSort(array, result)

test = [6, 5, 3, 1, 8, 7, 3, 4]
sorted_test = selectSort(test) # the algorithm is designed to create/return a new list

print('Sorted:', sorted_test)

Sorted: [1, 3, 3, 4, 5, 6, 7, 8]

Complexity of Bubble, Insertion, and Selection Sort.

The 3 sorting algorithms are learned together due to their Big-O Notation.

All 3 algorithms are classified as $O(n^2)$ .

PreviousBinary Search NextRecursion

Last updated 1 year ago

hashtagBubble Sort

hashtagInsertion Sort

hashtagSelection Sort

hashtagComplexity of Bubble, Insertion, and Selection Sort.

Bubble Sort

Insertion Sort

Selection Sort

Complexity of Bubble, Insertion, and Selection Sort.