Big O

Big O is a mathematical notation to show the limiting behavior of a function when the argument is going toward a value or infinity.

In CS, we use it to describe the performance of an algorithm in terms of time and space.

Big O notation will give us an upper bound on the growth rate of a function, allowing us to compare the efficiency of different algorithms.

Selection Sort

Sorts arrays by repeatedly finding the minimum element from the unsorted part and putting it at the beginning.

Step 1: Array arr with N size

int[] arr = {10, 30, 15, 5};

Step 2: Initialise i = 0

Step 3: If(i < N-1), Check for any element arr[j] where j > i and arr[j] < arr[i], then Swap arr[i] and arr[j]

i = 0, assume arr[0] = 10 is the minimum
- 10 < 30, 10 remains the minimum
- 10 < 15, 10 remains the minimum
- 10 > 5, so 5 is the new minimum
  Swap 10 and 5 -> {5, 30, 15, 10}
  {5} is considered sorted
i = 1, assume arr[1] = 30 is the minimum
- 30 > 15, minimum value = 15
- 15 > 10, minimum value = 10, no more values
  Swap arr[1] with arr[3]
  New array is {5, 10, 15, 30}
  {5, 10} is considered sorted
  {15, 30} is unsorted
i = 2, assume arr[2] = 15 is the minimum
- 15 < 30, so the array is sorted
  Fully sorted array = {5, 10, 15, 30}

Step 4: i = i + 1 and Goto Step 3

Step 5: Exit

Fully sorted array = {5, 10, 15, 30}

Selection Sort Big O

Let N be the number of integers in an array

Each iteration in an algorithm leads to a new comparison made. For example, the first iteration will be (n-1) comparisions, 2nd will be (n-2), and on till the last iteration which will be 1.

number of comparisions = (n-1) + (n-2) + (n-3) + … + 1 = n(n-1)/2 = n^2

Time complexity for selection sort will be O(n^2)

Time complexity cases for selection sort:

Best case: when array is already sorted (algorithm does not need to make any changes, low time)

Avg-case: elements are randomized (takes a bit of time for algorithm to sort)

Worst-case: elements are in descending order but algorithm is trying to sort into ascending order (algorithm will go one by one to compare values resulting in the highest possible time for the algorithm to sort)

Code Example

import java.util.Arrays;

class GfG {

    static void selectionSort(int[] arr){
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
          
            // Assume the current position holds
            // the minimum element
            int min_idx = i;

            // Iterate through the unsorted portion
            // to find the actual minimum
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                  
                    // Update min_idx if a smaller element
                    // is found
                    min_idx = j;
                }
            }

            // Move minimum element to its
            // correct position
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
            printArray(arr);           
        }
    }

    static void printArray(int[] arr){
        for (int val : arr) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
  
    public static void main(String[] args){
        int[] arr = { 64, 25, 12, 22, 11 };

        System.out.print("Original array: ");
        printArray(arr);

        selectionSort(arr);

        System.out.print("Sorted array: ");
        printArray(arr);
    }
}

GfG.main(new String[]{});

Original array: 64 25 12 22 11 
11 25 12 22 64 
11 12 25 22 64 
11 12 22 25 64 
11 12 22 25 64 
Sorted array: 11 12 22 25 64 

Insertion Sort

Sorts arrays by repeatedly taking an element from the unsorted part and inserting it into the correct position in the sorted part.

Step 1: Array arr with N size

int[] arr = {10, 30, 15, 5};

Step 2: Initialise i = 1

Step 3: If(i < N), Check for the position to insert arr[i] in the sorted part (arr[0] to arr[i-1])

i = 1, assume arr[1] = 30 is the element to be inserted.
- Compare arr[1] with arr[0] (10): 30 > 10, no shift needed.
  Sorted array: {10, 30}
i = 2, assume arr[2] = 15 is the element to be inserted.
- Compare arr[2] with arr[1] (30): 15 < 30, so shift arr[1] to the right (arr[1] = 30).
- Now compare arr[2] with arr[0] (10): 15 > 10, insert 15 after 10.
  New array: {10, 15, 30, 5}
  {10, 15} is considered sorted.
i = 3, assume arr[3] = 5 is the element to be inserted.
- Compare arr[3] with arr[2] (30): 5 < 30, so shift arr[2] to the right (arr[2] = 30).
- Now compare arr[3] with arr[1] (15): 5 < 15, shift arr[1] to the right (arr[1] = 15).
- Now compare arr[3] with arr[0] (10): 5 < 10, shift arr[0] to the right (arr[0] = 10).
  Insert 5 at arr[0].
  New array: {5, 10, 15, 30}
  {5, 10, 15} is considered sorted.

Step 4: i = i + 1 and Goto Step 3

Step 5: Exit

Fully sorted array = {5, 10, 15, 30}

Insertion Sort Big O

Let N be the number of integers in an array

Each iteration in an algorithm leads to a new comparison made. For example, the first iteration will be (n-1) comparisions, 2nd will be (n-2), and on till the last iteration which will be 1.

number of comparisions = (n-1) + (n-2) + (n-3) + … + 1 = n(n-1)/2 = n^2

Time complexity for selection sort will be O(n^2)

Time complexity cases for selection sort:

Best case: when array is already sorted (algorithm does not need to make any changes, low time)

Avg-case: elements are randomized (takes a bit of time for algorithm to sort)

Worst-case: elements are in reversed order (each element needs to be compared and swapped with every preceding element, maximum possible time for algorithm to work)

Code Example (GfG)

public class InsertionSort {
    /* Function to sort array using insertion sort */
    void sort(int arr[])
    {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
            printArray(arr);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");

        System.out.println();
    }

    // Driver method
    public static void main(String args[])
    {
        int arr[] = { 12, 11, 13, 5, 6 };

        InsertionSort ob = new InsertionSort();
        ob.sort(arr);

        printArray(arr);
    }
}
InsertionSort.main(new String[]{});

Homework:

Part 1: Write your own

a. Selection sort, and sort an array in descending order
b. Insertion sort, and sort an array in ascending order

Submissions that directly copy examples given in the lesson material will not be accepted.

Part 2: Time Complexity Exercise

Write Java functions for Selection and Insertion Sort (You may use your code or modified parts of your code from part 1)
Ensure that each function records the time taken to sort the arrays (will be given below)
Record time taken to sort each array with each sorting algorithm
Answer the following questions
- Which algorithm performed better for Array A? Why?
- Which sorting algorithm beformed better for Array B? Why?
- When is it best to use each sorting algorthim? (think about how sorted a dataset is, the size of a data set, etc.)
  Arrays
- int[] arrayA = {29, 10, 14, 37, 13};
- int[] arrayB = {1, 2, 5, 4, 3, 6, 7, 8, 9, 10};

// Descending Selection Sort

// Ascending Insertion Sort

//Part 2 Comparing the two algorithms Time Complexity