Sorting Algorithms (See related posts)

This code uses a variety of sorting methods. This code compiles with Borland C++ 5.0 it's useful for seeing how to duplicate the algorithms in other languages. Each sort is found in a separate function called in the main function. This version uses a vector and can sort up to 5 million numbers(possibly more). I suggest larger vectors use the quicksort, unless you want to wait a few days. I find the code fairly concise it makes random numbers depending on the amount you specify for sorting and then outputs the time in seconds to sort the number vector.

It uses an option menu and makes use of
-Bubble Sort
-Selection Sort
-Insertion Sort
-Shell Sort
-Quick Sort

   1  
   2  #include "iostream.h"
   3  #include "stdlib.h"
   4  #include "time.h"
   5  #include "conio.h"
   6  #include "vector.h"
   7  using namespace std;
   8  // VIEW RESULTS
   9  void view_sort(vector <int> arr, long max)
  10  {
  11      for(long x=0;x<max;x++)
  12      {
  13          cout<<arr[x]<<"\t";
  14      }
  15  }
  16  // BUBBLE SORT
  17  vector <int> bubble(vector <int> arr, long max){
  18  int tmp;
  19  for(long i=0;i<max;i++)
  20  {
  21   for(long x=0; x<max-1-i; x++)
  22   {
  23    if(arr[x] > arr[x+1])
  24      {
  25      //r.push_back(rnd);
  26     tmp = arr[x];
  27     arr[x] = arr[x+1];
  28     arr[x+1] = tmp;
  29    }
  30   }
  31  
  32  }
  33  return  arr;
  34  }
  35  // SELECTION SORT
  36  vector <int> select(vector <int> arr, long max){
  37  int tmp;
  38  int min;
  39  for(long i=0;i<max;i++)
  40  {
  41  min = i;
  42     for(long x=i; x<max; x++)
  43     {
  44      if(arr[x] < arr[min])
  45       {
  46    min = x;
  47      }
  48     }
  49    tmp = arr[i];
  50    arr[i] = arr[min];
  51    arr[min] = tmp;
  52   }
  53   return arr;
  54  }
  55  // INSERTION SORT
  56  vector <int> insert(vector <int> arr, long max)
  57  {
  58  int i, j, index;
  59  for(i=1; i < max;i++)
  60  {
  61      index  = arr[i];
  62      j = i;
  63      while((j > 0) && (arr[j-1] > index))
  64         {
  65          arr[j] = arr[j-1];
  66          j = j-1;
  67         }
  68     arr[j] = index;
  69  }
  70  return arr;
  71  }
  72  // SHELL SORT
  73  vector <int> shell(vector <int> arr, long max){
  74  
  75  int index, i, j;
  76  for(i=1; i < max;i++)
  77  {
  78      index  = arr[i];
  79      j = i;
  80      while((j > 0) && (arr[j-1] > index))
  81         {
  82          arr[j] = arr[j-1];
  83          j = j-1;
  84  
  85        }
  86     arr[j] = index;
  87  }
  88  return arr;
  89  }
  90  /* ######## QUICK SORT ######### */
  91  void quicksort(vector <int> & arr, int start, int end){
  92  int pivot, starth, endh; // store pivot # keep start & end in memory for split
  93  starth = start;
  94  endh = end;
  95  pivot = arr[start];
  96  
  97  while(start < end)
  98  {
  99   while((arr[end] >= pivot) && (start < end))
 100    end--;
 101      if (start != end)
 102      {
 103        arr[start] = arr[end];
 104        start++;
 105      }
 106    while ((arr[start] <= pivot) && (start < end))
 107        start++;
 108      if (start != end)
 109      {
 110        arr[end] = arr[start];
 111        end--;
 112      }
 113  }
 114  arr[start] = pivot;
 115  pivot = start;
 116  start = starth;
 117  end = endh;
 118  if(start < pivot)
 119  quicksort(arr, start, pivot-1);
 120  if(end > pivot)
 121  quicksort(arr, pivot+1, end);
 122  }
 123  
 124  /* BEGIN MAIN */
 125  int main(){
 126  time_t start;
 127  long rnd = rand()%1000+1;
 128  vector <int> r;
 129  //long r[200001];
 130  long tmp;
 131  long maxnum; // if you overload this variable, beware!
 132  int option;
 133  bool stop = false;
 134  bool view = false;
 135  while(!stop){
 136  cout<<"\t\t\tAlgorithms For Sorting Numbers\n"<<endl;
 137  
 138  cout<<"Choose Method:\n[1] Bubble\n[2] Selection\n[3] Insertion\n[4] Shell Sort\n[5] Quick Sort";
 139  cin>>option;
 140  
 141  // ARRANGE ARRAY
 142  cout<<"Length (<=5000000 )\n";
 143  cin>>maxnum;
 144  
 145  if(maxnum == 1)
 146  maxnum = 1000000;
 147  
 148  for(long x=0;x<maxnum;x++)
 149  {
 150  long rnd = rand()%1000+1;
 151  //cout<<rnd<<"\t";
 152  r.push_back(rnd);
 153  }
 154  // END ARRANGE ARRAY
 155  
 156  start = time(NULL);
 157  if(option == 1)
 158  r = bubble(r,maxnum);
 159  if(option == 2)
 160  r = select(r,maxnum);
 161  if(option == 3)
 162  r = insert(r,maxnum);
 163  if(option == 4)
 164  r = shell(r,maxnum);
 165  if(option==5)
 166  quicksort(r,0,maxnum-1);
 167  time_t stopclock;
 168  stopclock = time(NULL);
 169  // print time result
 170  
 171  cout<<endl<<double(stopclock)-start<<"[seconds]";
 172  // view sort results?
 173  cout<<"\nView the sorted numbers? [1=yes||0=no]";
 174  int v;
 175  cin>>v;
 176  if(v == 1)
 177  {
 178  view = true;
 179  view_sort(r,maxnum);
 180  }
 181  // end program?
 182  cout<<endl<<"Press 0 to quit any key to continue";
 183  int s;
 184  cin>>s;
 185  if(s == 0)
 186  stop = true; clrscr();
 187  }
 188  }