Back

Activity 5.8 — Sorting Algorithms

divider

Introduction

Activity 5.8

Selection Sort & Insertion Sort

What does sorting mean?

// What does "sorted ascending" mean?
// Each element is <= the next element.


int[] nums = {2, 4, 7, 9};

Selection Sort

// Selection sort idea:
// 1) Find smallest element
// 2) Swap it into position 0
// 3) Repeat for the rest of the array
// Selection sort outer loop
for (int i = 0; i < arr.length - 1; i++)
{
    int minIndex = i;
    // find smallest from i to end
}

Insertion Sort

// Insertion sort idea:
// Build a sorted section on the left.
// Insert each new value into correct position.
// Insertion sort outer loop
for (int i = 1; i < arr.length; i++)
{
    int key = arr[i];
    int j = i - 1;


    // shift larger elements right
}

Library Sorting

// Sorting using library
import java.util.Arrays;


Arrays.sort(arr);
  • Preferred in real programs.
  • You should still understand how sorting works.

Key Takeaways

  • Sorting rearranges elements in place.
  • Selection sort uses repeated minimum selection.
  • Insertion sort builds a sorted section.
  • Nested loops are essential.

'F' → Fullscreen

Objectives

  • icon Trace selection sort step-by-step.
  • icon Implement insertion sort.
  • icon Compare manual sorting with Arrays.sort.
divider

Activity Tasks

  • icon Create a project named Activity5_8_Sorting.
  • icon Complete Tasks 1–3.

Figures: Reference Implementations

Figure 1 — Selection Sort
// Figure 1 — Selection Sort
public static void selectionSort(int[] arr)
{
    for (int i = 0; i < arr.length - 1; i++)
    {
        int minIndex = i;


        for (int j = i + 1; j < arr.length; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }


        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}
Figure 2 — Insertion Sort
// Figure 2 — Insertion Sort
public static void insertionSort(int[] arr)
{
  for (int i = 1; i < arr.length; i++)
  {
    int key = arr[i];
    int j = i;


    while (j > 0 && key < arr[j - 1])
    {
      arr[j] = arr[j - 1];
      j--;
    }


    arr[j] = key;
  }
}

Task 1: Trace Selection Sort

Task 1 — Selection Sort Trace
public class Program
{
    public static void main(String[] args)
    {
        // Task 1 — Trace Selection Sort
        //
        // Trace the array after each outer loop pass.
        // Use this array:
        //
        // {7, 3, 8, 1}


        int[] nums = {7, 3, 8, 1};


        selectionSort(nums);


        printArray(nums);
    }


    public static void selectionSort(int[] arr)
    {
        for (int i = 0; i < arr.length - 1; i++)
        {
            int minIndex = i;


            for (int j = i + 1; j < arr.length; j++)
            {
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }


            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;


            // Add a print here to observe progress
        }
    }


    public static void printArray(int[] arr)
    {
        for (int v : arr)
        {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

Task 2: Implement Insertion Sort

Task 2 — Insertion Sort
public class Program
{
    public static void main(String[] args)
    {
        // Task 2 — Implement Insertion Sort
        //
        // 1) Copy insertionSort from the figure.
        // 2) Test on {5, 2, 9, 1, 7}
        // 3) Print before and after.


        int[] nums = {5, 2, 9, 1, 7};


        System.out.println("Before:");
        printArray(nums);


        insertionSort(nums);


        System.out.println("After:");
        printArray(nums);
    }


    public static void insertionSort(int[] arr)
    {
      for (int i = 1; i < arr.length; i++)
      {
          int key = arr[i];
          int j = i;


          while (j > 0 && key < arr[j - 1])
          {
              arr[j] = arr[j - 1];
              j--;
          }


          arr[j] = key;
      }
    }


    public static void printArray(int[] arr)
    {
        for (int v : arr)
        {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

Task 3: Compare with Arrays.sort

Task 3 — Arrays.sort Comparison
import java.util.Arrays;


public class Program
{
    public static void main(String[] args)
    {
        // Task 3 — Compare with Arrays.sort
        //
        // 1) Create an array.
        // 2) Copy it.
        // 3) Sort one using selectionSort.
        // 4) Sort the other using Arrays.sort.
        // 5) Compare results.


        int[] nums = {10, 4, 7, 2, 9};


        int[] copy = Arrays.copyOf(nums, nums.length);


        selectionSort(nums);
        Arrays.sort(copy);


        System.out.println("Selection sort result:");
        printArray(nums);


        System.out.println("Arrays.sort result:");
        printArray(copy);
    }


    public static void selectionSort(int[] arr)
    {
        for (int i = 0; i < arr.length - 1; i++)
        {
            int minIndex = i;


            for (int j = i + 1; j < arr.length; j++)
            {
                if (arr[j] < arr[minIndex])
                {
                    minIndex = j;
                }
            }


            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }


    public static void printArray(int[] arr)
    {
        for (int v : arr)
        {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}
divider

Sample Output

Terminal window
Before:
5 2 9 1 7
After:
1 2 5 7 9


Selection sort result:
2 4 7 9 10
Arrays.sort result:
2 4 7 9 10
divider

Reflection

  1. How does selection sort choose the next element?
  2. How is insertion sort different from selection sort?
  3. When should you use Arrays.sort instead of writing your own sort?
divider

Submission

Submit your completed activity.

Activity Complete