0
$\begingroup$

I want to understand how the algorithm of selection sort sorts the given array, $$A[5]=\{5,9,11,10,2\}$$ Step -$1:-$ I compare A[0] with remaining elements of the array and since $A[4]<A[0]$ I swap them which leaves me with, $$A=\{2,9,11,10,5\}$$ Step-$2:-$ Repeating the similar procedure for $A[1]$ gives $$\{2,5,11,10,9 \}$$ Step-$3:-$ Repeating similar procedure gives $$\{2,5,10,11,9\}$$ And the for loop stops. But the array isn't sorted yet. Is there any mistake with my interpretation of the algorithm?

C program for selection sort:-

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    
    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
$\endgroup$
1
  • $\begingroup$ You should give the pseudocode of the algorithm that you are calling "selection sort" (because it is unclear with your description). $\endgroup$
    – Nathaniel
    Mar 18 at 17:32

1 Answer 1

0
$\begingroup$

You are stopping the i loop too soon.

You should try it again and keep track of the value of $i$ and keep in mind that in an array of length $n$, indices of the array are between $0$ and $n-1$.

$\endgroup$
6
  • $\begingroup$ I tried out his code and gave as an input the array that was written in the question and the C code sorted it, I don't understand why he assumes that for loop stops there. (I added i<n, instead of i<n-1, but I think i<n-1 (theoretically changes) but didn't change computation, however of course i<n should be there) $\endgroup$
    – math boy
    Mar 18 at 22:51
  • $\begingroup$ @Nathaniel,@math boy. I actually misunderstood the code and got my answer after some verification. I thank your answers and comments. $\endgroup$
    – RAHUL
    Mar 19 at 7:29
  • 1
    $\begingroup$ @mathboy i < n is unnecessary: the last loop with i = n - 1 does nothing, because the last element is necessary the greatest. $\endgroup$
    – Nathaniel
    Mar 19 at 8:52
  • $\begingroup$ (@Nathaniel last element is necessary the greatest as well as the smallest left, more interesting in a loop establishing this.) $\endgroup$
    – greybeard
    Mar 19 at 11:14
  • $\begingroup$ @greybeard you are right, of course. My point was that the loop invariant being "Elements at indices between 0 and $i-1$ are at the right position", it was not needed to do the last loop, because the element at index $n-1$, being the greatest, is at the right position. $\endgroup$
    – Nathaniel
    Mar 19 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.