//=================================================
//=================================================
void print_array(int arr[], int size)
{
    int i;
    for(i=0; i<size; i++)
        printf("%d ", arr[i]);
}

//=================================================
// find the index of the minimum number in an array
//
// [Parameters]: arr - the array
//               size - the size of the array
// [Return value]: index of the minimum number
//=================================================
int find_min(int arr[], int size)
{
    int index_of_min = 0, i;

    for(i = 0; i < size; ++i)
       if(arr[i] < arr[index_of_min])
          index_of_min = i;

    return index_of_min;
}

//=================================================
// selection sort:
//   select the smallest number in the array a from index 0 to size-1,
//   and swap it with a[0];
//   then select the smallest number in array a from index 1 to size-1,
//   and swap it with a[1];
//   then select the smallest number in array a from index 2 to size-1,
//   and swap it with a[2];
//   and so on.
//
// [Parameters]: arr - the array
//               size - the array size
//=================================================
void select_sort(int arr[], int size)
{
    int i, index_of_min, temp;

    for(i = 0; i < size; ++i) {
        // find index of minimum number in a[i..size-1]
        index_of_min = find_min(arr + i, size - i);

        printf("i= %d, index_of_min= %d, selected number is %d (a[%d]).\n",
            i, index_of_min, arr[i+index_of_min], i+index_of_min);

        //swap arr[i] and arr[i+index_of_min]
        temp = arr[i];
        arr[i] = arr[i+index_of_min];
        arr[i+index_of_min] = temp;

        printf("After swapping a[%d] and a[%d], array is:\n",
                 i, i+index_of_min);
        print_array(arr, size);
        printf("\n");
        printf("Elements 0 to %d in correct position.\n\n", i);

    }
}

//=================================================
//=================================================
int main()
{
    int a[] = {9, 6, 8, 3, 7};

    int size = sizeof(a)/sizeof(a[0]);

    printf("### Before sorting, array is:\n");
    print_array(a, size);
    printf("\n");

    select_sort(a, size);

    printf("### After sorting, array is:\n");
    print_array(a, size);
    printf("\n");
}