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: }