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

Introduction

In this tutorial, we will explore the concept of insertion sort, a simple and intuitive sorting algorithm used in computer science. Understanding insertion sort is key for grasping more complex sorting techniques and computer science concepts. This guide will break down the insertion sort process step-by-step, making it easy to implement and understand.

Step 1: Understand the Basics of Insertion Sort

• Insertion sort builds a sorted array one element at a time.
• It works similarly to how you might sort playing cards in your hands.
• The algorithm divides the list into a sorted and an unsorted part.
• Elements from the unsorted part are picked and placed at the correct position in the sorted part.

Step 2: Visualize the Process

• Imagine you have an array: [5, 2, 9, 1, 5, 6].
• Start with the second element (2) and compare it to the first (5).
• Since 2 is smaller, move 5 to the right and insert 2 at the beginning.
• The array now looks like: [2, 5, 9, 1, 5, 6].

Step 3: Implementing Insertion Sort in Pseudocode

Here’s a simple pseudocode to implement insertion sort:

function insertionSort(array):
    for i from 1 to length(array) - 1:
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key:
            array[j + 1] = array[j]
            j = j - 1
        array[j + 1] = key

• The key is the element to be positioned.
• The inner loop shifts elements to the right to make space for the key.

Step 4: Practice the Algorithm

• Try implementing the pseudocode in your preferred programming language (e.g., Python, Java).
• Here is an example in Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Example usage
arr = [5, 2, 9, 1, 5, 6]
insertion_sort(arr)
print(arr)

Step 5: Analyze the Complexity

• Time Complexity:
  • Best case: O(n) when the array is already sorted.
  • Average and worst case: O(n²) for random or reverse-sorted arrays.
• Space Complexity: O(1) since it sorts in place.

Conclusion

Insertion sort is a straightforward algorithm that is easy to understand and implement. It is particularly useful for small datasets or nearly sorted arrays. To deepen your understanding, try implementing the algorithm in different programming languages or explore variations of sorting algorithms. Happy coding!