Preview

21 - Sorting

 1. In an insertion sort elements are split into two parts and each part is recursively sorted. An array of one item is sorted (base case).

  True

  False

 2. Analyse the code below. What type of sort has been coded?
import java.util.Arrays;

public class SortTest
{
   public static void xort(int[] elements)
   {
      for (int j = 0; j < elements.length - 1; j++)
      {
         int minIndex = j;
         for (int k = j + 1; k < elements.length; k++)
         {
            if (elements[k] < elements[minIndex])
            {
               minIndex = k;
            }
         }
         int temp = elements[j];
         elements[j] = elements[minIndex];
         elements[minIndex] = temp;
       }
   }

   public static void main(String[] args)
   {
      int[] arr1 = {3, 86, -20, 14, 40};
      System.out.println(Arrays.toString(arr1));
      selectionSort(arr1);
      System.out.println(Arrays.toString(arr1));
   }
}

  Insertion Sort

  Merge Sort

  Binary Sort

  Selection Sort

 3. Under what condition will a selection sort execute faster?

  It will always take the same amount of time to execute

   If the data is already sorted in descending order

   If the data is already sorted in ascending order

  If the data is randomly organised i.e not sorted

 4. The following method should sort the numbers in the passed array into ascending order. But, it does not work. Which of the following lines is wrong?
public static void selectionSort(int[] elements)
{
  for (int j = 0; j < elements.length ? 1; j++)      // line 1
  {
     int minIndex = j;                               // line 2
     for (int k = 0; k < elements.length; k++)       // line 3
     {
        if (elements[k] < elements[minIndex])        // line 4
        {
           minIndex = k;                             // line 5
        }
     }
     int temp = elements[j];
     elements[j] = elements[minIndex];
     elements[minIndex] = temp;
   }
}

  Line 1

  Line 2

  Line 3

  Line 4

 5. Refer to the question and code above. What is wrong with the line you identified?

  The outer loop should start at the inner loop index + 1

  The outer loop should start at the inner loop index - 1

   The inner loop should start at the outer loop index + 1.

  The inner loop should start at the inner loop index - 1

 6. The following code demonstrates an insertion sort.
import java.util.Arrays;

public class SortTest
{
   public static void xSort(int[] elements)
   {
      for (int j = 1; j < elements.length; j++)
      {
         int temp = elements[j];
         int possibleIndex = j;
         while (possibleIndex > 0 && temp < elements[possibleIndex - 1])
         {
            elements[possibleIndex] = elements[possibleIndex - 1];
            possibleIndex--;
         }
         elements[possibleIndex] = temp;
      }
  }

   public static void main(String[] args)
   {
      int[] arr1 = {3, 86, -20, 14, 40};
      System.out.println(Arrays.toString(arr1));
      insertionSort(arr1);
      System.out.println(Arrays.toString(arr1));
   }
}

  FALSE

  TRUE

 7. If the data is already sorted in the correct order you don't need to move any values and an insertion sort would execute faster.

  FALSE

  TRUE

 8. In an insertion sort, if the data is already sorted in descending order, it would result in _________________.

  the shortest execution

  the longest execution

  the same amount of time as if it was sorted in ascending order

  the same amount of time as if it was not sorted at all

 9. Assuming this method should sort the numbers in the passed array into ascending order, what is wrong with line 1?
public static void insertionSort(int[] elements)
{
  for (int j = 1; j < elements.length - 1; j++)                       // line 1
  {
     int temp = elements[j];                                          // line 2
     int possibleIndex = j;                                           // line 3
     while (possibleIndex > 0 && temp < elements[possibleIndex - 1])  // line 4
     {
        elements[possibleIndex] = elements[possibleIndex - 1];        // line 5
        possibleIndex--;
     }
     elements[possibleIndex] = temp;
  }
}

  Nothing is wrong - it is correctly coded

  for (int j = 1) should be for (int j = 0)

  It should loop through the entire array

  j++ should be j--

 10. Selection sort and Insertion sort both have nested loops that run through the data of size n approximately n squared times.

  TRUE

  FALSE

 11. Considering the above, Selection sort and insertion sort perform differently on some data.

  FALSE

  TRUE

 12. Merge sort is basically a Divide and Conquer algorithm to sort a given set of elements _____________ and then merge them.

  iteratively

  recursively

  modularly

  basely

 13. Analyse the following code. What is happening on the line below the comment x? (refer to line 30 in the following code)
 
public class MyMergeSort {
     
    private int[] array;
    private int[] tempMergArr;
    private int length;
 
    public static void main(String a[]){
         
        int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
        MyMergeSort mms = new MyMergeSort();
        mms.sort(inputArr);
        for(int i:inputArr){
            System.out.print(i);
            System.out.print(" ");
        }
    }
     
    public void sort(int inputArr[]) {
        this.array = inputArr;
        this.length = inputArr.length;
        this.tempMergArr = new int[length];
        doMergeSort(0, length - 1);
    }
 
    private void doMergeSort(int lowerIndex, int higherIndex) {
         
        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            // COMMENT X: The below step __________________?!??
            doMergeSort(lowerIndex, middle);
            doMergeSort(middle + 1, higherIndex);
            mergeParts(lowerIndex, middle, higherIndex);
        }
    }
 
    private void mergeParts(int lowerIndex, int middle, int higherIndex) {
 
        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
        }
 
    }
}

  None of these answers are correct

  ....merges both sides of the array

  ...sorts the right side of the array

  ...sorts the left side of the array

 14. The following code demonstrates:
public static void XSort(int[] a) {
    boolean sorted = false;
    int temp;
    while(!sorted) {
        sorted = true;
        for (int i = 0; i < array.length - 1; i++) {
            if (a[i] > a[i+1]) {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                sorted = false;
            }
        }
    }
}

  a selection sort

  a bubble sort

  an insertion sort

  a merge sort

 15. The idea behind _________________is dividing the array into the sorted and unsorted subarrays.

  a bubble sort

  an insertion sort

  a merge sort

  a selection sort