7.6 - ArrayLists, Sorting

Selection Sort.

  • The one of the easiest sorts to demonstrate.
  • The selection sort identifies either the maximum or minimum of the compared values and iterates over the structure checking if the item stored at the index matches that condition, if so, it will swap the value stroed at that index and continue.
  • This implementation uses a helper method to perform the swap operation since variables can hold only one value at a time!!!

Let’s use this array as an example: arr[] = {64, 25, 12, 22, 11}

picture 1 for selection sortin picture 2 for selection sortin picture 3 for selection sortin picture 4 for selection sortin picture 5 for selection sortin

College Board Example code below…

public class SelectionSort {
    public static void main(String[] args) {
        int[] numbers = {64, 25, 12, 22, 11};  // Example array of numbers

        // Perform selection sort
        for (int outerLoop = 0; outerLoop < numbers.length - 1; outerLoop++) {
            // Start by assuming the current item is the smallest
            int minIndex = outerLoop;

            // Check the rest of the array for anything smaller
            for (int inner = outerLoop + 1; inner < numbers.length; inner++) {
                // If you find something smaller, update the index
                if (numbers[inner] < numbers[minIndex]) {
                    minIndex = inner;
                }
            }

            // If the smallest item isn’t already in the right place, swap them
            if (minIndex != outerLoop) {
                // Swap numbers[outerLoop] and numbers[minIndex]
                int temp = numbers[outerLoop];
                numbers[outerLoop] = numbers[minIndex];
                numbers[minIndex] = temp;
            }
        }

        // Print the sorted array
        System.out.println("Sorted array:");
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }
}

SelectionSort.main(null);


Sorted array:
11 12 22 25 64

How does the swapping actualy happen?

  • We use swap-item mothod.

Swap Algorithm

private void swapItems(int firstIndex, int secondIndex, Object[] arrayOfStuff)
{
    // **thirdHand** temporarily holds the value from firstIndex so it doesn't get lost during the swap
    Object thirdHand = arrayOfStuff[firstIndex];
    
    // Move the value from secondIndex to firstIndex
    arrayOfStuff[firstIndex] = arrayOfStuff[secondIndex];
    
    // Place the value that was originally at firstIndex (stored in thirdHand) into secondIndex
    arrayOfStuff[secondIndex] = thirdHand;
}
// First you will see the three parameters as you can see below↓↓↓
// **The firstIndex** = The index of the first item to be swapped.
// **The secondIndex** = The index of the second item to be swapped.
// **arrayOfStuff** = The array where the swapping takes place.

Some common questions:

Can an enhanced for loop be used?

  • Answer: No, The Selection Sort algorithm needs to know the index of the item it is working with.

    How does the swap occur?

  • Answer: A third variable is needed to temporarily hold on to the swapped value from the array since variables can only hold one thing at a time.





Inserting Sort

  • The insertion sort is characterized by building a sorted structure as it proceeds. It inserts each value it finds at the appropriate location in the data structure. This is often accomplished by using a while loop as the inner loop.

picture 1 for inserting sortin

  • Consider an array having elements : {23, 1, 10, 5, 2}

initial:

  • Current element is 23
  • The first element in the array is assumed to be sorted.
  • The sorted part until 0th index is : [23]

First Pass:

  • Compare 1 with 23 (current element with the sorted part).
  • Since 1 is smaller, insert 1 before 23 .
  • The sorted part until 1st index is: [1, 23]

Second Pass:

  • Compare 10 with 1 and 23 (current element with the sorted part).
  • Since 10 is greater than 1 and smaller than 23 , insert 10 between 1 and 23 .
  • The sorted part until 2nd index is: [1, 10, 23]

Third Pass:

  • Compare 5 with 1 , 10, and 23 (current element with the sorted part).
  • Since 5 is greater than 1 and smaller than 10 , insert 5 between 1 and 10
  • The sorted part until 3rd index is : [1, 5, 10, 23]

Fourth Pass:

  • Compare 2 with 1, 5, 10 , and 23 (current element with the sorted part).
  • Since 2 is greater than 1 and smaller than 5 insert 2 between 1 and 5 .
  • The sorted part until 4th index is: [1, 2, 5, 10, 23]

Final Array:

  • The sorted array is: [1, 2, 5, 10, 23]

College Board Example code below…

import java.util.ArrayList;

public class InsertionSortExample {

    // Method to perform Insertion Sort on the list
    public static void insertionSort(ArrayList<Integer> randomList) {
        // Loop through each element in the list starting from the second element
        // (The first element is already considered sorted)
        for (int outer = 1; outer < randomList.size(); outer++) {
            
            // 'tested' is the current element we're trying to place in the correct position
            int tested = randomList.get(outer);
            
            // 'inner' represents the index of the last element in the sorted portion of the list
            int inner = outer - 1;

            // Move elements in the sorted part of the list to the right
            // until we find the correct position for 'tested'
            while (inner >= 0 && randomList.get(inner) > tested) {
                // Shift the element one position to the right to make space
                randomList.set(inner + 1, randomList.get(inner));
                inner--; // Move the 'inner' pointer to the left
            }

            // Place the 'tested' element in its correct position
            randomList.set(inner + 1, tested);
        }
    }

    public static void main(String[] args) {
        // Create an ArrayList to store the integers we want to sort
        ArrayList<Integer> randomList = new ArrayList<>();

        // Adding elements {23, 1, 10, 5, 2} to the list
        randomList.add(23);
        randomList.add(1);
        randomList.add(10);
        randomList.add(5);
        randomList.add(2);

        // Print the original list before sorting
        System.out.println("Original list: " + randomList);

        // Call the insertionSort method to sort the list
        insertionSort(randomList);

        // Print the sorted list after the insertion sort is completed
        System.out.println("Sorted list: " + randomList);
    }
}

InsertionSortExample.main(null);

Original list: [23, 1, 10, 5, 2]
Sorted list: [1, 2, 5, 10, 23]

Another Example…

6th PopCorn - Hack

Problem: Sort the Ducks!

You have a list of ducks, and each duck has a name and weight. Your task is to sort these ducks by weight in ascending order.

Choose either Selection Sort or Insertion Sort to do the sorting.

Example:

Given this list:

  • Duck A (4.5 kg)
  • Duck B (2.1 kg)
  • Duck C (5.0 kg)
  • Duck D (1.9 kg)

After sorting, the output should be:

  • Duck D (1.9 kg)
  • Duck B (2.1 kg)
  • Duck A (4.5 kg)
  • Duck C (5.0 kg)

You can use this class for the ducks:

class DebugDuck implements Comparable<DebugDuck> {
    String name;
    double weight;

    public DebugDuck(String name, double weight) {
        this.name = name;
        this.weight = weight;
    }

    @Override
    public int compareTo(DebugDuck other) {
        return Double.compare(this.weight, other.weight);
    }

    @Override
    public String toString() {
        return name + " (" + weight + " kg)";
    }
}

Task:

  • Implement either sorting algorithm to sort the ducks by weight.
  • Print the sorted list.