#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

string animals[] =
 {    "aardvark",     "albatross",     "alligator",        "amoeba",
           "ant",      "anteater",      "antelope",     "armadillo",
        "baboon",           "bat",          "bear",           "bee",
        "beetle",     "butterfly",   "caprimulgus",       "caribou",
          "carp",           "cat",   "caterpillar",       "chicken",
    "chimpanzee",           "cod",        "cougar",           "cow",
          "crab",     "crocodile",          "deer",         "dingo",
           "dog",       "dolphin",          "dove",          "duck",
         "eagle",           "eel",      "elephant",           "elk",
        "ferret",      "flamingo",      "flounder",          "frog",
        "gerbil",       "giraffe",           "gnu",          "goat",
      "goldfish",       "gorilla",       "haddock",       "hamster",
          "hawk",      "hedgehog",           "hen",  "hippopotamus",
        "hyaena",        "iguana",       "jackass",      "kangaroo",
         "koala",       "lamprey",         "lemur",       "leopard",
          "lion",         "llama",       "lobster",        "monkey",
         "moose",      "mosquito",          "moth",         "mouse",
      "nematode",          "newt",       "octopus",       "opossum",
     "orangutan",        "osprey",         "otter",           "owl",
         "panda",       "panther",       "peacock",       "penguin",
      "pheasant",        "pigeon",           "pig",     "porcupine",
   "prairie-dog",        "quagga",         "quail",        "rabbit",
        "racoon",           "rat",    "rhinoceros",    "salamander",
    "sea-urchin",      "seahorse",          "seal",       "sealion",
     "semicolon",         "shark",        "shrimp",         "skunk",
         "snake",        "sphynx",        "spider",         "squid",
      "squirrel",      "starfish",      "tapeworm",         "tiger",
      "tortoise",          "tuna",        "turkey",        "turtle",
       "unicorn",       "varmint",          "vole",       "vulture",
        "walrus",       "warthog",        "weasel",        "weevil",
         "whale",     "woodlouse",    "woodpecker",          "worm",
          "yeti",         "zebra",          "zebu" };

const int numanimals = sizeof(animals) / sizeof(animals[1]);

void order(string & x, string & y)
{ if (x < y)
    return;
  string temp = x;
  x = y;
  y = temp; }

void sort(string R[], int N)
{ int steps = 0;
  for (int j = N - 2; j >= 0; j -= 1)
  { for (int i = 0; i <= j ; i += 1)
    { order(R[i], R[i+1]);
      steps += 1; } }
  cout << "Took " << steps << " steps\n"; }

int main()
{
  srandomdev();
  // randomize the array
  for (int i = 0; i < numanimals; i += 1)
  { int r1 = random() % numanimals;
    int r2 = random() % numanimals;
    string temp = animals[r1];
    animals[r1] = animals[r2];
    animals[r2] = temp; }

  for (int i = 0; i < numanimals; i += 1)
  { cout << animals[i] << "\n";
    i += 1; }
  cout << "\n";

  sort(animals, numanimals);

  for (int i = 0; i < numanimals; i += 1)
  { cout << animals[i] << "\n";
    i += 1; }
  cout << "\n"; }