Sorting Algorithms in Java: Basics and Examples. Practical Tasks

Nine hands-on exercises reinforce the algorithms from the course: sorting, computing an average, Fibonacci numbers, estimating complexity with Big O notation, swapping values, reversing an array, and searching for an element. Each task builds on a specific lesson and asks you to step through code in the debugger, fill in a trace table, or refine an implementation.

1. Debugging Bubble Sort

1. Create a table for any array where you log the values of i, j, and the current array state for each cycle of the Bubble Sort algorithm.
2. Use the debugger in your IDE.
3. For example, for the array 0 2 5 3 4:

   Debugging Steps

   i	j	Array State	Did if block run?
   0	4	0 2 5 3 4	-
   0	3	0 2 3 5 4	+
   0	2	0 2 3 5 4	-
   0	1	0 2 3 5 4	-
   1	4	0 2 3 4 5	+
   1	3	0 2 3 4 5	-
   1	2	0 2 3 4 5	-
   2	4	0 2 3 4 5	-
   2	3	0 2 3 4 5	-
   3	4	0 2 3 4 5	-
   4	-	0 2 3 4 5	-

2. Modify the Bubble Sort

1. Update the Bubble Sort program:
   a) Add early termination if no swaps were made in a pass.
   b) The current implementation "floats" the minimum element to the start of the array. Modify the program so that it pushes the minimum element to the end of the array (i.e., the inner for loop should iterate from start to end).

   public class BubbleSorter {
       public static void sort(int[] array) {
           for (int i = 0; i < array.length; i++) {
               for (int j = array.length - 1; j > i; j--) {
                   if (array[j - 1] > array[j]) {
                       int tmp = array[j - 1];
                       array[j - 1] = array[j];
                       array[j] = tmp;
                   }
               }
           }
       }
   }

3. Debugging Selection Sort

Repeat Task 1 using the Selection Sort algorithm.

1. Modify the Selection Sort – exclude the swap operation if the minimum element is already in the correct position.

   public class SelectionSorter {
       public static void sort(int[] array) {
           for (int i = 0; i < array.length; i++) {
               int pos = i;
               int min = array[i];
               for (int j = i + 1; j < array.length; j++) {
                   if (array[j] < min) {
                       pos = j;
                       min = array[j];
                   }
               }
               if (pos != i) {
                   array[pos] = array[i];
                   array[i] = min;
               }
           }
       }
   }

4. Find the Bug in an Average Calculation

Given the following method that is supposed to calculate the average of an int[] array:

public class AverageCalculator {
    public static double average(int[] array) {
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }
        int count = array.length;
        return sum / count;
    }
}

1. Run the method for the array {1, 2, 3, 4}. The expected result is 2.5, but the program returns 2. Use the debugger to find the cause by checking the result of sum / count before it is assigned to a double variable.
2. Fix the bug using the integer division section of the «Average Value of an Array in Java» lesson.
3. Add a check for an empty array (array.length == 0): the method should return 0 instead of throwing an ArithmeticException.

5. Compare Recursion and Iteration for Fibonacci Numbers

1. Take the recursive method and the loop-based method for computing Fibonacci numbers from the «Fibonacci Numbers in Java» lesson.
2. Measure the execution time (using System.currentTimeMillis() before and after the call) for n = 30, n = 35, and n = 40 for both implementations. Record the results in a table.

   Execution time, ms

   n	Recursion	Loop
   30
   35
   40

3. Explain the result: why does the recursive implementation slow down dramatically as n grows? Connect your answer to the O(2^n) versus O(n) complexity covered in the lesson.
4. Add memoization to the recursive method (cache already computed values in a HashMap<Integer, Long>) and repeat the measurement for n = 40.

6. Determine Algorithm Complexity from Code

For each method below, determine its Big O complexity based on the «Algorithm Complexity and Big O Notation» lesson, and justify your answer in one sentence.

// A
public static int first(int[] array) {
    return array[0];
}

// B
public static int sum(int[] array) {
    int s = 0;
    for (int x : array) {
        s += x;
    }
    return s;
}

// C
public static boolean hasDuplicate(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] == array[j]) {
                return true;
            }
        }
    }
    return false;
}

// D
public static int binarySearch(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

1. Fill in the table.

   Complexity of methods A–D

   Method	Big O
   A
   B
   C
   D

2. Check yourself: measure the execution time of the hasDuplicate method for arrays of 1,000, 10,000, and 100,000 elements and confirm that the growth matches your complexity estimate.

7. Prove That Swap Does Not Work on Primitives

1. Write the swap(int a, int b) method from the «How to Swap Variables in Java» lesson and call it on two local variables. Use the debugger (or print statements before and after the call) to confirm that the caller's variables did not change.
2. Explain why, based on how Java passes primitive parameters: by value, not by reference.
3. Write a swap(int[] array, int i, int j) method that swaps two array elements by index, and prove that this time the swap works: the reference parameter points to the same array, and it is the array's elements that change, not the parameter itself.
4. Use your swap method for arrays inside your own Bubble Sort or Selection Sort implementation instead of a manual temporary-variable swap.

8. Trace the Array Reversal Algorithm

1. Take the in-place array reversal method (two pointers, left and right) from the «Reverse an Array» lesson.
2. For the array {1, 2, 3, 4, 5}, fill in a step table like in Task 1, recording left, right, and the array state on every loop iteration.

   Array reversal steps

   left	right	Array State

3. Use the debugger to check how many loop iterations were needed for an array of 5 elements versus 6 elements, and explain the difference between even and odd array lengths.
4. Write a version of the method that does not mutate the original array but returns a new reversed array, and compare its space complexity with the in-place version.

9. Compare Linear and Binary Search

1. Take the linear search and binary search implementations from the «Search Algorithms» lesson.
2. Add a comparison counter (int comparisons) to both methods and print its value after the search finishes.
3. Create a sorted array of 100 elements and search for: the first element, the last element, and an element that is not in the array. Fill in the table with the number of comparisons for each case.

   Number of comparisons

   Target	Linear Search	Binary Search
   First element
   Last element
   Missing element

4. Explain why the number of comparisons in binary search barely changes as the array grows, while in linear search it grows proportionally. Connect your answer to the «Algorithm Complexity and Big O Notation» lesson.