Selection Sort Questions for Interview Preparation Set 2

What is the mathematical definition of selection sort?

We define selection sort mathematically:

1. L' is a permutation of L,
2. for all and
3. 
4. s is the smallest element of L, and
5. L_s is the set of elements of L without one instance of the smallest element of L.

Write an algorithm for selection sort.

1. Repeat step 2 and 3 varying j from 0 to n-2 //Repeat for n-1 passes
2. Find the index of the minimum value in arr[j] to arr[n-1]
   1. Set min_index=j
   2. Repeat step c varying i from j+1 to n-1
   3. If arr[i]<arr[min_index]: min_index = i
3. swap arr[j] with arr[min_index]

How is selection sort implemented ?

void selectionSort(int numbers[], int array_size)
{

    int i, j;

    int min, temp;

    for (i = 0; i < array_size-1; i++)
    {

        min = i;

        for (j = i+1; j < array_size; j++)
        {

            if (numbers[j] < numbers[min])
            {

                min = j;

            }

        }

        temp = numbers[i];

        numbers[i] = numbers[min];

        numbers[min] = temp;

    }

}

How many comparisons are performed in the second pass of the selection sort algorithm?

n-2 comparisons are performed in the second pass of the selection sort algorithm.

What is the best case performance of selection sort?

The best case performance of selection sort is O(n²).

What is the mathematical definition of selection sort?

We define selection sort mathematically:

1. L' is a permutation of L,
2. for all and
3. 
4. s is the smallest element of L, and
5. L_s is the set of elements of L without one instance of the smallest element of L.

How do you define selection sort?

Selection sort scans through the list iteratively, selecting one item in each scan, and moving the item to its correct position in the list.

NOTE: Iteratively means one by one. It can also be called 'in a loop'.

Which are the basic steps for performing selection sort?

There are basically two steps perform during selection sort:

1. Find smallest element in unsorted portion from list or array.
2. Interchange the smallest element with the one at the front of the unsorted portion

How can we rewrite the Selection Sort algorithm so that it sorts numbers from highest to lowest?

To modify the Selection Sort Algorithm so that it sorts from highest to lowest, we need to search for the largest card rather than the smallest. The modifications to the original algorithm are marked in italics.

1. Get a list of unsorted numbers
2. Set a marker for the unsorted section at the front of the list
3. Repeat steps 4 through 7 until one number remains in the unsorted section
4. Compare all unsorted numbers
5. Select the largest unsorted number
6. Swap this number with the first number in the unsorted
7. Advance the marker to the right one position
8. Stop

How is Selection Sort analyzed?

Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all n elements (this takes n - 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n - 1 elements and so on, for comparisons. Each of these scans requires one swap for (n-1) elements.