README.md

Linked Lists

Description

Code that defines a custom list class (linked lists) and implements four sorting algorithms; then records their runtimes when sorting lists with increasing number of elements.

Data Structure

List of nodes

python-lists-in-python/main.py

Lines 7 to 9 in 56f69ac

	class linked_list():
	def __init__(self, contents=[], first=None):
	self.first = linked_list.__node(None,first)

Nodes

Nodes have a item in them and point to another node

python-lists-in-python/main.py

Lines 15 to 18 in 56f69ac

	class __node():
	def __init__(self, item, next=None):
	self.item = item
	self.next = next

Sorting Algorithms

	Bubble	Selection	Merge	Quick
Time Complexity	O(n2)	O(n2)	O(n log n)	O(n log n)

Bubble

Compares pairs of elements and swaps them if they are out of order.

Selection

Takes the smallest element of the main list and adds it to a sub-list until it get to the end of the list.

Merge

Splits the list into elements, then merges pairs of sub-lists keeping, the elements in order until it is one list again.

Quick

Selects a pivot and moves all smaller elements to one side of the list then does the same to each side of the list.