What techniques can you use to sort data in Python without built-in methods?

1 Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. In Python, you can implement Bubble Sort by using nested loops. The outer loop runs until no more swaps are needed, while the inner loop compares each pair of adjacent elements and swaps them using a temporary variable if they are out of order.

2 Insertion Sort

Insertion Sort builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it provides an intuitive way to sort a list by taking one element from the input data and finding its correct position in the sorted list. In Python, this can be done by iterating through the list, and for each element, shifting the greater elements of the list to the next position to make space for the unsorted element.

3 Selection Sort

Selection Sort is a straightforward algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front of the list, and a sublist of the remaining unsorted items. On each iteration, the smallest (or largest, depending on the desired order) unsorted element is selected and swapped with the leftmost unsorted element. The sublist of sorted items grows with each iteration. In Python, this translates to nested loops where the inner loop finds the minimum element and the outer loop places it into the correct position.

4 Merge Sort

Merge Sort is an efficient, general-purpose, comparison-based sorting algorithm. It divides the unsorted list into n sublists, each containing one element (a list of one element is considered sorted), then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining. To implement Merge Sort in Python, you need a recursive function that splits the list and another helper function that will merge the sorted pieces back together.

5 Quick Sort

Quick Sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. Implementing Quick Sort in Python involves choosing a pivot and then moving all elements smaller than the pivot to the left and all larger elements to the right, before recursively sorting the sub-arrays.

6 Heap Sort

Heap Sort is a comparison-based sorting technique based on a binary heap data structure. It's similar to selection sort where we first find the maximum element and place it at the end. We repeat the same process for the remaining elements. A binary heap is a complete binary tree where items are stored in a special order such that the value in a parent node is greater (in a max heap) or smaller (in a min heap) than the values in its two children nodes. In Python, Heap Sort can be implemented by first building a max heap from the input data, and then repeatedly extracting the largest element from the heap and rebuilding the heap.

7 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?