selection

[nearc]

Can u explain why we need min_idx? isn't arr[i]=arr[min_idx] ?

 void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
 
   
    for (i = 0; i < n-1; i++)
    {
        
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;

        swap(&arr[min_idx], &arr[i]);
    }
}

[Ganado]

isn't arr[i]=arr[min_idx]

So you're asking isn't i always equal to min_idx, then?

No, the inner for loop (the j loop) can modify the min_idx value further, once it finds an element that is less than what the current min_idx's value is. After which, min_idx becomes whatever j is, not i.

Basically, the algorithm you have assumes that the first element is going to be the smallest element (as if it were already sorted), but then does swapping once it finds the smallest number in the array that isn't in ascending order.

// Example program
#include <iostream>

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
 
    for (i = 0; i < n-1; i++)
    {
        min_idx = i;
        for (j = i+1; j < n; j++)
        {
            if (arr[j] < arr[min_idx])
            {
                min_idx = j;
            }
        }

        std::cout << "swapping arr[min_idx=" << min_idx << "] with";
        std::cout << " arr[i=" << i << "]\n";
        swap(&arr[min_idx], &arr[i]);
    }
}

int main()
{
    int arr[] = {5, 6, 3, 2, 7};
    
    selectionSort(arr, 5);
    
    for (int i = 0; i < 5; i++)
    {
        std::cout << arr[i] << " ";   
    }
    std::cout << std::endl;
}

Run this code and look at the print statements

swapping arr[min_idx=3] with arr[i=0]
swapping arr[min_idx=2] with arr[i=1]
swapping arr[min_idx=3] with arr[i=2]
swapping arr[min_idx=3] with arr[i=3]
2 3 5 6 7 

Only on the last iteration of your algorithm does it needlessly swap.

[icy1]

Probably more idiomatic to declare variables as close possible to their usage (especially array index variables), rename "n" to arr_size or similar to make it obvious. Also, it's a simpler syntax to use std::swap.

min_idx, or i_min as i called it, is initialized as a copy of i with an opportunity to be a different index if a smaller value is found.

As Ganado pointed out, there is a chance for needless swaps, and indeed the pseudocode on the wiki only swaps when that i_min != i. So the C++ should look more like

void SelectionSort(int arr[], int arr_size)
{
    for (int i=0, i_min=i; i<arr_size-1; ++i)
    {
        for (int j=i+1; j<arr_size; ++j)
        {
            if (arr[j] < arr[i_min])
                i_min = j;
        }
        
        if (i_min != i)
            std::swap(arr[i_min], arr[i]);
    }
}

[nearc]

but how does j for loop make min_idx go through all array? doesn't it just become i+1?
So i would be 1st element
and
min_idx would be 2nd element same as j.

[icy1]

Break it down into steps; try to visualize.

Very first iteration
i=0, i_min=0. Now we look at values of the rest indices (1...end) and if anything is smaller, i_min set to that index. i_min now holds index of the smallest possible of the whole array, and we swap its value with our current spot i=0. So minimum value now sits at index 0.

i=1, i_min=1. Now we look at values of the rest of indices (2...end) with same procedure. i_min eventually holds index of smallest possible of this range, and we swap its value with our current spot of i=1. So this next minimum value now sits at index 1.

etc.

As you can see, i_min was index with smallest, then next smallest, then third smallest, then fourth smallest, etc. The range of search keeps dropping by 1 so we don't touch the ones we had placed previously.