How To Sort An Array In Python Without Sort Function

In this tutorial, we will learn how to sort an array in Python without using the built-in sort function. You’ll see step-by-step how to implement two popular sorting algorithms: Bubble Sort and Selection Sort.

These methods will help you to understand the basic concepts of sorting and also provide a foundation for learning other advanced sorting techniques in the future.

Step 1: Understand Bubble Sort

Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the array and comparing each pair of adjacent elements. If the elements are in the incorrect order, they are swapped. This process continues until the entire array is sorted.

This is a visualization of the Bubble Sort process:

[5, 2, 8, 3, 1]

Pass 1:

  • Compare 5 and 2: [2, 5, 8, 3, 1]
  • Compare 5 and 8: [2, 5, 8, 3, 1]
  • Compare 8 and 3: [2, 5, 3, 8, 1]
  • Compare 8 and 1: [2, 5, 3, 1, 8]

Pass 2:

  • Compare 2 and 5: [2, 5, 3, 1, 8]
  • Compare 5 and 3: [2, 3, 5, 1, 8]
  • Compare 5 and 1: [2, 3, 1, 5, 8]

Pass 3:

  • Compare 2 and 3: [2, 3, 1, 5, 8]
  • Compare 3 and 1: [2, 1, 3, 5, 8]

Pass 4:

  • Compare 2 and 1: [1, 2, 3, 5, 8]

The final sorted array is: [1, 2, 3, 5, 8]

Step 2: Understand Selection Sort

Selection Sort is another simple sorting algorithm that works by selecting the smallest (or largest) element from the remaining unsorted portion of the array and placing it at the correct location. Once an element has been placed at the correct location, it is considered sorted.

This is a visualization of the Selection Sort process:

[5, 2, 8, 3, 1]

Pass 1:

  • Find the minimum element from index 0 to the end: [1, 2, 8, 3, 5]
  • Swap the minimum element (1) with the element at index 0: [1, 2, 8, 3, 5]

Pass 2:

  • Find the minimum element from index 1 to the end: [1, 2, 8, 3, 5]
  • Swap the minimum element (2) with the element at index 1: [1, 2, 8, 3, 5]

Pass 3:

  • Find the minimum element from index 2 to the end: [1, 2, 3, 8, 5]
  • Swap the minimum element (3) with the element at index 2: [1, 2, 3, 8, 5]

Pass 4:

  • Find the minimum element from index 3 to the end: [1, 2, 3, 5, 8]
  • Swap the minimum element (5) with the element at index 3: [1, 2, 3, 5, 8]

The final sorted array is: [1, 2, 3, 5, 8]

Each pass of the selection sort algorithm finds the minimum element from the unsorted portion of the array and swaps it with the element at the beginning of the unsorted portion. This process is repeated until the entire array is sorted.

Step 3: Implement Bubble Sort in Python

To implement Bubble Sort in Python, follow these steps:

  1. Create a function called bubble_sort that takes an array as an argument.
  2. Initialize a variable swapped to True.
  3. Create a while loop that continues as long as swapped is True.
  4. Set swapped to False inside the loop.
  5. Loop through the array, excluding the last element in each iteration.
  6. In each iteration, compare the current element and the next element.
  7. If the two elements are in the wrong order, swap them and set swapped to True.

Here’s the Python code for Bubble Sort:

1
2
3
4
5
6
7
8
9
def bubble_sort(arr):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
    return arr

Step 4: Implement Selection Sort in Python

To implement Selection Sort in Python, follow these steps:

  1. Create a function called selection_sort that takes an array as an argument.
  2. Loop through the array, excluding the last element.
  3. In each iteration, find the index of the minimum element in the remaining unsorted array.
  4. Swap the current element with the found minimum element if necessary.

Here’s the Python code for Selection Sort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def bubble_sort(arr):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
    return arr
 
 
def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_index = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr
 
 
arr = [5, 2, 8, 3, 1]
 
sorted_arr_bubble = bubble_sort(arr)
print(sorted_arr_bubble)
 
sorted_arr_selection = selection_sort(arr)
print(sorted_arr_selection)

Output

[1, 2, 3, 5, 8]
[1, 2, 3, 5, 8]

Conclusion

In this tutorial, you learned how to sort an array in Python using two popular sorting algorithms: Bubble Sort and Selection Sort.

These algorithms provide a basis for understanding other advanced sorting techniques and help you become familiar with the process of sorting an array.

Feel free to try these methods on different arrays to get a better understanding of how they work and to practice your sorting skills.