provided code: import java.util.Comparator; /** * Your implementation of various iterative sorting algorithms. */ public class Sorting { /** * Implement bubble sort. * * It should be:
provided code: import java.util.Comparator; /** * Your implementation of various iterative sorting algorithms. */ public class Sorting { /** * Implement bubble sort. * * It should be:
provided code: import java.util.Comparator; /** * Your implementation of various iterative sorting algorithms. */ public class Sorting { /** * Implement bubble sort. * * It should be:
/** * Your implementation of various iterative sorting algorithms. */ public class Sorting {
/** * Implement bubble sort. * * It should be: * in-place * stable * adaptive * * Have a worst case running time of: O(n^2) * And a best case running time of: O(n) * * NOTE: You should implement bubble sort with the last swap optimization. * * You may assume that the passed in array and comparator * are both valid and will never be null. * * @param <T> Data type to sort. * @param arr The array that must be sorted after the method runs. * @param comparator The Comparator used to compare the data in arr. */ public static <T> void bubbleSort(T[] arr, Comparator<T> comparator) { // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)! }
/** * Implement selection sort. * * It should be: * in-place * unstable * not adaptive * * Have a worst case running time of: O(n^2) * And a best case running time of: O(n^2) * * You may assume that the passed in array and comparator * are both valid and will never be null. * * @param <T> Data type to sort. * @param arr The array that must be sorted after the method runs. * @param comparator The Comparator used to compare the data in arr. */ public static <T> void selectionSort(T[] arr, Comparator<T> comparator) { // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)! }
/** * Implement insertion sort. * * It should be: * in-place * stable * adaptive * * Have a worst case running time of: O(n^2) * And a best case running time of: O(n) * * You may assume that the passed in array and comparator * are both valid and will never be null. * * @param <T> Data type to sort. * @param arr The array that must be sorted after the method runs. * @param comparator The Comparator used to compare the data in arr. */ public static <T> void insertionSort(T[] arr, Comparator<T> comparator) { // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)! } }
Transcribed Image Text:For this assignment you will be coding 3 different iterative sorts: bubble sort, insertion sort, and selection sort. In addition
to the requirements for each sort, the autograder will be looking at the number of comparisons made between elements to
test for efficiency.
For each sorting algorithm, you may assume that the array you are sorting will not contain null elements. You should also
assume that the array may contain any number of duplicate elements.
Your implementations should match what was taught in this course.
IMPORTANT:
• You will be given 5 attempts on this assignment, with a 30 minute cooldown between submissions.
• Please run your code before each submission to ensure that there are no formatting errors! If there are
formatting errors in your code, your code will not be graded and a submission attempt will be logged. For
more information, please review the Vocareum overview below.
Comparator
Each method will take in a Comparator, which is used to compare two elements. You must use this Comparator, as the
number of comparisons performed with it will be used when testing your assignment. The comparator is used as follows:
comparator.compare (A, B) will return:
• <0 if A is less than B
• > 0 if A is greater than B
• O if A is equal to B
Generic Methods
Most of the assignments is this course so far have utilized generics by incorporating them into the class
declaration. However, the rest of the assignments will have you implement various algorithms as static
methods in a utility class. Thus, the generics from here on will use generic methods instead of generic classes
(hence the <T> in each of the method headers and javadocs). This also means any helper methods you create
will also need to be static with the same <T> in the method header.
In-Place Sorts
The three sorting algorithms that you will be implementing are in-place sorts. This means that the items in the
array passed in should not get copied over to another data structure. Note that you can still create variables
that hold only one item. However, you should not create another data structure, such as an array or list, in the
method.
Stable Sorts
Some of the sorts below are stable sorts. This means that duplicates must remain in the same relative
positions after sorting as they were before sorting.
Adaptive Sorts
Some of the sorts below are adaptive sorts. This means that the algorithm takes advantage of existing order in
the input array. The algorithm can detect existing order in the input array and optimize its performance based
on that order.
Bubble Sort
Bubble sort should be in-place, stable, and adaptive. It should have a worst case running time of O(n²) and a
best case running time of O(n). Note: Implement bubble sort with the optimization where it utilizes the last
Transcribed Image Text:Bubble Sort
Bubble sort should be in-place, stable, and adaptive. It should have a worst case running time of O(n²) and a
best case running time of O(n). Note: Implement bubble sort with the optimization where it utilizes the last
swapped index. Remembering where you last swapped will enable some optimization for bubble sort. For
example, traversing the array from smaller indices to larger indices, if you remember the index of your last
swap, you know after that index, there are only the largest elements in order. Therefore, on the next iteration,
you start at the front but stop at the last swapped index. Make sure you only look at the indices that you do
not know are sorted. Do not make extra comparisons.
Exam of two iterations of bubble sort with last swapped optimization:
Start of bubble sort:
1
1
1
2
1
Start iteration 1:
Compare 1 (at index 0) with 2 (at index 1) and don't swap
7
2 6 5 3 4
Compare 2 (at index 1) with 6 (at index 2) and don't swap
7
2 6 5 3 4
Compare 6 (at index 2) with 5 (at index 3) and swap
1 2 5
4
7
Compare 6 (at index 3) with 3 (at index 4) and swap
6
2
3
Compare 6 (at index 4) with 4 (at index 5) and swap
2 5 3
6
7
Compare 6 (at index 5) with 7 (at index 6) and don't swap
1
2 5 3 4 6 7
Compare 7 (at index 6) with 8 (at index 7) and don't swap
7
2 5 3
6
Compare 8 (at index 7) with 9 (at index 8) and don't swap
1
2
5
3 4 6
7
5
5
3
3
4
4
4
7
Start iteration 2:
Note: Skip over indices 5-8 since no swaps occurred there.
Compare 1 (at index 0) with 2 (at index 1) and don't swap
1 2 5 3 4 6 7
Compare 2 (at index 1) with 5 (at index 2) and don't swap
7
2 5 3 4 6
Compare 5 (at index 2) with 3 (at index 3) and swap
5
4
2
Compare 5 (at index 3) with 4 (at index 4) and swap
1
2
3
4
5 6
6
7
7
7
8
8
8
8
8
8
8
8
8
8
8
8
8
9
9
9
9
9
9
9
9
9
9
9
O
Process or set of rules that allow for the solving of specific, well-defined computational problems through a specific series of commands. This topic is fundamental in computer science, especially with regard to artificial intelligence, databases, graphics, networking, operating systems, and security.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
