Metode Sorting | Belajar SELECTION SORT Informatika | Berpikir Komputasional

Introduction

In this tutorial, we will explore the Selection Sort algorithm, a fundamental method for sorting data in computer science. This technique is particularly relevant for beginners learning computational thinking and algorithm design. By the end of this guide, you should have a clear understanding of how Selection Sort works and how to implement it.

Step 1: Understanding Selection Sort

Selection Sort is a simple sorting algorithm that divides the input list into two parts: the sorted part and the unsorted part. The algorithm repeatedly selects the smallest (or largest, depending on sorting order) element from the unsorted part and moves it to the end of the sorted part.

Key Characteristics

• Time Complexity: O(n²) in all cases (best, average, worst)
• Space Complexity: O(1) (in-place sorting)
• Stability: Not stable (equal elements may not maintain their original relative order)

Step 2: The Selection Sort Algorithm

Here’s how the Selection Sort algorithm works step-by-step:

1. Start with the first element as the minimum.
2. Compare this minimum with all other elements in the array.
3. If you find an element smaller than the current minimum, update the minimum.
4. After checking all elements, swap the minimum with the first element of the unsorted part.
5. Move the boundary between sorted and unsorted parts one element to the right.
6. Repeat the process for the rest of the array.

Example

Consider the array: [29, 10, 14, 37, 13]

• First Pass:

  • Minimum is 10. Swap 10 with 29.
  • Array becomes: [10, 29, 14, 37, 13]

• Second Pass:

  • Minimum is 13. Swap 13 with 29.
  • Array becomes: [10, 13, 14, 37, 29]

• Continue this process until the array is fully 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
        # Swap the found minimum element with the first element
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# Example usage
arr = [29, 10, 14, 37, 13]
sorted_arr = selection_sort(arr)
print("Sorted array:", sorted_arr)

Practical Tips

• Use Selection Sort for small datasets where simplicity is prioritized over efficiency.
• Avoid using Selection Sort for large datasets because of its O(n²) time complexity.

Conclusion

Selection Sort is a straightforward yet powerful algorithm for understanding the basics of sorting. By grasping how it works and being able to implement it in code, you are building a foundation for more complex sorting algorithms. Next, consider exploring other sorting algorithms, such as Bubble Sort or Quick Sort, to compare their efficiencies and use cases.