Sorting algorithms arrange elements in a specific order. Understanding these fundamental algorithms is essential for any programmer.
Stability in Sorting Algorithms
A sorting algorithm is stable if it maintains the relative order of equal elements. When a stable sort is applied to elements with equal keys, their original sequence is preserved.
Bubble Sort
Bubble Sort is a straightforward comparison-based algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process continues until no swaps are needed, indicating the list is sorted. The name comes from smaller elements "bubbling" to the top of the list.
Algorithm steps:
- Compare each pair of adjacent elements
- Swap if the first element is greater than the second (for ascending order)
- After each pass, the largest unsorted element moves to its correct position
- Repeat until no swaps occur
def bubble_sort(arr):
n = len(arr)
for pass_num in range(n - 1):
swapped = False
for i in range(n - 1 - pass_num):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
if not swapped:
break
if __name__ == '__main__':
data = [5, 4, 3, 2, 1]
bubble_sort(data)
print(data)
# Worst case: O(n²)
# Best case: O(n)
# Stable: Yes
Selection Sort
Selection Sort divides the input into a sorted and unsorted region. The algorithm repeatedly selects the minimum element from the unsorted region and moves it to the sorted region.
Algorithm steps:
- Find the minimum element in the unsorted portion
- Swap it with the first unsorted element
- Expand the sorted region by one
- Repeat until the entire array is sorted
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
if __name__ == '__main__':
data = [64, 25, 12, 22, 11]
selection_sort(data)
print(data)
# Worst case: O(n²)
# Best case: O(n²)
# Stable: No
Insertion Sort
Insertion Sort builds the final sorted array one item at a time. It iterates through an array, removing one element per iteration and finding the place the element belongs in the array.
Algorithm steps:
- Start with the second element
- Compare it with elements before it
- Shift elements that are greater than the current element to the right
- Insert the current element into its correct position
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
if __name__ == '__main__':
data = [12, 11, 13, 5, 6]
insertion_sort(data)
print(data)
# Worst case: O(n²)
# Best case: O(n)
# Stable: Yes
Quick Sort
Quick Sort is a divide-and-conquer algorithm that works by selecting a pivot element and partitioning the array around the pivot. Elements smaller than the pivot go to the left, and elements greater go to the right. The process recurses on both partitions.
Algorithm steps:
- Select a pivot element
- Partition: reorder elements so those smaller than pivot are on the left, greater on the right
- Recursively apply the same logic to left and right partitions
def quick_sort(arr, low, high):
if low >= high:
return
pivot = arr[low]
left = low
right = high
while left < right:
while left < right and arr[right] >= pivot:
right -= 1
arr[left] = arr[right]
while left < right and arr[left] < pivot:
left += 1
arr[right] = arr[left]
arr[left] = pivot
quick_sort(arr, low, left - 1)
quick_sort(arr, left + 1, high)
if __name__ == '__main__':
data = [10, 7, 8, 9, 1, 5]
quick_sort(data, 0, len(data) - 1)
print(data)
Binary Search
Binary Search efficiently finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half.
def binary_search(arr, target):
if len(arr) == 0:
return False
mid = len(arr) // 2
if target == arr[mid]:
return True
elif target > arr[mid]:
return binary_search(arr[mid + 1:], target)
else:
return binary_search(arr[:mid], target)
if __name__ == '__main__':
sorted_data = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(sorted_data, 7))
print(binary_search(sorted_data, 6))
Queue
A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front.
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
if __name__ == '__main__':
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.size())
print(q.is_empty())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
Deque (Double-Ended Queue)
A Deque allows insertion and removal of elements from both ends. It can function as both a queue and a stack.
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
return self.items.pop(0)
def remove_rear(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
if __name__ == '__main__':
dq = Deque()
dq.add_rear(1)
dq.add_rear(2)
print(dq.remove_front())
print(dq.remove_front())
Stack
A Stack is a LIFO (Last-In-First-Out) data structure where the last element added is the first one to be removed.
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items) - 1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
if __name__ == '__main__':
s = Stack()
print(s.is_empty())
s.push(1)
s.push(2)
s.push(3)
print(s.is_empty())
print(s.size())
print(s.pop())
print(s.peek())
print(s.pop())
print(s.pop())
Singly Linked List
A Linked List consists of nodes where each node contains a data field and a referenec to the next node in the list.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def length(self):
count = 0
current = self.head
while current:
count += 1
current = current.next
return count
def traverse(self):
current = self.head
while current:
print(current.data, end=' ')
current = current.next
print()
def add_at_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def append(self, data):
if self.is_empty():
self.add_at_head(data)
return
current = self.head
while current.next:
current = current.next
current.next = Node(data)
def insert_at(self, position, data):
if position <= 0:
self.add_at_head(data)
elif position >= self.length():
self.append(data)
else:
current = self.head
index = 0
while index < position - 1:
current = current.next
index += 1
new_node = Node(data)
new_node.next = current.next
current.next = new_node
def remove(self, data):
current = self.head
previous = None
while current:
if current.data == data:
if previous is None:
self.head = current.next
else:
previous.next = current.next
return
previous = current
current = current.next
def search(self, data):
current = self.head
while current:
if current.data == data:
return True
current = current.next
return False
if __name__ == '__main__':
ll = LinkedList()
print(ll.is_empty())
print(ll.length())
ll.add_at_head(5)
ll.add_at_head(2)
ll.add_at_head(1)
print(ll.length())
ll.traverse()
ll.append(3)
ll.traverse()
ll.insert_at(2, 4)
ll.traverse()
print(ll.search(3))
print(ll.search(6))
ll.remove(5)
ll.traverse()
Doubly Linked List
A Doubly Linked List has nodes that contain references to both the next and previous nodes, allowing traversal in both directions.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def length(self):
count = 0
current = self.head
while current:
count += 1
current = current.next
return count
def traverse(self):
current = self.head
while current:
print(current.data, end=' ')
current = current.next
print()
def add_at_head(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
return
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
def append(self, data):
if self.is_empty():
self.add_at_head(data)
return
current = self.head
while current.next:
current = current.next
new_node = Node(data)
current.next = new_node
new_node.prev = current
def insert_at(self, position, data):
if position <= 0:
self.add_at_head(data)
elif position >= self.length():
self.append(data)
else:
current = self.head
index = 0
while index < position - 1:
current = current.next
index += 1
new_node = Node(data)
new_node.next = current.next
current.next.prev = new_node
current.next = new_node
new_node.prev = current
def remove(self, data):
current = self.head
while current:
if current.data == data:
if current.prev is None:
self.head = current.next
else:
current.prev.next = current.next
if current.next:
current.next.prev = current.prev
return
current = current.next
def search(self, data):
current = self.head
while current:
if current.data == data:
return True
current = current.next
return False
if __name__ == '__main__':
dll = DoublyLinkedList()
print(dll.is_empty())
print(dll.length())
dll.add_at_head(5)
dll.add_at_head(2)
dll.add_at_head(1)
print(dll.length())
dll.traverse()
dll.append(3)
dll.traverse()
dll.insert_at(2, 4)
dll.traverse()
print(dll.search(3))
print(dll.search(6))
dll.remove(5)
dll.traverse()
Circular Linked List
In a Circular Linked List, the last node points back to the first node, forming a circle. This implementation covers a singly circular linked list.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def length(self):
if self.is_empty():
return 0
count = 1
current = self.head
while current.next != self.head:
count += 1
current = current.next
return count
def traverse(self):
if self.is_empty():
return
current = self.head
print(current.data, end=' ')
while current.next != self.head:
current = current.next
print(current.data, end=' ')
print()
def add_at_head(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
new_node.next = new_node
return
current = self.head
while current.next != self.head:
current = current.next
new_node.next = self.head
self.head = new_node
current.next = self.head
def append(self, data):
if self.is_empty():
self.add_at_head(data)
return
current = self.head
while current.next != self.head:
current = current.next
new_node = Node(data)
current.next = new_node
new_node.next = self.head
def insert_at(self, position, data):
if position <= 0:
self.add_at_head(data)
elif position >= self.length():
self.append(data)
else:
current = self.head
index = 0
while index < position - 1:
current = current.next
index += 1
new_node = Node(data)
new_node.next = current.next
current.next = new_node
def remove(self, data):
if self.is_empty():
return
current = self.head
previous = None
while current.next != self.head:
if current.data == data:
if previous is None:
tail = self.head
while tail.next != self.head:
tail = tail.next
self.head = current.next
tail.next = self.head
else:
previous.next = current.next
return
previous = current
current = current.next
if current.data == data:
if previous is None:
self.head = None
else:
previous.next = self.head
def search(self, data):
if self.is_empty():
return False
current = self.head
if current.data == data:
return True
while current.next != self.head:
current = current.next
if current.data == data:
return True
return False
if __name__ == '__main__':
cll = CircularLinkedList()
print(cll.is_empty())
print(cll.length())
cll.add_at_head(5)
cll.add_at_head(2)
cll.add_at_head(1)
print(cll.length())
cll.traverse()
cll.append(3)
cll.traverse()
cll.insert_at(2, 4)
cll.traverse()
print(cll.search(3))
print(cll.search(1))
print(cll.search(6))
cll.remove(5)
cll.remove(3)
cll.traverse()