    001: #include <iostream>
    002: #include <vector>
    003: #include <cstdlib>
    004: #include <ctime>
    005:
    006: using namespace std;
    007:
    008: #include "ccc_time.cpp"
    009:
    010: /**
    011:    Swaps two integers.
    012:    @param x the first integer to swap
    013:    @param y the second integer to swap
    014: */
    015: void swap(int& x, int& y)
    016: {
    017:    int temp = x;
    018:    x = y;
    019:    y = temp;
    020: }
    021:
    022: /**
    023:     Gets the position of the smallest element in a vector range.
    024:     @param a the vector
    025:     @param from the beginning of the range
    026:     @param to the beginning of the range
    027:     @return the position of the smallest element in
    028:     the range a[from]...a[to]
    029: */
    030: int min_position(vector<int>& a, int from, int to)
    031: {
    032:    int min_pos = from;
    033:    int i;
    034:    for (i = from + 1; i <= to; i++)
    035:       if (a[i] < a[min_pos]) min_pos = i;
    036:    return min_pos;
    037: }
    038:
    039: /**
    040:    Sorts a vector using the selection sort algorithm
    041:    @param a the vector to sort
    042: */
    043: void selection_sort(vector<int>& a)
    044: {
    045:    int next; /* the next position to be set to the minimum */
    046:
    047:    for (next = 0; next < a.size() - 1; next++)
    048:    {
    049:       /* find the position of the minimum */
    050:       int min_pos = min_position(a, next, a.size() - 1);
    051:       if (min_pos != next)
    052:          swap(a[min_pos], a[next]);
    053:    }
    054: }
    055:
    056: /**
    057:    Prints all elements in a vector
    058:    @param a the vector to print
    059: */
    060: void print(vector<int> a)
    061: {
    062:    for (int i = 0; i < a.size(); i++)
    063:       cout << a[i] << " ";
    064:    cout << "\n";
    065: }
    066:
    067: /**
    068:    Sets the seed of the random number generator.
    069: */
    070: void rand_seed()
    071: {
    072:    int seed = static_cast<int>(time(0));
    073:    srand(seed);
    074: }
    075:
    076: /**
    077:    Computes a random integer in a range.
    078:    @param a the bottom of the range
    079:    @param b the top of the range
    080:    @return a random integer x, a <= x and x <= b
    081: */
    082: int rand_int(int a, int b)
    083: {
    084:    return a + rand() % (b - a + 1);
    085: }
    086:
    087: int main()
    088: {
    089:    rand_seed();
    090:    cout << "Enter vector size: ";
    091:    int n;
    092:    cin >> n;
    093:    vector<int> v(n);
    094:    for (int i = 0; i < v.size(); i++)
    095:       v[i] = rand_int(1, 100);
    096:    Time before;
    097:    selection_sort(v);
    098:    Time after;
    099:
    100:    cout << "Elapsed time = " << after.seconds_from(before)
    101:       << " seconds\n";
    102:    return 0;
    103: }