All Flashcards
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 is Selection Sort?
A sorting algorithm that divides the list into sorted and unsorted subarrays, repeatedly finding the minimum element from the unsorted subarray and placing it at the beginning.
What is Insertion Sort?
A sorting algorithm that builds the final sorted array one item at a time by repeatedly inserting elements from the unsorted portion into the correct position in the sorted portion.
What is an ArrayList?
A resizable array implementation of the List interface.
What is a sorted array?
An array where elements are arranged in a specific order (ascending or descending).
What is a subarray?
A contiguous part of an array.
What is ascending order?
Arrangement from smallest to largest.
What is descending order?
Arrangement from largest to smallest.
What is swapping?
Exchanging the positions of two elements in an array.
What is an algorithm?
A step-by-step procedure for solving a problem.
What is run-time comparison?
Evaluating the efficiency of algorithms by counting statement executions.
What is the core idea behind Selection Sort?
Repeatedly selecting the smallest element and moving it to the sorted portion.
What is the core idea behind Insertion Sort?
Building a sorted subarray by inserting elements from the unsorted portion into their correct positions.
How do you determine if an ArrayList is sorted?
Iterate through the list, checking if each element is less than or equal to the next.
What is the purpose of sorting algorithms?
To arrange elements in a specific order, typically ascending or descending, for easier searching and data retrieval.
What is the significance of run-time comparisons?
They help in understanding the efficiency of different algorithms and choosing the best one for a specific task.
What are the two subarrays in Selection Sort?
Sorted subarray and unsorted subarray.
What are the two subarrays in Insertion Sort?
Sorted subarray and unsorted subarray.
Why is it important to check if an ArrayList is sorted?
To ensure data integrity and efficiency in search and retrieval operations.
What is the main goal of comparing sorting algorithms?
To understand their relative efficiency and choose the best one for a given situation.
What is the role of swapping in sorting algorithms?
To rearrange elements in the correct order.