Hey guys, I was curious if I could get some help with these two pieces of code. What I'm trying to do is count the number of comparisons and moves there are in each type of sort, now I'm not a super programmer but I kinda know my way around the language.

What I'm having problems with is putting the counters in the correct spot. Any and all help is appreciated! =)


INSERTION SORT CODE:

#include "list.cpp"
using namespace std;
void insertionSort(ListType list, int n);

int compare = 0;
int move = 0;

int main()
{
 
    
        ListType list;
        int n;
        int num;
        
       	cout << "How many trials do you want to perform: ";
		cin >> num;
		cout << "What is the size of the list you are testing: ";
		cin >> n;
		for (int i = 1; i <= num; i++)
		{
			fillList(list, n);
			insertionSort(list, n);
		}
		cout << "comparisons: " << compare/num << "\nmoves: " 
			 << move/num << endl;
        
        fillList(list, n);
        insertionSort(list, n);
        system("PAUSE");
        return 0;
}

void insertionSort(ListType list, int n)
{
        int j, k;
        element itemToInsert;
        bool stillLooking;
        // On the kth pass, insert item k into its correct position among 
        // the first k entries in array. }

        for (k = 1; k < n; ++k)
        {
            
        // Walk backwards through list, looking for slot to insert A[K] 
                itemToInsert = list[k];
                j = k - 1;
                stillLooking = true;
                while ((j >= 0) && stillLooking )
                {
                      compare++;//------------------------------------>FIX
                        if (itemToInsert  < list[j]) 
                        {
                           move++;
                                list[j + 1] = list[j]; 
                                --j;
                        }
                        else
                                stillLooking = false;
                // Upon leaving loop, J + 1 is the index 
                // where itemToInsert  belongs
                list[j + 1] = itemToInsert;
                }    
        }
}

----------------------------------------------------------------------------------------------------------------------------------------------------

SELECTION SORT CODE:

#include "list.cpp"
#include "boolean.h"

using namespace std;

void selectionSort(ListType list, int n);

int compare = 0;
int move = 0;

int main()
{
        ListType list;
        int n;
        int num;

		cout << "How many trials do you want to perform: ";
		cin >> num;
		cout << "What is the size of the list you are testing: ";
		cin >> n;
		for (int i = 1; i <= num; i++)
		{
			fillList(list, n);
			selectionSort(list, n);
		}
		cout << "comparisons: " << compare/num << "\nmoves: " 
			 << move/num << endl;
        
        fillList(list, n);
        selectionSort(list, n);
        system("PAUSE");
        return 0;
}

void selectionSort(ListType list, int n)
{
        int index; 
        element temp;

        // Make n - 1 passes through successively smaller segments

        for (int j = 0; j < n - 1; ++j) 
        {
                index = j; 
                for (int k = j + 1; k < n; ++k)  // Find index of the smallest element 
                        {
                        compare++;
                        if (list[k] <  list[index]) 
                                index = k; 
                                
                if (index != j) 
                {
                          move ++; //--------------------------> FIX
                        temp = list[index];             // Exchange must be made 
                        list[index] = list[j]; 
                        list[j] = temp;
                        
                        //printList(list, n);
                } 
        } 
} 
}

Edited 6 Years Ago by Kayano: n/a

well for class we are looking at the Big O of n deal and we have to show the number of comparisons and moves for the bubble sort, selection sort and insertion sort. I have the bubble sort working correctly but the other two aren't from what I understand about the Big O stuff. The number of comparisons is about double of the number of moves. But I get like weird numbers from both the selection sort and insertion sort.

well big O notation is like a worst case scenario of what the function will do an upper bounds. take 1,2,3,4,5,6,7,8,9 as an example. if you passed this into your sort function it would run the minimum number of times. so depending of the values of the array the sorts will run differently

So the insertion sort and selection sort may not have the same comparison/move numbers as the bubble sort?

Ex: Bubble sort
Number of Trials: 10
Size of list: 10 ( 10 random numbers in an array)
comparisons: 42
moves: 23

As for the selection sort this is what I get, and just wondering but aren't these 3 sorts supposed to be similar?

Ex: Insertion sort
Number of Trials: 10
Size of list: 10 ( 10 random numbers in an array)
comparisons: 25 (seems like the number should be nearly double)
moves: 16
And when I get to bigger numbers the comparisons and moves are almost exactly the same which seems odd to me.

the problem is you are using random numbers so the situation changes every time. also you are not using srand before the first call to rand so you are using the same set of random numbers every time.

This question has already been answered. Start a new discussion instead.