Sorting algorithms problem

[beacon]

I'm writing a program as an assignment that takes 5 sorting algorithms and and tests for the amount of time and the number of comparisons it takes to um, sort an array.

I have run into some trouble though. On lines 54-59, I previously had them placed from line 46 on. This worked out great for printing just the bubble sort, but I have to get the other four sorting algorithms in here and I was hoping to print the contents out in a for loop, as it shows on line 53.

When I attempt this, however, I get nothing but a blank executable. Any ideas?

Also, would someone please check out my sorting algorithms and see if you don't see any mistakes. My professor told us to just copy and paste them, but there were a ton of errors that I had to correct and I'm not sure if I got them all because I don't exactly know the ins and outs of the algorithms just yet. If someone does check this out, would you pay special attention to the QuickSort? I have to find a way to get that one to work using only 2 parameters and I'm pretty much out of ideas.

Thanks for the help...

MAIN.CPP

#include <iostream>
#include <fstream>
#include <ctime>
#include <iomanip>
 
#include "SortClass.h"
 
using namespace std;
 
//This copies the contents of A2 into A1
void CopyArray(int A1[],int A2[],int size){
    for(int j=0;j<size;j++){
        A1[j]=A2[j];
    }
}
 
void FillArray(int A[],int size){
    srand(29734);
    for(int j=0;j<size;j++){
        A[j]=rand()%size;
    }
}
 
void main(){
 
    int Sizes[] = {100,1000,5000,10000,50000,100000};
    int ArraySize=0;
    int * Nums;
    int * TempNums;
 
    SortClass S;
    SortResults SR[30];
 
    int count=0;
 
    //major driving loop
    for(int i=0;i<6;i++){
 
        Nums = new int[Sizes[i]] ;
        TempNums = new int[Sizes[i]];
 
        FillArray(Nums,Sizes[i]);
 
        CopyArray(TempNums,Nums,Sizes[i]);
        SR[count++] = S.BubbleSort(TempNums,Sizes[i]);
 
        delete [] Nums;
        delete [] TempNums;
 
    }//end driving loop
 
    //make another loop to print out results
    for(i=0; i<30; i++){
        cout<<SR[i].SortName<<endl;
        cout<<SR[i].Comparisons<<endl;
        cout<<SR[i].DataSetSize<<endl;
        cout<<SR[i].RunTime<<endl;
        cout<<SR[i].Swaps<<endl;
        cout<<endl<<endl;
    }
    //end loop
 
}

SORTCLASS.CPP

// SortClass.cpp: implementation of the SortClass class.
//
//////////////////////////////////////////////////////////////////////
 
#include "SortClass.h"
 
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
 
SortClass::SortClass()
{
 
}
 
SortClass::~SortClass()
{
 
}
 
SortResults SortClass::BubbleSort(int numbers[], int array_size){
 
    int i=0, j=0, temp=0;
    int comparisons=0,swaps=0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults BR;
    BR.SortName = "BubbleSort";
    BR.DataSetSize = array_size;
 
    start_time = GetTickCount();
    for (i = (array_size - 1); i >= 0; i--){
        comparisons++;
        for(j=1;j<=i;j++){
            if (numbers[j-1] > numbers[j]){
                temp = numbers[j-1];
                numbers[j-1] = numbers[j];
                numbers[j] = temp;
                swaps++;
            }
        }
    }
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    BR.Comparisons = comparisons;
    BR.Swaps = swaps;
    BR.RunTime = (run_time/1000.0);
 
    return BR;
 
}
 
void SortClass::SelectionSort(int numbers[], int array_size){
 
    int i, j, temp;
    int pos_greatest;
    int comparisons=0,swaps=0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults BR;
    BR.SortName = "BubbleSort";
    BR.DataSetSize = array_size;
 
    start_time = GetTickCount();
 
    for (i = (array_size - 1); i > 0; i--){
        pos_greatest = 0;
        for (j = 0; j <= i; j++){
            if(numbers[j] > numbers[pos_greatest]){
                pos_greatest = j;
            }
        }
        temp = numbers[i];
        numbers[i] = numbers[pos_greatest];
        numbers[pos_greatest] = temp;
    }
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    BR.Comparisons = comparisons;
    BR.Swaps = swaps;
    BR.RunTime = (run_time/1000.0);
 
    return BR;
}
 
void SortClass::InsertionSort(int numbers[], int array_size){
 
    int i, j, index;
    int comparisons=0,swaps=0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults BR;
    BR.SortName = "BubbleSort";
    BR.DataSetSize = array_size;
 
    start_time = GetTickCount();
 
    for (i = 1; i < array_size; i++){
        index = numbers[i];
        j=i;
        while ((j > 0) && (numbers[j-1] > index)){
            numbers[j] = numbers[j-1];
            j = j-1;
        }
        numbers[j] = index;
    }
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    BR.Comparisons = comparisons;
    BR.Swaps = swaps;
    BR.RunTime = (run_time/1000.0);
 
    return BR;
}
 
void SortClass::ShellSort(int numbers[], int array_size){
 
    int i, j, increment, temp;
    int comparisons=0,swaps=0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults BR;
    BR.SortName = "BubbleSort";
    BR.DataSetSize = array_size;
 
    start_time = GetTickCount();
 
    increment = 3;
    while (increment > 0){
        for (i = 0; i < array_size; i++){
            j = i;
            temp = numbers[i];
            while ((j >= increment) && (numbers[j-increment] > temp)){
                numbers[j] = numbers[j - increment];
                j = j - increment;
            }
            numbers[j] = temp;
        }
        if (increment/2 != 0)
            increment = increment/2;
        else if (increment == 1)
            increment = 0;
        else
            increment = 1;
    }
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    BR.Comparisons = comparisons;
    BR.Swaps = swaps;
    BR.RunTime = (run_time/1000.0);
 
    return BR;
}
 
void SortClass::QuickSort(int numbers[], int start, int end){
 
    int i = start;
    int k = end;
    int comparisons=0,swaps=0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults BR;
    BR.SortName = "BubbleSort";
    BR.DataSetSize = array_size;
 
    start_time = GetTickCount();
 
    if (end - start >= 1){
        int pivot = numbers[start];
 
        while (k > i){
            while (numbers[i] <= pivot && i <= end && k > i)
                i++;
            while (numbers[k] > pivot && k >= start && k >= i)
                k--;
            if (k > i)
                swap(numbers, start, k);
        }
        swap(numbers, start, k);
 
        QuickSort(numbers, start, k-1);
 
 
    }
    else{
        return;
    }
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    BR.Comparisons = comparisons;
    BR.Swaps = swaps;
    BR.RunTime = (run_time/1000.0);
 
    return BR;
}
 
void SortClass::swap(int numbers[], int index1, int index2){
 
    int temp = numbers[index1];
    numbers[index1] = numbers[index2];
    numbers[index2] = temp;
}
 

SORTCLASS.H

// SortClass.h: interface for the SortClass class.
//
//////////////////////////////////////////////////////////////////////
 
#include <iostream>
#include <string>
#include <windows.h>
#include <stdio.h>
 
using namespace std;
 
#if !defined(AFX_SORTCLASS_H__B90D8BDD_9661_4EC7_9789_4EB5E7E4B0EA__INCLUDED_)
#define AFX_SORTCLASS_H__B90D8BDD_9661_4EC7_9789_4EB5E7E4B0EA__INCLUDED_
 
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
 
struct SortResults{
    string SortName;
    int DataSetSize;
    unsigned int Swaps;
    int Comparisons;
    double RunTime;
};
 
class SortClass  
{
 
 
public:
 
    SortClass();
    ~SortClass();
    SortResults BubbleSort(int[], int);
    SortResults SelectionSort(int[], int);
    SortResults InsertionSort(int[], int);
    SortResults ShellSort(int[], int);
    SortResults QuickSort(int[], int, int);
    SortResults swap(int[], int, int);
 
};
 
#endif // !defined(AFX_SORTCLASS_H__280BFDFC_EE79_43E7_B877_EE25B636B5FC__INCLUDED_)
 

P.S. Sorry for such a looooooooonnnnn ggg post!

[Ganon11]

I'm not sure why your loop isn't working in your driver program (the one with main()), but I can help with your QuickSort question. The two parameter QuickSort should need just the array of numbers and its length in an int variable (an int[] and an int - that's two parameters). However, this short method only calls your three parameter QuickSort with the array, the start (which index is the start?), and the end (which index is the end?). The three-parameter QuickSort can be private, to prevent anyone from using it incorrectly. Now your QuickSort looks just like the other sorting methods, and people can use it in the same way.

[beacon]

I noticed the part about the quick sort after the fact and I had already changed it to resemble what you described. Thanks for pointing it out though because if I hadn't seen it I surely would have been greatful for the help.

[beacon]

I got this straightened out. In my frustration I started playing around with numbers in the array and was telling the program to loop through and sort for 30 data sets in my struct.

I must have been have asleep when I did this...

[beacon]

SortResults SortClass::BubbleSort(int numbers[], int array_size){
 
    int i=0, j=0, temp=0;
    int comparisons=0,swaps=0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults BR;
    BR.SortName = "BubbleSort";
    BR.DataSetSize = array_size;
 
    start_time = GetTickCount();
    for (i = (array_size - 1); i >= 0; i--){
        comparisons++;
        for(j=1;j<=i;j++){
            if (numbers[j-1] > numbers[j]){
                temp = numbers[j-1];
                numbers[j-1] = numbers[j];
                numbers[j] = temp;
                swaps++;
            }
        }
    }
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    BR.Comparisons = comparisons;
    BR.Swaps = swaps;
    BR.RunTime = (run_time/1000.0);
 
    return BR;
 
}
 
SortResults SortClass::SelectionSort(int numbers[], int array_size){
 
    int i, j, temp;
    int pos_greatest;
    int comparisons=0,swaps=0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults SS;
    SS.SortName = "SelectionSort";
    SS.DataSetSize = array_size;
 
    start_time = GetTickCount();
 
    for (i = (array_size - 1); i > 0; i--){
        pos_greatest = 0;
        for (j = 0; j <= i; j++){
            comparisons++;
            if(numbers[j] > numbers[pos_greatest]){
                pos_greatest = j;
            }
        }
        temp = numbers[i];
        numbers[i] = numbers[pos_greatest];
        numbers[pos_greatest] = temp;
        swaps++;
    }
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    SS.Comparisons = comparisons;
    SS.Swaps = swaps;
    SS.RunTime = (run_time/1000.0);
 
    return SS;
}
 
SortResults SortClass::InsertionSort(int numbers[], int array_size){
 
    int i, j, index;
    int comparisons=0,swaps=0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults IS;
    IS.SortName = "InsertionSort";
    IS.DataSetSize = array_size;
 
    start_time = GetTickCount();
 
    for (i = 1; i < array_size; i++){
        index = numbers[i];
        j=i;
        while ((j > 0) && (numbers[j-1] > index)){
            comparisons++;
            numbers[j] = numbers[j-1];
            j = j-1;
        }
        numbers[j] = index;
        swaps++;
    }
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    IS.Comparisons = comparisons;
    IS.Swaps = swaps;
    IS.RunTime = (run_time/1000.0);
 
    return IS;
}
 
SortResults SortClass::ShellSort(int numbers[], int array_size){
 
    int i, j, increment, temp;
    int comparisons=0,swaps=0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults ShS;
    ShS.SortName = "ShellSort";
    ShS.DataSetSize = array_size;
 
    start_time = GetTickCount();
 
    increment = 3;
    while (increment > 0){
        for (i = 0; i < array_size; i++){
            j = i;
            temp = numbers[i];
            while ((j >= increment) && (numbers[j-increment] > temp)){
                comparisons++;
                numbers[j] = numbers[j - increment];
                j = j - increment;
            }
            numbers[j] = temp;
            swaps++;
        }
        if (increment/2 != 0)
            increment = increment/2;
        else if (increment == 1)
            increment = 0;
        else
            increment = 1;
    }
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    ShS.Comparisons = comparisons;
    ShS.Swaps = swaps;
    ShS.RunTime = (run_time/1000.0);
 
    return ShS;
}
 
SortResults SortClass::QuickSort(int numbers[], int array_size){
 
                int comparisons=0,swaps=0;
                int start = 0, end = 0;
 
    DWORD start_time,end_time,run_time;
 
    SortResults QS;
    QS.SortName = "QuickSort";
    QS.DataSetSize = array_size;
 
    start_time = GetTickCount();
 
    quickSort(numbers, start, end);
 
    end_time = GetTickCount();
 
    run_time = end_time-start_time;
 
 
    QS.Comparisons = comparisons;
    QS.Swaps = swaps;
    QS.RunTime = (run_time/1000.0);
 
    return QS;
 
}
 
void SortClass::quickSort(int numbers[], int start, int end){
 
    int i = start;
    int k = end;
 
    if (end - start >= 1){
        int pivot = numbers[start];
 
        while (k > i){
            while (numbers[i] <= pivot && i <= end && k > i)
                i++;
            while (numbers[k] > pivot && k >= start && k >= i)
                k--;
            if (k > i){
                comparisons++;
                swap(numbers, start, k);
                                                }
        }
        swaps++;
        swap(numbers, start, k);
                                quickSort(numbers, start, k-1);
                                quickSort(numbers, k+1, end);
 
 
    }
    else{
        return;
    }
 
}
 
void SortClass::swap(int numbers[], int index1, int index2){
 
    int temp = numbers[index1];
    numbers[index1] = numbers[index2];
    numbers[index2] = temp;
}
 

My last dilemma with this is that I have to count the number of comparisons and swaps each sort makes. I got the bubble, insertion, selection, and shell to work, but not the quick. Can anybody tell me where I should place my comparisons and swap counters to get them to increment correctly?

Have I even declared the quickSort function correctly in the QuickSort class? Do I need to in order to get the QuickSort to work properly?

Also, please check that I have them placed in the correct location for the other sorts. I believe I do, but it never hurts to have a trained eye take a look.

Thanks...

[Ganon11]

You make a comparison at every execution of your inner while loops, too, so you should have comparisons++ in there too.

[beacon]

So if I have a while loop, I need to place a comparison in every inner while loop? What about the swaps? Were they in the right place?

Also, I'm still not sure how to get the quick sort to test for anything. I don't think I have called the function correctly or something.

[Laharl]

Your swaps look OK, I think.

As to testing quicksort, you can put in some printing statements to print the array after each swap, or each recursive call, or whatever interval you feel works. This may require a printArray function so you're not constantly rewriting the same code.