C++

Forum

 
Sorting

theonealone (18)
Hey guys have a small problem.

I have this code where i need to write a function. This function,

Checks every consecutive pair of items in the container, eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last and finds the percentage that are in order vs the total number of pairs. This percentage value is returned.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
template <class iterator>
 int sortPercent(iterator start, iterator finish)
{
   /**************************************************  ***********************\
      sortPercentage
      Checks every consecutive pair of items in the container, 
      eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last
      and finds the percentage that are in order vs the total number of pairs.
      This percentage value is returned.
   \*************************************************  ************************/
 
   iterator left, right;
   int InnerCount;
   int comparisons;
   int swaps = 0;

   for (comparisons = 0; comparisons < finish; comparisons++)
   {
      for (InnerCount = 0; InnerCount < finish; InnerCount++)
      {
         right = left = start;

         while (right != finish)
         {
            if (*left < *right)
            {
               swaps+=1;
            }
         }
      }
      comparisons+=1;
	
   }
return comparisons;
}


This is what i got so far.

The whole code is below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
 

/********************************************************\
   Test program for demonstrating sorting algorithms
\********************************************************/
#include <stdlib.h>

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdlib.h>

#include "dataobject.h"

using namespace std;

int randNum();

template <class iterator> 
   void sortContainer(iterator start, iterator finish, int gap);
   

int randNum()
{
   // rand() produces pseudo-random number in range 0 to RAND_MAX
   // for most compilers RAND_MAX is 2^15-1
   // randNum() produces pseudo-random number in range 0 to 2^31-1
  
   return ((rand() << 16) + rand());
} 


template <class iterator>
 int sortPercent(iterator start, iterator finish)
{
   /**************************************************  ***********************\
      sortPercentage
      Checks every consecutive pair of items in the container, 
      eg, 1st and 2nd, 2nd and 3rd, 3rd and 4th ... to ... 2nd last and last
      and finds the percentage that are in order vs the total number of pairs.
      This percentage value is returned.
   \*************************************************  ************************/
 
   iterator left, right;
   int InnerCount;
   int comparisons;
   int swaps = 0;

   for (comparisons = 0; comparisons < finish; comparisons++)
   {
      for (InnerCount = 0; InnerCount < finish; InnerCount++)
      {
         right = left = start;

         while (right != finish)
         {
            if (*left < *right)
            {
               swaps+=1;
            }
         }
      }
      comparisons+=1;
	
   }
return comparisons;
}

template <class iterator> 
   void sortContainer(iterator start, iterator finish, int gap)
{
   /****************************************************************\
       Sort the container using shell sort
       gap will be called with the original size of the container
       The underlying sort for the container is bubble sort which
       will be run twice for each gap decrement
   \****************************************************************/

   if (gap == 1) return;
   
   iterator left, right;
   int i, numswap, totswap=0, numpass;

	
   
   gap = gap * 3 / 4;
   do {
      numswap = 0;
      
      // Reduce gap. Gap will start out at half the size of the container
      // Eventually will stabilize at 1 in size
      gap = (gap * 2 + 1) / 3; 
      
      // make two passes through container with bubble sort
      for (numpass=0; numpass<2; numpass++) {
         right = left = start;
         // Make the distance between left and right gap in size
         for (i=0; i<gap; i++) right++;
       
         // Make a pass through container using Bubble sort
 
         while (right != finish) {

            if (*left < *right) {
               swap(left, right);
               numswap++;
            }
            left++;
            right++;
         }
       cout << "LOL \n";
         // update some statistics and print them
         totswap += numswap;
         cout << "gap = " << gap << " num swaps = " << numswap;
         cout << " sort percentage = " << sortPercent(start, finish) << "\n";
         
         if (numswap == 0) break;
      }
   } while (numswap > 0 || gap > 1);
   
   cout << "Total swaps = " << totswap << "\n";
}

int main(int argc, char *argv[])
{
   const int MAXDATA = 10000;
   vector<dataObject> array;
   dataObject *doPtr;
   int i, rand;
   
   try {
      /**************************************************************\
         Initialise things to demonstrate the sort
      \**************************************************************/
      
      // fill vector with unique values
      for (i=0; i<MAXDATA; i++) {
         doPtr = new dataObject(i);
         array.push_back(*doPtr);
         delete doPtr;
      }
      
      // set up random number generator
      if (argc != 2) {
         cout << "Syntax : program seed\n";
         cout << "seed is any integer value\n";
         return 0;
      }
      int seed = atoi(argv[1]);
      srand(seed);
      
      // scramble vector
      for (i=0; i<MAXDATA; i++) {
         rand = randNum() % MAXDATA;
         swap(array[i], array[rand]);
      }
      cout << MAXDATA << " Items in vector\n";
      
      /*************************************************************\
         sort the vector using iterators 
      \*************************************************************/
      
      cout << "Sorting vector using shell sort\n";
      sortContainer(array.begin(), array.end(), array.size());
      
   } catch(...) {
      cout << "\nERROR - undefined Exception thrown\n";
      exit(1);
   }
   
   return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
#ifndef DATAOBJECT_H_
#define DATAOBJECT_H_

#include <algorithm>

/***********************************************************\
   class for holding data to be stored in container objects
\***********************************************************/

struct dataObject
{
   int keyval;
   
   /********************************************************\
      place any other data declartions the data object 
      may need here
   \********************************************************/
   
   /********************************************************\
      constructors
   \********************************************************/
   
   // constructor
   dataObject() : keyval(-1) {}
   dataObject(int val) : keyval(val) {}
   
   // copy constructor
   dataObject(const dataObject &other) : keyval(other.keyval) {
      // copy any data in other to this
   }
   
   /********************************************************\
      misc functions
   \********************************************************/
   
   void swapObjects(dataObject &other) {
      std::swap(keyval, other.keyval);
      // swap any other data in dataObject
   }
   
   bool isKeyval(int val) const {
      return (val == keyval);
   }
   
   int getKeyval() const {
      return keyval;
   }
   
   int getHashval(int range) const {
      return (keyval % range);
   }

   bool empty() const {
      return (keyval == -1);
   }
   
   /********************************************************\
      overloaded operators
   \********************************************************/
   
   // overloaded assignment operator
   dataObject& operator = (const dataObject &other) {
      dataObject temp(other);
      swapObjects(temp);
      return *this;
   }
   
   // overloaded relational operators
   bool operator == (const dataObject &other) const {
      return (keyval == other.keyval);
   }
   
   bool operator != (const dataObject &other) const {
      return (keyval != other.keyval);
   }
   
   bool operator > (const dataObject &other) const {
      return (keyval > other.keyval);
   }
   
   bool operator < (const dataObject &other) const {
      return (keyval < other.keyval);
   }
   
   bool operator >= (const dataObject &other) const {
      return (keyval >= other.keyval);
   }
   
   bool operator <= (const dataObject &other) const {
      return (keyval <= other.keyval);
   }
};

#endif


Any help is appreciated.
Thanks in advance,
kev82 (323)
Why do you have two loops? For a list of n things, there are n-1 consecutive pairs. So just need to loop i from 0 to n-2 inclusive and check pair i,i+1. Keep a count of how many had data[i]<=data[i+1], divide this by n-1 and that's the answer, surely?

Topic archived. No new replies allowed.