Answers for "selection sort swaps"

The number of swaps required in selection sort

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll a[111111], tmp[111111], ans;
 
void merge_sort(ll a[], ll b[], ll lo, ll hi)
{
    ll i, j, k;
 
    if (lo >= hi)
        return;
 
    ll mid = (lo + hi) / 2;
 
    merge_sort(a, b, lo, mid);
    merge_sort(a, b, mid + 1, hi);
 
    i = lo;
    j = mid + 1;
 
    for (k = lo; k <= hi; k++)
        if (j > hi)
            b[k] = a[i++];
        else if (i > mid)
            b[k] = a[j++];
        else if (a[i] <= a[j])
            b[k] = a[i++];
        else
        {
            b[k] = a[j++];
            ans += mid - i + 1;
        }
 
    for (i = lo; i <= hi; i++)
        a[i] = b[i];
}
 
int main(void)
{
    ll t;
 
    scanf("%lld", &t);
 
    while (t--)
    {
        ll n, i;
 
        scanf("%lld", &n);
        for (i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
 
        ans = 0;
        merge_sort(a, tmp, 1, n);
 
        printf("%lldn", ans);
    }
    return 0;
}

how to send values to a selection sorting function

1  // Fig. 8.15: fig08_15.cpp
 2  // This program puts values into an array, sorts the values into
 3  // ascending order and prints the resulting array.
 4  #include <iostream>
 5  using std::cout;
 6  using std::endl;
 7
 8  #include <iomanip>
 9  using std::setw;
10
11  void selectionSort( int * const, const int ); // prototype
12  void swap( int * const, int * const ); // prototype
13
14  int main()
15  {
16     const int arraySize = 10;
17     int a[ arraySize ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
18
19     cout << "Data items in original ordern";
20
21     for ( int i = 0; i < arraySize; i++ )
22        cout << setw( 4 ) << a[ i ];
23
24     selectionSort( a, arraySize ); // sort the array
25
26     cout << "nData items in ascending ordern";
27
28     for ( int j = 0; j < arraySize; j++ )
29        cout << setw( 4 ) << a[ j ];
30
31     cout << endl;
32     return 0; // indicates successful termination
33  } // end main
34
35  // function to sort an array
36  void selectionSort( int * const array, const int size )
37  {
38     int smallest; // index of smallest element
39
40     // loop over size - 1 elements
41     for ( int i = 0; i < size - 1; i++ )
42     {
43        smallest = i; // first index of remaining array
44
45        // loop to find index of smallest element
46        for ( int index = i + 1; index < size; index++ )
47
48           if ( array[ index ] < array[ smallest ] )
49              smallest = index;
50
51        swap( &array[ i ], &array[ smallest ] );
52     } // end if
53  } // end function selectionSort
54
55  // swap values at memory locations to which                  
56  // element1Ptr and element2Ptr point                         
57  void swap( int * const element1Ptr, int * const element2Ptr )
58  {                                                            
59     int hold = *element1Ptr;                                  
60     *element1Ptr = *element2Ptr;                              
61     *element2Ptr = hold;                                      
62  } // end function swap