Selection Sort Questions for Interview Preparation Set 3

How many Comparisons would be Required?

Consider the following lists of partially sorted numbers. The double bars represent the sort marker. For each list state how many comparisons and swaps are needed to sort the next number.

1. [1 3 4 6 7 || 9 8]
2. [1 2 4 5 8 || 9]
3. [1 3 || 4 9 6 8
4. [|| 9 2 3 8 1 6 4]
5. [2 3 4 || 9 8 7 6 5]

Answer:

1. comparisons = 0, swaps = 1
2. comparisons = 0, swaps = 0
3. comparisons = 3, swaps = 0
4. comparisons = 6, swaps = 1
5. comparisons = 4, swaps = 1

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.

Sort an Array with C++

{

    30, 50, 20, 10, 40
}

const int nSize = 5;

int anArray[nSize] = { 30, 50, 20, 10, 40 };

void main()
{

    // Step through each element of the array
    for (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++)
    {

        // nSmallestIndex is the index of the smallest element
        // we've encountered so far.
        int nSmallestIndex = nStartIndex;

        // Search through every element starting at nStartIndex+1
        for (
        int nCurrentIndex = nStartIndex + 1;

        nCurrentIndex < nSize;

        nCurrentIndex++
        )
        {

            // If the current element is smaller
            // than our previously found smallest
            if (anArray[nCurrentIndex] < anArray[nSmallestIndex])
            // Store the index in nSmallestIndex
            {

                nSmallestIndex = nCurrentIndex;

            }

        }

        // Swap our start element with our smallest element
        swap(anArray[nStartIndex], anArray[nSmallestIndex]);

    }

}

Another Variation of the above question: Rewrite the selection sort code above to sort in descending order (largest numbers first).

If (anArray[nCurrentIndex] < anArray[nSmallestIndex])

if (anArray[nCurrentIndex] > anArray[nSmallestIndex])

const int nSize = 5;

int anArray[nSize] = { 30, 50, 20, 10, 40 };

void main()
{

    // Step through each element of the array
    for (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++)
    {

        // nLargestIndex is the index of the smallest element
        // we've encountered so far.
        int nLargestIndex = nStartIndex;

        // Search through every element starting at nStartIndex+1
        for (
        int nCurrentIndex = nStartIndex + 1;

        nCurrentIndex <

        nSize; nCurrentIndex++
        )
        {

            // If the current element is smaller
            // than our previously found smallest
            if (anArray[nCurrentIndex] < anArray[nLargestIndex])
            {

                // Store the index in nLargestIndex
                nLargestIndex = nCurrentIndex;

            }

        }

        // Swap our start element with our smallest element
        swap(anArray[nStartIndex], anArray[nLargestIndex]);

    }

}

What is the average case performance of selection sort?

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

What is the worst case performance of selection sort?

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

Is selection sort having same efficiency as bubble sort?

Yes, both have same efficiency order of growth.

What is the average case performance of selection sort?

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

Sort the following array

{

    30, 50, 20, 10, 40
}

Answer:

1. We find the smallest element, starting from index 0:

   { 30, 50, 20, 10 , 40 }

2. We then swap this with the element at index 0:

   { 10 , 50, 20, 30 , 40 }

3. Now that the first element is sorted, we can ignore it. Consequently, we find the smallest element, starting from index 1:

   { 10, 50, 20 , 30, 40 }

4. And swap it with the element in index 1:

   { 10, 20 , 50 , 30, 40 }

5. Find the smallest element starting at index 2:

   { 10, 20, 50, 30 , 40 }

6. And swap it with the element in index 2:

   { 10, 20, 30 , 50 , 40 }

7. Find the smallest element starting at index 3:

   { 10, 20, 30, 50, 40  }

8. And swap it with the element in index 3:

   { 10, 20, 30, 40 , 50  }

9. Finally, find the smallest element starting at index 4:

   { 10, 20, 30, 40, 50  }

10. And swap it with the element in index 4 (which doesn't do anything):

    { 10, 20, 30, 40, 50  }

11. Done!

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'.

What is the worst case space complexity of selection sort?

The worst case space complexity of selection sort is O(n) total, O(1) auxiliary.