Section 6 - Inserting and Sorting

1A.6.1 Inserting

To test inserting a new element into an array, we will make a symbolic gesture in the direction of creating space for the new element to be placed: Anticipating a single insertion, we will make the array one element larger than the original data set. This allows us to insert an item without losing any data. It works for our current purpose, since we are timing a single insertion into a fixed-size array -- even though we are repeating the task many times. If we were designing a more accommodating data structure that grew as we inserted something, we might very well have to place the code that expanded the array into the timing loop. Instead, our symbolic gesture of allocating one extra element than we originally need can be replaced with any extra amount of memory -- we could, for example allocate double the original size and fix that amount, never allowing the data to grow beyond it. This is acceptable if we are claiming, up-front, that we know the maximum size of the array (the number of seats in concert venue is fixed, so adding a new sale to the event will never cause the array to grow beyond the capacity of the theater).

You may complain that, in the code below, we will insert a new element repeatedly, causing old data to disappear off the top of the array (see the comment a few boxes down that includes "** we lose data... **"). I repeat - we are timing the insertion, not the data allocation - and the purported data loss can be overcome by allocating more memory or using a different data structure. So it is fine for our purposes. I might not have allocated even one extra element, and the analysis would still work. The purpose of the extra allocation is to represent where, in a fixed-size array, we might make arrangements for a growing data set.

After this two-paragraph caveat, here, finally, is the code that allocates the array:

   // we add 1 to make room for an insertion
   iTunesEntry *tunesArray = new iTunesEntry[arraySize + 1];
   for (int k = 0; k < arraySize; k++)
      tunesArray[k] =  tunesInput[k];

The explanation above was a way to say you can replace the 1 with 1000, arraySize or some other expansion amount.

In order to test an insertion, we will take five positions at random and insert into these five positions over and over. The five positions are chosen to be at different places in the original tunesArray[] so we will be getting a representative result. Here is the set-up for the five positions:

   // 5 positions we will "insert at" in the larger iTunes list of 80 tunes
   int writePosition;
   const int NUM_POSITIONS = 5;
   const int NUM_INSERTIONS = 500000;
   int somePositions[NUM_POSITIONS] = {3, 67, 20, 15, 59  };

The announcement of our intention to the user and starting the clock is the same as before, so we won't repeat that here.

And here is the actual insertion loop:

   // we will do NUM_INSERTIONS insertions, throwing away tunes that run off the top
   for (int attempt = 0; attempt < NUM_INSERTIONS; attempt++)
   {
      writePosition = somePositions[ attempt % NUM_POSITIONS ];

      // move everything up one 
      for (int k = arraySize; k > writePosition; k--)
         tunesArray[k] = tunesArray[k-1];

      // now put a new tune into the free position
      tunesArray[writePosition].setArtist("Amerie");
      tunesArray[writePosition].setTitle("Outro");
      tunesArray[writePosition].setTime(63);
   }

Here is the whole program and some sample runs:

// Main file for insertion example
// CS 2C, Foothill College, Michael Loceff, creator

#include <iostream>
using namespace std;

#include "iTunes.h"

// for timing our algorithms
#include <time.h>

// ----------- prototypes -------------
void displayOneTune(iTunesEntry tune);

// --------------- main ---------------
int main()
{
   // how we read the data from files
   iTunesEntryReader tunesInput("itunes_file.txt");
   int arraySize;

   // how we test the success of the read:
   if (tunesInput.readError())
   {
      cout << "couldn't open " << tunesInput.getFileName() << " for input.\n";
      exit(1);
   }

   // create an array of objects for our own use:
   arraySize = tunesInput.getNumTunes();
   
   // we add 1 to make room for an insertion
   iTunesEntry *tunesArray = new iTunesEntry[arraySize + 1];
   for (int k = 0; k < arraySize; k++)
      tunesArray[k] =  tunesInput[k];
   
   // 5 positions we will "insert at" in the larger iTunes list of 80 tunes
   int writePosition;
   const int NUM_POSITIONS = 5;
   const int NUM_INSERTIONS = 500000;
   int somePositions[NUM_POSITIONS] = {3, 67, 20, 15, 59  };

   cout << "Doing " << NUM_INSERTIONS << " insertions in array having "
      << arraySize << " iTunes." << endl;

   // start the clock -------------------------
   clock_t startTime, stopTime; 
   startTime = clock();

   // we will do NUM_INSERTIONS insertions, throwing away tunes that run off the top
   for (int attempt = 0; attempt < NUM_INSERTIONS; attempt++)
   {
      writePosition = somePositions[ attempt % NUM_POSITIONS ];

      // move everything up one 
      for (int k = arraySize; k > writePosition; k--)
         tunesArray[k] = tunesArray[k-1];

      // now put a new tune into the free position
      tunesArray[writePosition].setArtist("Amerie");
      tunesArray[writePosition].setTitle("Outro");
      tunesArray[writePosition].setTime(63);
   }

   // how we determine the time elapsed -------------------
   stopTime = clock();

   // show list with the new tunes inserted into various places during debugging
   // for (int k = 0; k < arraySize; k++)
   //   displayOneTune(tunesArray[k]);
   //  cout << endl << endl;

   // report algorithm time
   cout << "\nAlgorithm Elapsed Time: " 
      << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC 
      << " seconds." << endl << endl;

   return 0;
}

void displayOneTune(iTunesEntry tune)
{
   //cout << tune.GetArtistLastName() << " | ";
   cout << tune.getArtist() << " | ";
   cout << tune.getTitle() << " | ";
   // cout << tune.getSTime() << " | "; 
   cout << " " << tune.convertTimeToString() << endl;
}
/* ---------------- Runs -------------------

Doing 500 insertions in array having 79 iTunes.

Algorithm Elapsed Time: 0 seconds.

Press any key to continue . . .

---------

Doing 5000 insertions in array having 79 iTunes.

Algorithm Elapsed Time: 0.015 seconds.

Press any key to continue . . .

---------

Doing 50000 insertions in array having 79 iTunes.

Algorithm Elapsed Time: 0.14 seconds.

Press any key to continue . . .

---------

Doing 500000 insertions in array having 79 iTunes.

Algorithm Elapsed Time: 1.232 seconds.

Press any key to continue . . .
---------------------------------------- */

As before, the sensitivity of timing to the number of searches should be linear, and it is.

1A.6.2 Sorting

As a representative computation, we will do a bubble sort, a very slow but easy-to-understand sorting algorithm that is built-in to our Foothill_Sort.h header file. We've seen it with simple ints, and now we do the same thing with the iTunesEntry array. Notice that we use the exact same syntax for the sort:

   arraySort(tunesArray, arraySize);

decorative pic We can do this because arraySort() is a template function, and therefore will take any data type -- that is, any data type as long as the < operator is overloaded, which it is (I did it for you). I don't expect all of you to know about template functions yet, and we will study this material soon.

Since iTunesEntry is a compound data type, we might want to sort by title one day and by time, another. So we insert a switch in the iTunesEntry class that selects which member, i.e., which field, is to be the key for the sort. This is done by calling the static iTunesEntry method SetNSortType(), and passing it one of three static class constants: SORT_BY_TIME, SORT_BY_TITLE or SORT_BY_ARTIST. Call this before you attempt the sort, and once called, the sort will obey your wishes. So the full sequence for the sort includes this static invocation. Here is the full protocol:

   // sort
   iTunesEntry::SetNSortType(iTunesEntry::SORT_BY_TIME);
   arraySort(tunes_array, array_size);

Because comparisons in our custom classes will occur so often, you will have a chance to implement your own setSortType() method in any class you design. However it is implemented, this (above) is how it is used.

All the remaining code has been explained previously, so I will now present the entire program with some (partial) output. We are doing a sort by time, but you can change this to sort on either of the other fields.

// Main file for iTunes project - bubble sort example.
// CS 2C, Foothill College, Michael Loceff, creator

#include <iostream>
using namespace std;

#include "iTunes.h"
#include "Foothill_Sort.h"

// for timing our algorithms
#include <time.h>

// ----------- prototypes -------------
void displayOneTune(iTunesEntry tune);

// --------------- main ---------------
int main()
{
   // how we read the data from files
   iTunesEntryReader tunesInput("itunes_file.txt");
   int arraySize;

   // how we test the success of the read:
   if (tunesInput.readError())
   {
      cout << "couldn't open " << tunesInput.getFileName() << " for input.\n";
      exit(1);
   }

   cout << tunesInput.getFileName() << endl;
   cout << tunesInput.getNumTunes() << endl;

   // create an array of objects for our own use:
   arraySize = tunesInput.getNumTunes();
   iTunesEntry *tunesArray = new iTunesEntry[arraySize];
   for (int k = 0; k < arraySize; k++)
      tunesArray[k] =  tunesInput[k];
   
   // show the array, unsorted
   for (int k = 0; k < arraySize; k++)
      displayOneTune(tunesArray[k]);
   cout << endl << endl;

   // how we time our algorithms -------------------------
   clock_t startTime, stopTime; 
   startTime = clock();

   // sort
   iTunesEntry::setSortType(iTunesEntry::SORT_BY_TIME);
   arraySort(tunesArray, arraySize);

   // how we determine the time elapsed -------------------
   stopTime = clock();

   // show sorted list
   for (int k = 0; k < arraySize; k++)
      displayOneTune(tunesArray[k]);
   cout << endl << endl;

   // report algorithm time
   cout << "\nAlgorithm Elapsed Time: " 
      << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC 
      << " seconds." << endl << endl;
      
   delete[] tunesArray;
   return 0;
}

void displayOneTune(iTunesEntry tune)
{
   cout << tune.getArtist() << " | ";
   cout << tune.getTitle() << " | ";
   // cout << tune.getSTime() << " | "; 
   cout << " " << tune.convertTimeToString() << endl;
}

/* --------------- Tail End of Run ----------------

...

Suzanne Vega | Luka |  3:51
Suzanne Vega | Small Blue Thing |  3:55
Bonnie Raitt | Something to Talk About |  3:47
Bonnie Raitt | I Can't Make You Love Me |  5:31
Natalie Cole | This Will Be |  2:51
Natalie Cole | Unforgettable |  3:31
Jet | Timothy |  4:20
Jet | Rip It Up |  3:20
Was (Not Was) | Where Did Your Heart Go? |  5:47
Was (Not Was) | I Blew Up The United States |  3:50


Veggie Tales | Our Big Break |  1:09
Blue Record | Bullhead's Psalm |  1:19
Yo-yo Ma | Bach: Suite for Cello No. 1 in G Major Prelude |  2:21
Caraivana | Tico-Tico No Fuba |  2:27
Yo-yo Ma | Simple Gifts |  2:34
Blue Record | Ogeechee Hymnal |  2:35
Ry Cooter | France Chance |  2:48
Natalie Cole | This Will Be |  2:51
Ry Cooter | Alimony |  2:55
Howlin' Wolf | Well That's All Right |  2:55
Nina Simone | Feeling Good |  2:57
Howlin' Wolf | Everybody's In The Mood |  2:58
John Lee Hooker | I Can't Quit You Baby |  3:02
Veggie Tales | Donuts for Benny |  3:04
Nina Simone | The Other Woman |  3:06
John Lee Hooker | Hobo Blues |  3:07
AOL Dejando Huella | Te Amo Tanto |  3:12
The Rubyz | Watch the Girl |  3:12
Reverend Gary Davis | Twelve Sticks |  3:14
Snoop Dog | Lil' Crips |  3:15
Jet | Rip It Up |  3:20
The Rubyz | Ladies and Gentleman |  3:21
Aaron Watson | The Road |  3:24
AOL Dejando Huellas | Dime Si te Vas Con El |  3:24
Sean Kingston | My Girlfriend |  3:24
Kanye West | Good Life |  3:27
Roy Buchanan | Hot Cha |  3:28
Jeff Golub | Shuffleboard |  3:30
Natalie Cole | Unforgettable |  3:31
Reverend Gary Davis | Samson and Delilah |  3:36
Snoop Dog | Think About It |  3:37
Lil Jon | Give It All U Got |  3:38
Carrie Underwood | Quitter |  3:40
Bonnie Raitt | Something to Talk About |  3:47
T-Pain | Take Your Shirt Off |  3:48
Rihanna | Russian Roulette |  3:48
Was (Not Was) | I Blew Up The United States |  3:50
Foo Fighters | Monkey Wrench |  3:50
Janiva Magness | I'm Just a Prisoner |  3:50
Suzanne Vega | Luka |  3:51
Suzanne Vega | Small Blue Thing |  3:55
Carrie Underwood | Cowboy Casanova |  3:56
Sean Kingston | Fire Burning |  3:59
Jay-Z | What We Talkin' About |  4:03
Caraivana | Noites Cariocas |  4:12
John Coltrane | In a Sentimental Mood |  4:16
Snoop Dogg | Gangsta Luv |  4:17
Jet | Timothy |  4:20
Foo Fighters | All My Life |  4:23
Terra Incogni | Lizard Skin |  4:30
Jay-Z | Empire State of Mind |  4:36
Janiva Magness | You Were Never Mine |  4:36
Steely Dan | Kid Charlemagne |  4:38
Eric Clapton | Pretending |  4:43
Mastadon | The Bit |  4:55
Terra Incognita | Clone |  4:58
Jeff Golub | Fish Fare |  4:59
Eric Clapton | Bad Love |  5:08
Steely Dan | Black Cow |  5:10
Kanye West | Stronger |  5:11
Return to Forever | Medieval Overture |  5:13
Herbie Hancock | Rockit |  5:25
Bonnie Raitt | I Can't Make You Love Me |  5:31
Snoop Dogg | That's The Homie |  5:43
Was (Not Was) | Where Did Your Heart Go? |  5:47
Mastadon | Oblivion |  5:48
Steely Dan | Haitian Divorce |  5:51
Jeff Golub | Goin' On |  5:56
McCoy Tyner | Blues On the Corner |  6:07
Nina Simone | Pirate Jenny |  6:42
John Patitucci | Monk/Trane |  7:14
Roy Buchanan | Green Onions |  7:23
John Patitucci | Sonny Side |  7:25
Herbie Hancock | Nefertiti |  7:31
John Coltrane | A Love Supreme Part 1 |  7:42
McCoy Tyner | Afro Blue |  12:22
Berliner Philharmoniker | Brahms: Symphony No. 4 in E Minor Op. 98 |  13:20
Berliner Philharmoniker | Brahms: Symphony No. 1 in C Minor Op. 68 |  13:59
Herbie Hancock | Chameleon |  15:41



Algorithm Elapsed Time: 0.001 seconds.

Press any key to continue . . .
------------------------------------------------------------- */