Sorting Algorithms

• Tweet
• 

        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  

#include "iostream.h"
#include "stdlib.h"
#include "time.h"
#include "conio.h"
#include "vector.h"
using namespace std;
// VIEW RESULTS
void view_sort(vector <int> arr, long max)
{
    for(long x=0;x<max;x++)
    {
        cout<<arr[x]<<"\t";
    }
}
// BUBBLE SORT
vector <int> bubble(vector <int> arr, long max){
int tmp;
for(long i=0;i<max;i++)
{
 for(long x=0; x<max-1-i; x++)
 {
  if(arr[x] > arr[x+1])
    {
    //r.push_back(rnd);
   tmp = arr[x];
   arr[x] = arr[x+1];
   arr[x+1] = tmp;
  }
 }

}
return  arr;
}
// SELECTION SORT
vector <int> select(vector <int> arr, long max){
int tmp;
int min;
for(long i=0;i<max;i++)
{
min = i;
   for(long x=i; x<max; x++)
   {
    if(arr[x] < arr[min])
     {
  min = x;
    }
   }
  tmp = arr[i];
  arr[i] = arr[min];
  arr[min] = tmp;
 }
 return arr;
}
// INSERTION SORT
vector <int> insert(vector <int> arr, long max)
{
int i, j, index;
for(i=1; i < max;i++)
{
    index  = arr[i];
    j = i;
    while((j > 0) && (arr[j-1] > index))
       {
        arr[j] = arr[j-1];
        j = j-1;
       }
   arr[j] = index;
}
return arr;
}
// SHELL SORT
vector <int> shell(vector <int> arr, long max){

int index, i, j;
for(i=1; i < max;i++)
{
    index  = arr[i];
    j = i;
    while((j > 0) && (arr[j-1] > index))
       {
        arr[j] = arr[j-1];
        j = j-1;

      }
   arr[j] = index;
}
return arr;
}
/* ######## QUICK SORT ######### */
void quicksort(vector <int> & arr, int start, int end){
int pivot, starth, endh; // store pivot # keep start & end in memory for split
starth = start;
endh = end;
pivot = arr[start];

while(start < end)
{
 while((arr[end] >= pivot) && (start < end))
  end--;
    if (start != end)
    {
      arr[start] = arr[end];
      start++;
    }
  while ((arr[start] <= pivot) && (start < end))
      start++;
    if (start != end)
    {
      arr[end] = arr[start];
      end--;
    }
}
arr[start] = pivot;
pivot = start;
start = starth;
end = endh;
if(start < pivot)
quicksort(arr, start, pivot-1);
if(end > pivot)
quicksort(arr, pivot+1, end);
}

/* BEGIN MAIN */
int main(){
time_t start;
long rnd = rand()%1000+1;
vector <int> r;
//long r[200001];
long tmp;
long maxnum; // if you overload this variable, beware!
int option;
bool stop = false;
bool view = false;
while(!stop){
cout<<"\t\t\tAlgorithms For Sorting Numbers\n"<<endl;

cout<<"Choose Method:\n[1] Bubble\n[2] Selection\n[3] Insertion\n[4] Shell Sort\n[5] Quick Sort";
cin>>option;

// ARRANGE ARRAY
cout<<"Length (<=5000000 )\n";
cin>>maxnum;

if(maxnum == 1)
maxnum = 1000000;

for(long x=0;x<maxnum;x++)
{
long rnd = rand()%1000+1;
//cout<<rnd<<"\t";
r.push_back(rnd);
}
// END ARRANGE ARRAY

start = time(NULL);
if(option == 1)
r = bubble(r,maxnum);
if(option == 2)
r = select(r,maxnum);
if(option == 3)
r = insert(r,maxnum);
if(option == 4)
r = shell(r,maxnum);
if(option==5)
quicksort(r,0,maxnum-1);
time_t stopclock;
stopclock = time(NULL);
// print time result

cout<<endl<<double(stopclock)-start<<"[seconds]";
// view sort results?
cout<<"\nView the sorted numbers? [1=yes||0=no]";
int v;
cin>>v;
if(v == 1)
{
view = true;
view_sort(r,maxnum);
}
// end program?
cout<<endl<<"Press 0 to quit any key to continue";
int s;
cin>>s;
if(s == 0)
stop = true; clrscr();
}
}

Tags:
• C++
• forcodegrrl

Comments

Snippets Manager replied on Tue, 2007/06/05 - 11:43am

Great post. I've used your quicksort algorithm as a basis for some academic coding I'm doing and had one suggestion. I'm sorting structs by one of their int fields and was thrown for a loop trying to extend your code. Your "pivot" variable is of the same type as your array "arr" (in my case, an electric pulse) but in the last few lines you use it as an assumed integer: arr[start] = pivot; // pivot = type of of arr pivot = start; // pivot = type int start = starth; end = endh; if(start < pivot) quicksort(arr, start, pivot-1); if(end > pivot) quicksort(arr, pivot+1, end); As long you're sorting an array of ints it works as designed. I don't know if you care, but thought I'd share. Thanks again. PS. This is a bugmenot.com account =)

• Login or register to post comments