Thread: Sorting Method

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    48

    Sorting Method

    Hi everyone, my team and I are trying to write a program together which will generate random numbers and display the time taken for each sorting method. We are trying to combine our 3 programs into one since each of us has written a function. I just wanted to know if we were at all close to completion. We just wanted to make sure that the functions we wrote were correct since this is the part we are concentrating on right now. We do not need answers....just a little guidance to make sure that we are on the right track.

    Output should resemble the following

    Unsorted array:
    5 1 6 2

    Sorted array (Selection Sort):
    1 2 5 6

    ""
    each sorting method
    ""



    Size Time(selection) Time(Heap) "" "" ""
    -----------------------------
    2000 0 0
    4000 0 0
    6000 0 0
    8000 0 0
    10000 0 0
    12000 0 0
    14000 0 0
    16000 0 0
    18000 0 0
    20000 0 0
    22000 0 0
    24000 1 0
    26000 1 0
    28000 1 0
    30000 1 0




    Thanks in advance for any help that is posted

    Code:
    # include <iostream.h>
    # include <conio.h>
    # include <iomanip.h>
    # include <time.h>
    # include <stdlib.h>
    # include <fstream.h>
    # define Size 30000 //need to remove the definition 
    
    void getRandomNumber(int[],int);
    void MergeSort(int[], int, int);
    void merge(int[], int, int);
    void SelectionSort(int[], int); //Remove this
    void QuickSort (int[],int); 
    void HeapSort(int[],int);
    void InsertionSort (int[],int); //or remove this
    
    
    void PrintArray(int[],int);
    
    ofstream outf("c:\\Output.txt",ios::app); //Prints output to the c: drive
    main() //Main of the Program
    {
    int Array[Size];
    clock_t start, end;
    
    getRandomNumber(Array,20);
    cout<<"Unsorted array: \n";
    outf<<"Unsorted array:"<<endl;
    PrintArray(Array,20);
    MergeSort(Array,20,20);
    cout<<"Sorted array (Merge Sort): \n"; 
    outf<<"Sorted array (Merge Sort):"<<endl; PrintArray(Array,20);
    
    getRandomNumber(Array,20);
    cout<<"Unsorted array: \n";
    outf<<"Unsorted array:"<<endl;
    PrintArray(Array,20);
    SelectionSort(Array,20);
    cout<<"Sorted array (Selection Sort): \n"; 
    outf<<"Sorted array (Selection Sort):"<<endl; PrintArray(Array,20);
    
    getRandomNumber(Array,20);
    cout<<"Unsorted array: \n";
    outf<<"Unsorted array:"<<endl;
    PrintArray(Array,20);
    QuickSort(Array,20);
    cout<<"Sorted array (Quick Sort): \n";
    outf<<"Sorted array (Quick Sort):"<<endl; PrintArray(Array,20);
    
    
    
    getRandomNumber(Array,20);
    cout<<"Unsorted array: \n";
    outf<<"Unsorted array:"<<endl;
    PrintArray(Array,20);
    HeapSort(Array,20);
    cout<<"Sorted array (Heap Sort): \n"; 
    outf<<"Sorted array (Heap Sort):"<<endl; PrintArray(Array,20);
    
    getRandomNumber(Array,20);
    cout<<"Unsorted array: \n";
    outf<<"Unsorted array:"<<endl;
    PrintArray(Array,20);
    InsertionSort(Array,20);
    cout<<"Sorted array (Insertion Sort): \n"; 
    outf<<"Sorted array (Insertion Sort):"<<endl; PrintArray(Array,20);
    
    
    //**************************
    cout<<"Size\tTime(selection)\tTime(Heap)\n";
    cout<<"-----------------------------\n";
    outf<<"Size\tTime(selection)\tTime(Heap)\n";
    outf<<"-----------------------------\n";
    //**************Major Editing
    
    for(int i=2000; i<=Size; i=i+2000)
    {
      getRandomNumber(Array,i);
      start = clock();
      SelectionSort(Array,i);
      end = clock();
    
      cout<<i<<"\t\t"<<(end-start)/CLK_TCK<<"\t";
      outf<<i<<"\t\t"<<(end-start)/CLK_TCK<<"\t";
      getRandomNumber(Array,i);
      start = clock();
      HeapSort(Array,i);
      end = clock();
      cout<<(end-start)/CLK_TCK<<endl;
      outf<<(end-start)/CLK_TCK<<endl;
    }
    getch();
    return 0;
    }
    
    void getRandomNumber(int array[],int size) { srand(time(0)); for(int i=0; i<size; i++)
      array[i]=rand()%201-100;
    }
    
    void PrintArray(int array[],int size)
    {
    for(int i=0; i<size; i++)
    {
      cout<<setw(4)<<array[i]<<((i+1)%10?" ":"\n");
      outf<<setw(4)<<array[i]<<((i+1)%10?" ":"\n"); } cout<<endl; }
    //*****************************************************************************
    void MergeSort(int a[], int left, int right)
    {
    	if(left<right) 
    	{
    		int mid=(left + right)/2;
    		MergeSort(a, left, mid);
    		MergeSort(a, mid+1, right);
    		merge(a,left,right);
    	}
    }
    
    
    void merge(int a[],int left, int right)
    {
    	int 	size=right-left+1,
    		mid=(left+right)/2;
    	int y, put;
    	int *b=new int[size];
    	int count=0;
    	for(int x=left;x<=mid;x++,count++)
    	{
    		b[count]=a[x];
    	}
    	for(x=right;x>=mid+1;x--,count++)
    	{
    		b[count]=a[x];
    	}
    	for(x=0,y=size-1,put=left;x<=y;put++)	
    	{
    		if(b[x]<=b[y])
    		{
    			a[put]=b[x];
    			x++;
    		}
    		else
    		{
    			a[put]=b[y];
    			y--;
    		}
    	}
    	delete[] b;
    }
    
    
    
    //*********************************************************************************
    void SelectionSort(int b[], int s)
    {
       int k,x,i,j;
     for(i = 0; i < s-1 ; i++)
       {
        k = i;
          x = b[i];
          for(j = i+1; j< s; j++)
           if(b[j] < x)
             {
              k=j;
                x=b[j];
             }
          b[k]=b[i];
          b[i]=x;
       }
    }
    //******************************************************************************************
    
    void choosePivot(int c[], int first, int last){
    { 
    	int  pivotIndex;
    	int mid = (first + last) / 2;
    
        if( c[ first ] <= c[ mid ] )
        {    if( c[ mid ] <= c[ last ] )  pivotIndex = mid;
              else  pivotIndex = ( c[ first ] <= c[ last ] ? last : first );
        }
        else if( c[ last ] <= c[ mid ] )  pivotIndex = mid;
        else  pivotIndex = ( c[ first ] <= c[ last ] ? first : last );
          swap( c[ first ],  c[ pivotIndex ] );
    }
    }
    
    void partition(int c[], int first, int last, int& pivotIndex)
    {
    		choosePivot(c, first, last);
    		int pivot = c[first];
    
    		int lastS1 = first;
    		int firstUnknown = first + 1;
    
    		for (; firstUnknown<=last;++firstUnknown)
    		{
    			if (c[firstUnknown]<pivot)
    			{
    				++lastS1;
    				swap(c[firstUnknown],c[lastS1]);
    			}
    		}
    		swap(c[first], c[lastS1]);
    		pivotIndex = lastS1;
    }
    
    void quicksort(int c[], int first, int last)
    {
    	int pivotIndex;
    
    	if (first<last)
    	{
    		partition(c, first, last, pivotIndex);
    
    		quicksort(c, first, pivotIndex-1);
    		quicksort(c, pivotIndex+1, last);
    	}
    }
    
    //*******************************************************************************
    void HeapSwap(int d[], int l, int k)
    {
     int temp;
     temp = d[l];
     d[l] = d[k];
     d[k] = temp;
    }
    
    void Shift(int d[], int first, int last) {  int largest = 2*first+1;
       while(largest <= last)
     {
      if(largest < last)
       if(d[largest] < d[largest+1])
        largest++;
    
      if(d[first] < d[largest])
      {
       HeapSwap(d, first,largest);
       first = largest;
       largest = 2*first+1;
          }
      else
       largest = last+1;
       }
    }
    
    void HeapSort(int d[], int size)
    {
     register int i;
     for(i = size/2-1; i >=0; --i)
        Shift(d,i,size-1);
       for(i = size-1; i > 1; --i)
     {
      HeapSwap(d, 0, i);
      Shift(d,0,i-1);
       }
     if(d[0] > d[1])
      HeapSwap(d, 0, 1);
    }
    //**************************************************************************
    void insertionSort(int e[], int n)
    {
    	for (int unsorted=1;unsorted<n;++unsorted)
    	{
    		int nextItem = e[unsorted];
    		int loc = unsorted;
    
    		for (;(loc>0) && (e[loc-1]>nextItem);--loc)
    			e[loc] = e[loc-1];
    
    		e[loc] = nextItem;
    	}
    }

  2. #2
    *this
    Join Date
    Mar 2005
    Posts
    498
    not to pounce on ya, but that merge sort function looks very very much, infact exactly like one ive seen on a tutorial: http://www.halcy0n.com/docs/doc.php?id=2 looks like you or your partners just copyed the template and changed it to a function, try coming up with it on your own its much more rewarding.

  3. #3
    *this
    Join Date
    Mar 2005
    Posts
    498
    on a side note, you might want to stick with new headers and not use old ones, for example <iostream> instead and use: using namespace std; also you can change the define to a constant integer,
    Code:
    const int SIZE = 30000;

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. best sorting method to sort half end of array
    By nitinmhetre in forum C Programming
    Replies: 2
    Last Post: 01-11-2007, 12:18 PM
  2. Name of sorting method
    By noodles in forum Tech Board
    Replies: 6
    Last Post: 10-07-2006, 01:54 AM
  3. change sorting method using polymorphism
    By Forever82 in forum C++ Programming
    Replies: 2
    Last Post: 07-31-2003, 01:21 PM
  4. Best sorting method to use
    By pelp in forum C++ Programming
    Replies: 3
    Last Post: 03-12-2003, 12:30 AM
  5. Sorting words with a fast, effincient sorting method
    By Unregistered in forum C++ Programming
    Replies: 19
    Last Post: 07-12-2002, 04:21 PM