Member Avatar for DoctorBob

So I have 4 different algorithms to sort numbers that me and my best friends wrote to see who's worked the best. They are not the greatest ..since we aren't the greatest programmers..haha but we thought it'd be fun. I thought I'd let you guys take a look at them if you want! just for fun..haha I've attached them.


ohh and if any of you know anything about asymptotic notation is there any way you could figure what the notation would be for all four algs. attached..? If not thats fine but i'm interested in finding out so when we do compare them it would help. ..p.s. don't laugh to much! I'd really like some feedback on these algs. even though they probably aren't so great!

#include<iostream>
#include<fstream>
using namespace std;

class item {
public:
  int number;
  item *next;
  item();
  ~item();
};

item::item() {
  next = NULL;
}

item::~item() {
  delete next;
}

int main(int argc, char* argv[]){
  if(argc==3){
    item* first = NULL; // first item
    item* last  = NULL; // last item
    item* temp;         // placeholder

    item* first2 = NULL; // first item
    item* last2  = NULL; // last item
    item* temp2;         // placeholder
    
    int num;
    
    int empty=-1;
    int high=-1000;
    int low=1000;
    int ele=0;


    
    ifstream file1(argv[1]);
    while (!file1.eof()) {
      file1 >> num;
      
      if (first == NULL) {
	first = new item;
	first->number = num;
	last = first;
	ele=ele+1;
      }
      else {
	temp = new item;
	temp->number = num;
	last->next = temp;
	last = temp;
	ele++;
      }
    }
    
    file1.close(); // close the input


    
    temp=first;
    while(temp){
      if(high<temp->number){
	high=temp->number;
      }
      if(low>temp->number){
	low=temp->number;
      }
      temp=temp->next;
    }
    empty=high+2;
    temp=first;
    while(ele!=1){
      for(int step=low;step<=high;step++){
	while(temp->next != NULL){
	  if(temp->number==step){
	    if(first2 == NULL){
	      first2 = new item;
	      first2->number = step;
	      last2 = first2;
	      temp->number=empty;
              step=high+1;
              temp=last;
	      //low=step;
	    }      
	    else{
	      temp2 = new item;
	      temp2->number=step;
	      temp->number=empty;
	      step=high+1;
	      last2->next=temp2;
	      last2 = temp2;
	      //low=step;
	      temp=last;
	    }
	  } 
	  else{
	    temp=temp->next;
	  }
	}
	temp=first;
      }
      ele--;
    }
    
    ofstream file2(argv[2]);
    temp2 = first2;
    int t=0;
    while (t != 1) {
      file2 << temp2->number << endl;
      if(temp2->next != NULL){
	temp2 = temp2->next;
      }
      else{
	t=1;
      }
    }
    
    file2.close(); // close the output file
    
  }
  else{
    cout<<"You didn't specify a file to open and a file to save to."<<endl;
    cout<<"Make sure you have your command line in this format:"<<endl;
    cout<<"./MMsorting infile.txt outfile.txt"<<endl;
    cout<<"Use your own names for infile (your data) and"<<endl<<" outfile (where your new data will save."<<endl;
  }
  return 0;
}
#include<iostream>
using namespace std;

const int SIZE = 10;

int split(int *array, int lower, int upper) {
  int middle;
  int temp;
  int bound = (upper - lower) + 1;

  if(bound >= 2 && bound < 4) {
    middle = (upper + lower) / 2;
    return split(array,lower,middle);
    return split(array,middle+1,upper);
  }
  else {
    for(int i=lower, j=upper; i<=j; i++, j--) {
      if(array[i] > array[j]) {
	temp = array[i];
	array[i] = array[j];
	array[j] = temp;
      }
    }
  }
  return 0;
}

int main() {
  int sortarray[SIZE]; // array of elements to sort
  int temp;            // temp placeholder
  int middle;
  int key = 0;
  srand(1000); // seed the random number generator

  /* populate the array */
  for (int i=0; i<SIZE; i++) {
    sortarray[i] = (rand()%100) + 1;
  }

  /* output the populated array */
  for (int i=0; i<SIZE; i++) {
    cout << sortarray[i] << endl;
  }

  cout << endl;

  /* initial sort */
  for(int i=0, j=SIZE-1; i <= j; i++, j--) {
    if (sortarray[i] > sortarray[j]) {
      temp = sortarray[i];
      sortarray[i] = sortarray[j];
      sortarray[j] = temp;
    } 
  }
  
  /* split */
  middle = (SIZE - 1) / 2;
  
  split(sortarray,0,middle);
  split(sortarray,middle+1,SIZE-1);
  
  for(int i=0, j=SIZE-1; i <= j; i++, j--) {
    if (sortarray[i] > sortarray[j]) {
      temp = sortarray[i];
      sortarray[i] = sortarray[j];
      sortarray[j] = temp;
    } 
  }
  
  for(int i = 0; i < SIZE; i++){ // starts the bubble sort
    for(int j = SIZE - 1; j > i; j--){ // starts the comparisons at the end of the array
      if(sortarray [j] < sortarray[j - 1]){ // checks the current element with the previous one
	key = sortarray[j]; // switches the elements if the conditions are met
	sortarray[j] = sortarray[j - 1];
	sortarray[j - 1] = key;
      }
    }
  }
  
  /* output the populated array */
  cout << endl;

  for (int i=0; i<SIZE; i++) {
    cout << sortarray[i] << endl;
  }


  return 0;
}
/*Authors Ryan Cox; Paul Day*/

/*The InsertMerge Algorithm*/

/*Algorithm Overview - This algorithm is combination of the Insertion Sort Algorithm and the Merge sort algorithm. What happens is that the linked list is split so and each half is insertion sorted.  The reason for the split is that it allows for a better case for the insertion sort therefore allowing the two halfs to sort faster.  The we merge said halves back together and come up with an algorithm thats better than Insertion sort, but not quite as good as Merge sort. The output list is in reverse order due to technical difficulties.*/

#include<iostream>
#include<fstream>
using namespace std;

class item {
public:
  int number;
  item *next;
  item *previous;
  item();
  ~item();
};

item::item() {
  next = NULL;
  previous = NULL;
}

item::~item() {
  delete next;
  delete previous;
}


int main(int argc, char* argv[]) {
  /* dynamic array stuff */
  item* first = NULL; // first item
  item* last  = NULL; // last item
  item* temp;         // placeholder
  item* temp2;        // another placeholder
  item* temp3;        // yet another placeholder

  double count = 0; //A counter to determine the length of the queue
  double halfway = 0; //This variable will determine the halfway point of the queue
  double endhere = 0;//This keeps my the second half from messing with the first half
  int tempnum1 = 0; //My first temp variable
  int tempnum2 = 0; //My second temp variable
  int outputme = 0; //This variable gets output to the outputfile

  cout<<"Importing numbers"<<endl;

  /* filehandles */
  ifstream infile(argv[1]);  // input file filehandler
  ofstream outfile(argv[2]); // output file filehandler
  int num;                   // read number from file

  /* error checking */
  if (argc != 3) {
    cout << endl << "[:usage:] ./fh <infile> <outfile>" << endl << endl;
    exit(-1);
  }

  /* read from input file */
  while (!infile.eof()) {
    infile >> num;

    if (first == NULL) {
      first = new item;
      first->number = num;
      last = first;
      count++;
    }
    else {
      temp = new item;
      temp->number = num;
      last->next = temp;
      temp->previous = last;
      last = temp;
      count++;
    }
  }

  infile.close(); // close the input file

  cout<<"Import Finished"<<endl;

  /* your algorithm goes here */

  halfway = ceil(count/2);//This determines the midpoint of my linked list

  cout<<"Mid-point found.  Insertion Sorting first half"<<endl;

  for (double i=1; i<halfway; i++)//The sort for the first half of the linked list
    {
      if (i==1)
	{
	  temp = first;
	  tempnum1 = temp->number;
	  temp2 = temp;
	  temp3=temp;
	}
      if (temp3->next != NULL)/*Temp3 is a temp pointer that is used here as a placeholder.  That prevents the algorithm from retracing
				it's steps*/
	{
	  temp3=temp3->next;
	  temp=temp3;
	  tempnum1=temp->number;
	  temp2=temp->previous;
	  
	  do//The comparisons
	    {
	      tempnum2=temp2->number;
	      
	      if (tempnum2>tempnum1)
		{
		  temp->number=tempnum2;
		  temp2->number=tempnum1;
		  
		  if (temp2->previous != NULL)
		    {
		      temp=temp2;
		      tempnum1=temp->number;
		      temp2=temp2->previous;
		    }
		}
	    }
	  while (tempnum2>tempnum1 && temp2->previous != NULL);

	}
    }
  
  cout<<"First half sorted"<<endl<<"Insertion Sorting second half"<<endl;
  
  temp3=temp3->next;//Preparing temp3 for the next halk

  for (double i=halfway; i<=count; i++)//The beginning of the next half to be sorted
    {
      if (temp3->next != NULL)//Stops temp3 from leaving the linked list
	{
	  temp3=temp3->next;
	  temp=temp3;
	  temp2=temp->previous;
	  
	  tempnum1=temp->number;
	  
	  endhere=i+1;//My variable to keep the two halves seperated.
	  
	  do//The sorting of the second half
	    {
	      tempnum2=temp2->number;
	      
	      if (tempnum2>tempnum1)
		{
		  temp->number=tempnum2;
		  temp2->number=tempnum1;
		  endhere=endhere-1;

		  if (endhere != halfway)
		    {
		      temp=temp2;
		      tempnum1=temp->number;
		      temp2=temp2->previous;
		    }
		}
	    }
	  while (tempnum2>tempnum1 && endhere!=halfway);
	}
    }
  
  cout<<"Both halves Insertion Sorted.  Commencing Merge"<<endl;
  
  temp=first;//Preparing for the Merging
  
  for (double i=1; i<halfway; i++)//This puts temp at the middle of the list
    {
      temp=temp->next;
    }
  
  temp2=last;//This puts temp2 at the end of the list
  tempnum1=0;
  tempnum2=0;
  
  temp3=temp;//This time temp3 is the stopper.  It doesn't move from the middle
  
  while (temp2->previous!=temp3 && temp->previous!=first)//The beginning of the merge
    {
      tempnum1=temp->number;//Assigning my temp variables the values
      
      tempnum2=temp2->number;
      
      if (tempnum1>tempnum2)//The comparisons
	{
	  outputme=tempnum1;//Outputme is the variable that gets output when to botht the screen and the destination file
	  temp=temp->previous;
	}
      else
	{
	  outputme=tempnum2;
	  temp2=temp2->previous;
	}
      outfile << outputme << endl;
    }
  if (temp->previous!=first)//This If/Else statement and following while statements output whichever half still has numbers leftover
    {
      while (temp->previous!=NULL)
	{
	  outfile<<temp->number<<endl;
	  temp=temp->previous;
	}
    }
  else
    {
      while(temp2->previous!=temp3)
	{
	  outfile<<temp2->number<<endl;
	  temp2=temp2->previous;
	}
    }
  
  cout<<"Sorting and outputting finished"<<endl;
  
  outfile.close(); // close the output file

}
#include <fstream>
using namespace std;

// Defines the structure for a node in the doubly-linked list.
class node {
public:
  int value;
  node *next, *prev;
  node::node() {
    next = NULL;
    prev = NULL;
  }
  node::~node() {
    delete next;
    delete prev;
  }
};

// Regular sort.
void InsertionSort(node *head, node *tail) {
  int key;
  node *left, *right = head->next;
  while (right) {
    key = right->value;
    left = right;
    while (left->prev && left->prev->value > key){
      left->value = left->prev->value;
      left = left->prev;
    }
    left->value = key;
    right = right->next;
  }
}

// Basic sort which will swap two integers if the first one is greater.
void OrderPair(int &x, int &y) {
  if (x > y) {
    int scratch = x;
    x = y;
    y = scratch;
  }
}

// Swap unordered pairs in a spiral fashion.
void SpiralPatch(node *head, node *tail) {
  node *left = head, *right = tail;
  while (left != right && left->prev != right) {
    OrderPair(left->value, right->value);
    left = left->next;
    OrderPair(left->value, right->value);
    right = right->prev;
  }
}

// This wrapper applies the spiral patch and then runs a regular sort.
void SpiralSort(node *head, node *tail) {
  SpiralPatch(head, tail);
  InsertionSort(head, tail);
}

// Main program loads input, sorts, and saves output.
int main(int argc, char* argv[]) {
  int scratch;
  node *first = NULL, *last = NULL, *temp;

  // Ensure command-line arguments.
  // Does not check if input file exists!
  if (argc != 3) return -1;

  // Load input file into list.
  ifstream infile(argv[1]);
  while (!infile.eof()) {
    infile >> scratch;
    if (infile.good()) {
      if (first) {
	last->next = new node;
	last->next->prev = last;
	last->next->value = scratch;
	last = last->next;
      }
      else {
	first = new node;
	first->value = scratch;
	last = first;
      }
    }
  }
  infile.close();

  // Apply sorting algorithm.
  SpiralSort(first, last);

  //Save output file from list.
  ofstream outfile(argv[2]);
  temp = first;
  while (temp != NULL) {
    outfile << temp->value << endl;
    temp = temp->next;
  }
  outfile.close();

  return 0;
}
  • 3 Contributors
  • 3 Replies
  • 114 Views
  • 17 Hours Discussion Span
  • Latest Post Latest Post by DoctorBob
Member Avatar for Bench

There's no such thing as a "Best" sorting algorithm. Depending on the amount of data you're holding, and how ordered the data is to start with, one algorithm may be better than the other in different situations.


If you wanted to test them out against each another, you could devise a way profiling them, eg, by measuring the time they each take to sort an array of a million randomly generated numbers, or by sorting some pre-defined sets of data and checking the number of passes.

The results are likely to be inconclusive, since there is no "best" sort algorithm. Have a look at this list of different sort methods - http://en.wikipedia.org/wiki/Sorting_algorithm

Member Avatar for Narue

>to see who's worked the best.
That's going to be difficult even if you just stick to profiling. Two of the algorithms sort arrays and two of them sort linked lists, so the innate performance will be different even without the sort. A better test would sort only linked lists or only arrays for all of the algorithms.

>They are not the greatest ..since we aren't the greatest programmers..haha
They all seem to be unique creations (or at least somewhat unconventional), so props for that.

>is there any way you could figure what the notation would be for all four algs. attached..?
Why not use this as a chance to learn how to analyze your algorithms? Anyway, this is my initial take on the sorts after a quick glance:

Ron - This is a straightforward technique. Ron is running the linked list through a pre-sort filter that swaps values (only if needed) from the outside in. If a lot of swaps are made this will make the insertion sort step faster, and if a lot of swaps aren't made, the insertion sort would have been fairly quick to begin with. The filter (called a spiral patch) takes linear time and the insertion sort takes quadratic time. The sort as a whole is O(n^2).

Brian - This is really little more than an exceptionally inefficient selection sort. I'd call it O(n^2) + O(k) because both of those factors are equally devastating to the performance of the algorithm. Brian also needs to learn how to comment his code better.

Casey - Like Ron, Casey runs the array through a linear pre-sort filter. Casey then runs the array through a quick and dirty divide and conquer sort (which itself is a recursive linear filter), runs the array through the pre-sort filter again (maybe it should be a function if you use it more than once) and finally finishes off the algorithm with bubble sort. The algorithm as a whole is O(n^2), but the linear filters could make this a pretty zippy sort in practice. I don't think bubble sort was a wise choice for the finalizer.

Paul - Despite the comments, I'd say that this is more of a one step Shell sort than a merge sort variation. It's still O(n^2), but the result is likely to be faster than just running a basic insertion sort on the linked list.

Strictly from an asymptotic perspective, Ron, Casey, and Paul are all equal but Brian falls short. My guess is that Ron will be the most consistent overall, followed by Casey, then Paul, and Brian will still fall short in all of the tests. Casey and Paul will have niche areas that perform better than Ron, but probably not sufficiently better to determine a clear winner across the board.

Take these estimates with a grain of salt. I'm simply going on a 2 or 3 minute judgment of each program, and I didn't run any of them.

Member Avatar for DoctorBob

Wow thanks for the feedback. We actually are testing these algorithms with samples of 10,100,1000,5000,10000 and 15000 sets of random numbers..except for casey's as it is seeded by a random number generator.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.