C++

Forum

 
Having trouble sorting 2 arrays in a heap sort. Assistance?

Xzi (26)
My program is supposed to sort some information by the college then by the city. The problem is I can't get it to sort by the city right yet. Here's my code:

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
 
#include <iostream>
#include <iomanip>
#include <string>
#include <fstream>

using namespace std;

void msHeap(string ar[], string arC[], int i, int n)
{
  int k = i * 2 + 1;
  while (k < n)
    {
      if(k + 1 < n && arC[k] < arC[k+1])k++;
      if(k + 1 < n && ar[k] < ar[k+1])k++;
      if (arC[i] < arC[k])swap(arC[i], arC[k]);
      if (ar[i] < ar[k])swap(ar[i], ar[k]);
      k = i++ * 2 + 1;
    }
}

void mHeap(string ar[], int i, int n)
{
  int k = i * 2 + 1;
  while (k < n)
    {
      if(k + 1 < n && ar[k] < ar[k+1])k++;
      if (ar[i] < ar[k])swap(ar[i], ar[k]);
      k = i++ * 2 + 1;
    }
}

// heapsort - largest at the top
// build the heap
void hcSort(string ar[], string arC[], int n)
{
  int i = n / 2;
  while(i-- > 0) msHeap(ar, arC, i, n);
  while(n-- > 0)
    {
      swap(arC[0], arC[n]);
      swap(ar[0], ar[n]);
      mHeap(arC, 0, n);
      mHeap(ar, 0, n);
    }
}//sort the heap

// heapsort - largest at the top
// build the heap
void hSort(string ar[], int n)
{
  int i = n / 2;
  while(i-- > 0) mHeap(ar, i, n);
  while(n-- > 0)
    {
      swap(ar[0], ar[n]);
      mHeap(ar, 0, n);
    }
}//sort the heap

string rmSpc(string stringIn)
{
  size_t pos = 0;
  bool spacesLeft  = true;
  while(spacesLeft)
    {

      pos = stringIn.find(" ");
      if(pos != string::npos)stringIn.erase(pos, 1);
      else spacesLeft = false;
    }
return stringIn;
}//remove spaces

int main()
{
  string line, dash("-"), ar[200], arC[200];
  int l, len = 0, t = 0;

  ifstream heap ("Universities.c");

  if(heap.is_open())
    {
      while(!heap.eof())
      {
        getline(heap,line);
        ar[t] = line;
        line = rmSpc(line);
        arC[t] = line.substr(line.find_last_of(dash) + 1);
        t++;
      }
    }

    hSort(ar, t);
    for(l = 0; l < t; l++)cout << ar[l] << endl;
    cout << "-------------------------------------------------------------------" << endl;
    cout << "Now this Program will print out the Universities according to city:" << endl;
    cout << "-------------------------------------------------------------------" << endl;
    hcSort(ar, arC, t);
    for(l = 0; l < t; l++)cout << arC[l] << endl;
}


The output is sorting JUST the cities without the college attached it looks like this:


Bacone College -   Muskogee OK
Cameron University - Lawton
Connors State College - Muskogee
Connors State College - Warner
East Central University - Ada
Langston University -  Langston
Langston University - Oklahoma City
Langston University - Tulsa
Mid-America Christian University - Oklahoma City
Northeastern Oklahoma A&M College - Miami
Northeastern State University - Broken Arrow
Northeastern State University - Muskogee
Northeastern State University - Tahlequah
Northern Oklahoma College - Enid
Northern Oklahoma College - Stillwater
Northern Oklahoma College - Tonkawa
Northwestern Oklahoma State University -  Enid
Northwestern Oklahoma State University - Alva
Northwestern Oklahoma State University - Woodward
Oklahoma Baptist University - Shawnee
Oklahoma Christian University of Science & Arts - Oklahoma City
Oklahoma City University - Oklahoma City
Oklahoma Panhandle State University - Goodwell
Oklahoma State University - Stillwater
Oklahoma State University Institute of Technology - Okmulgee
Oklahoma State University System - Tulsa
Oklahoma Wesleyan University - Bartlesville
Oral Roberts University - Tulsa
Rogers State University -  Claremore
Rogers State University - Bartlesville
Rogers State University - Pryor
Southeastern Oklahoma State University - Durant
Southern Nazarene University - Bethany
Southwestern Oklahoma State University - Weatherford
St. Gregory's University - Shawnee
University Center at Ponca City - Ponca City
University of Central Oklahoma - Edmond
University of Oklahoma - Norman
University of Oklahoma Health Sciences Center -    Oklahoma City
University of Science & Arts of Oklahoma - Chickasha
University of Tulsa - Tulsa
-------------------------------------------------------------------
Now this Program will print out the Universities according to city:
-------------------------------------------------------------------

Ada
Alva
Bartlesville
Bartlesville
Bethany
BrokenArrow
Chickasha
Claremore
Durant
Edmond
Enid
Enid
Goodwell
Langston
Lawton
Miami
Muskogee
Muskogee
MuskogeeOK
Norman
OklahomaCity
OklahomaCity
OklahomaCity
OklahomaCity
OklahomaCity
Okmulgee
PoncaCity
Pryor
Shawnee
Shawnee
Stillwater
Stillwater
Tahlequah
Tonkawa
Tulsa
Tulsa
Tulsa
Tulsa
Warner
Weatherford
Woodward


And finally here's the source file:


Oklahoma State University - Stillwater
Oklahoma State University Institute of Technology - Okmulgee
Oklahoma State University System - Tulsa
Mid-America Christian University - Oklahoma City
Southeastern Oklahoma State University - Durant
Cameron University - Lawton
East Central University - Ada
Oklahoma Christian University of Science & Arts - Oklahoma City
Rogers State University -  Claremore
Rogers State University - Bartlesville
Rogers State University - Pryor
Langston University -  Langston
Langston University - Tulsa
Langston University - Oklahoma City
Northwestern Oklahoma State University -  Enid
Northwestern Oklahoma State University - Woodward
Northwestern Oklahoma State University - Alva
Oklahoma City University - Oklahoma City
Oklahoma Panhandle State University - Goodwell
University of Oklahoma Health Sciences Center -    Oklahoma City
Northeastern State University - Muskogee
Northeastern State University - Broken Arrow
Northeastern Oklahoma A&M College - Miami
Northeastern State University - Tahlequah
Oklahoma Wesleyan University - Bartlesville
Oral Roberts University - Tulsa
St. Gregory's University - Shawnee
Southern Nazarene University - Bethany
Southwestern Oklahoma State University - Weatherford
University of Central Oklahoma - Edmond
Oklahoma Baptist University - Shawnee
University of Oklahoma - Norman
University of Science & Arts of Oklahoma - Chickasha
Bacone College -   Muskogee OK
University of Tulsa - Tulsa
Connors State College - Muskogee
Connors State College - Warner
Northern Oklahoma College - Tonkawa
Northern Oklahoma College - Stillwater
Northern Oklahoma College - Enid
University Center at Ponca City - Ponca City
Last edited on
sohguanh (1236)
Your header file indicate you are ready to use C++ classes so why not use the standard C++ STL algorithm classes also ?

I notice you write your own heap sort but if you can use the sort function provided is better.

http://www.cplusplus.com/reference/algorithm/sort/
Xzi (26)
Well I have to use a heap sort and that doesn't look like a heap sort.. is it? And I'm not exactly sure what the standard C++ STL Algorithm classes are. Can you explain?
Xzi (26)
Ok I did a little searching and I found them.
Topic archived. No new replies allowed.