Sorting Algorithms. Tasks
1. Debugging Bubble Sort
- 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. - Use the debugger in your IDE.
- 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
- 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 innerfor
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.
- 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; } } } }

Please log in or register to have a possibility to add comment.