Informatika: Berpikir Komputasional : Sorting / Pengurutan: Teknik Selection Sort (Bahasa Indonesia)

Introduction

This tutorial provides a step-by-step guide to understanding and implementing the Selection Sort algorithm, a fundamental sorting technique in computer science. By mastering Selection Sort, you'll gain insights into basic algorithmic thinking and improve your problem-solving skills in programming.

Step 1: Understanding Selection Sort

Selection Sort is a simple comparison-based sorting algorithm that works by repeatedly selecting the minimum element from the unsorted portion of the list and moving it to the beginning. Here’s what you need to know:

• The algorithm divides the list into two parts: the sorted part and the unsorted part.
• It iteratively selects the smallest element from the unsorted part and swaps it with the first unsorted element.
• This process continues until the entire list is sorted.

Step 2: Step-by-Step Algorithm

To implement Selection Sort, follow these steps:

1. Start with the first element as the minimum.
2. Compare this minimum with the next element in the unsorted portion.
3. If a smaller element is found, update the minimum.
4. After checking all elements, swap the minimum element with the first unsorted element.
5. Move the boundary of the sorted and unsorted parts one element to the right.
6. Repeat steps 1 to 5 until the entire list is sorted.

Example

Consider the array: [64, 25, 12, 22, 11]

• First pass: Find the minimum (11), swap with 64 → [11, 25, 12, 22, 64]
• Second pass: Find the minimum (12), swap with 25 → [11, 12, 25, 22, 64]
• Third pass: Find the minimum (22), swap with 25 → [11, 12, 22, 25, 64]
• Fourth pass: The next minimum (25) is already in place → [11, 12, 22, 25, 64]
• Final pass: The last element (64) is already sorted.

Step 3: Implementing Selection Sort in Code

Here’s a simple implementation of Selection Sort in Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        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]
    return arr

# Example usage
array = [64, 25, 12, 22, 11]
sorted_array = selection_sort(array)
print(sorted_array)  # Output: [11, 12, 22, 25, 64]

Conclusion

Selection Sort is an excellent introductory algorithm for understanding sorting and algorithm design. While not the most efficient for large datasets due to its O(n^2) time complexity, it provides a clear framework for learning more complex sorting techniques. As a next step, consider exploring other sorting algorithms like Bubble Sort or Quick Sort for a deeper understanding of their efficiencies and use cases.