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(n²)	O(n²)	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.
Name		Name	Last commit message	Last commit date
Latest commit History 23 Commits
README.md		README.md
bubble_sort_21000.csv		bubble_sort_21000.csv
main.py		main.py
merge_sort100.csv		merge_sort100.csv
merge_sort1000.csv		merge_sort1000.csv
merge_sort1E+06.csv		merge_sort1E+06.csv
merge_sort1E+07.csv		merge_sort1E+07.csv
quick_sort1000.csv		quick_sort1000.csv
sel_sort1000.csv		sel_sort1000.csv
	class linked_list():
	def __init__(self, contents=[], first=None):
	self.first = linked_list.__node(None,first)
	class __node():
	def __init__(self, item, next=None):
	self.item = item
	self.next = next