All Flashcards
What are the general steps of Selection Sort?
- Find the smallest element in the unsorted portion. 2. Swap it with the first element of the unsorted portion. 3. Repeat for the remaining unsorted portion.
What are the general steps of Insertion Sort?
- Assume the first element is sorted. 2. Take the next element and insert it into the correct position in the sorted portion. 3. Repeat for all remaining elements.
What are the steps to check if an ArrayList is sorted?
- Iterate through the list. 2. Compare each element with the next. 3. If any element is greater than the next, the list is not sorted.
Steps of Selection Sort (detailed)
- Find the minimum element in the unsorted array. 2. Swap the found minimum element with the first element of the unsorted array. 3. Move to the next element in the unsorted array. 4. Repeat until the array is sorted.
Steps of Insertion Sort (detailed)
- Iterate from the second element to the end of the array. 2. For each element, compare it with the elements before it. 3. Shift the elements greater than the current element to one position ahead of their current position. 4. Insert the current element in the correct position.
Steps to determine if an ArrayList is sorted (detailed)
- Start from the first element of the ArrayList. 2. Compare each element with the next element in the ArrayList. 3. If any element is greater than the next element, return false. 4. If the end of the ArrayList is reached, return true.
What is the first step in Selection Sort?
Find the smallest element in the unsorted portion.
What is the first step in Insertion Sort?
Assume the first element is sorted.
What is the first step to check if an ArrayList is sorted?
Iterate through the list.
What is the last step in Selection Sort?
Repeat for the remaining unsorted portion.
What does this code do?
java
public static boolean isSorted(ArrayList<Integer> array) {
for (int i = 0; i < array.size() - 1; i++) {
if (array.get(i + 1) < array.get(i)) {
return false;
}
}
return true;
}
Checks if an ArrayList of Integers is sorted in ascending order.
What is the purpose of the outer loop in the selectionSort method?
To traverse to the second to last item in the ArrayList.
What is the purpose of the inner loop in the selectionSort method?
To find the smallest remaining item in the unsorted portion of the ArrayList.
What is the purpose of the outer loop in the insertionSort method?
To iterate through the ArrayList, considering each element for insertion into the sorted portion.
What is the purpose of the inner loop in the insertionSort method?
To shift elements to the right to create space for inserting the current element in its correct position.
What is the error in the following code?
java
public static ArrayList<Integer> selectionSort(ArrayList<Integer> array) {
for (int i = 0; i < array.size(); i++) { // Error is here
int smallestIndex = i;
int smallestElement = array.get(i);
for (int j = i + 1; j < array.size(); j++) {
if (array.get(j) < smallestElement) {
smallestIndex = j;
smallestElement = array.get(j);
}
}
if (smallestIndex > i) {
int originalItem = array.get(i);
array.set(i, smallestElement);
array.set(smallestIndex, originalItem);
}
}
return array;
}
The outer loop should iterate up to array.size() - 1 to avoid an IndexOutOfBoundsException.
What is the error in the following code?
java
public static ArrayList<Integer> insertionSort(ArrayList<Integer> array) {
for (int i = 1; i < array.size(); i++) {
int currentElement = array.get(i);
int currentIndex = i;
for (int j = i; j > 0; j++) {
if (currentElement < array.get(j - 1)) { // shifting the item left until properly placed by swapping consecutive items
int itemToRight = array.get(j - 1);
array.set(j - 1, currentElement);
array.set(j, itemToRight);
}
}
}
return array;
}
There is no error in the code.
Predict the output:
java
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
selectionSort(list);
System.out.println(list);
[1, 2, 5, 8, 9]
Predict the output:
java
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
insertionSort(list);
System.out.println(list);
[1, 2, 5, 8, 9]
Complete the code:
java
public static boolean isSorted(ArrayList<Integer> array) {
for (int i = 0; i < array.size() - 1; i++) {
if (array.get(i + 1) < array.get(i)) {
// Complete this line
}
}
return true;
}
return false;
What are the differences between Selection Sort and Insertion Sort?
Selection Sort: Finds the minimum element and swaps. | Insertion Sort: Inserts elements into the sorted portion.
Selection Sort vs. Insertion Sort: Data Accesses
Selection Sort: Requires more data accesses and modifications. | Insertion Sort: Requires fewer data accesses and modifications.
Selection Sort vs. Insertion Sort: Best case scenario
Selection Sort: Performance not affected by input. | Insertion Sort: More efficient when data is partially sorted.
Selection Sort vs. Insertion Sort: Implementation Complexity
Selection Sort: Generally simpler to implement. | Insertion Sort: Slightly more complex due to shifting elements.
Selection Sort vs. Insertion Sort: Performance on small datasets
Selection Sort: Performance is generally consistent. | Insertion Sort: Can be faster for small, nearly sorted datasets.
Selection Sort vs. Insertion Sort: Number of swaps
Selection Sort: Performs fewer swaps. | Insertion Sort: Performs more swaps.
Selection Sort vs. Insertion Sort: Adaptability
Selection Sort: Not adaptive (doesn't take advantage of existing order). | Insertion Sort: Adaptive (performs better on nearly sorted data).
Selection Sort vs. Insertion Sort: Use cases
Selection Sort: Suitable for small datasets where minimizing writes is important. | Insertion Sort: Suitable for small datasets or when data is nearly sorted.
Selection Sort vs. Insertion Sort: Worst-case time complexity
Selection Sort: O(n^2). | Insertion Sort: O(n^2).
Selection Sort vs. Insertion Sort: Space complexity
Selection Sort: O(1). | Insertion Sort: O(1).