Learn sorting & searching algorithms — visualize every step!
Al-Farabi Kazakh National University · Algorithms & Data StructuresA console-based Python application for managing contacts — but with a twist! It implements 4 sorting algorithms and 4 search algorithms, allowing you to compare their performance side-by-side and learn how they work.
Contacts are stored as a Python list of dictionaries: [ {'name': 'Alice', 'phone': '1234'}, ... ]. This simple structure makes it easy to demonstrate searching and sorting algorithms.
O(log n) ≈ 20 operations · O(n) ≈ 1 million · O(n log n) ≈ 20 million · O(n²) ≈ 1 trillion!
Scans every contact in the list from start to end until the target is found (or list ends). Simple but slow for large datasets.
The PhoneBook also supports BST search — contacts are inserted into a tree structure by name. Average lookup is O(log n), but can degrade to O(n) if the tree is unbalanced.
| Algorithm | Best | Average | Worst | Requires |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | Nothing |
| Binary Search | O(1) | O(log n) | O(log n) | Sorted data |
| BST Search | O(1) | O(log n) | O(n) | BST structure |
Repeatedly compares adjacent elements and swaps them if they're in the wrong order. Each pass "bubbles" the largest unsorted element to its correct position.
Finds the minimum element repeatedly and places it at the beginning of the unsorted portion. Always O(n²) — no best case optimization.
Divides the array in half recursively, sorts each half, then merges them back together. Always O(n log n) — guaranteed performance regardless of input!
Picks a pivot, partitions elements around it, then recursively sorts partitions. Average O(n log n), worst O(n²). Most commonly used in practice!
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
# Global list to store contacts contacts = [] def add_contact(name, phone): """Add a new contact. Time Complexity: O(n)""" if not name or not phone: print("Error: Name and phone cannot be empty.") return False # Linear Search for duplicates - O(n) for contact in contacts: if contact['name'].lower() == name.lower(): print(f"Error: Contact '{name}' already exists.") return False contacts.append({'name': name, 'phone': phone}) return True def remove_contact(name): """Remove a contact by name. Time Complexity: O(n)""" for i, contact in enumerate(contacts): if contact['name'].lower() == name.lower(): contacts.pop(i) return True return False def edit_contact(name, new_phone): """Edit a contact's phone number. Time Complexity: O(n)""" for contact in contacts: if contact['name'].lower() == name.lower(): contact['phone'] = new_phone return True return False
| Function | Complexity | Description |
|---|---|---|
| add_contact() | O(n) | Linear search for duplicates |
| remove_contact() | O(n) | Linear search to find contact |
| edit_contact() | O(n) | Linear search to find contact |
| linear_search() | O(n) | Must check every contact |
| binary_search() | O(log n) | Requires sorted list |
| bubble_sort() | O(n²) | Two nested loops |
| selection_sort() | O(n²) | Find minimum repeatedly |
| merge_sort() | O(n log n) | Divide and conquer |
| quick_sort() | O(n log n) | Partition by pivot |
| load_from_file() | O(n) | Read n contacts |
| save_to_file() | O(n) | Write n contacts |