2 Replies - 2629 Views - Last Post: 17 August 2015 - 01:49 PM

#1 Syre Lancaster  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 22
  • Joined: 04-May 14

Sorting issues(Practice problem)

Posted 16 August 2015 - 11:38 PM

Hey guys, I'm working on a practice project for C++ and I've hit a bump.
Here's the information:
Write a program that creates three identical arrays, list1, list2, and list3, of 5000 elements. The program then sorts list1 using bubble sort, list2 using selection sort, and list3 using insertion sort and outputs the number of comparisons and item assignments made by each sorting algorithm.
Here's what the output is supposed to look like:
Posted Image

Now if you run the code I've got, you can see that the insertion sort comparisons are dead wrong (big old goose egg) and I think I gaffed up the selection sort assignments?
Anyway, here's the code I've got so far:
// Bravo 7-2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int minLocation(int list[], int first, int last);
void swap(int list[], int first, int second, int& exchange);
void selectionSort2(int[], int, int&, int&);
void bubbleSort2(int[], int, int&, int&);
void insertionSort2(int[], int, int&, int&);
void fillArray(int list[], int length);
void copyArray(int list1[], int list2[], int length);



int main()

{

	int list1[5000];
	int list2[5000];
	int list3[5000];

	int compBubbleSort = 0, compSelectionSort = 0, compInsertionSort = 0;
	int assignBubbleSort = 0, assignSelectionSort = 0, assignInsertionSort = 0;
	fillArray(list1, 5000);
	copyArray(list1, list2, 5000);
	copyArray(list1, list3, 5000);
	bubbleSort2(list1, 5000, compBubbleSort, assignBubbleSort);
	selectionSort2(list2, 5000, compSelectionSort, assignSelectionSort);
	insertionSort2(list3, 5000, compInsertionSort, assignInsertionSort);
	cout << "Number of comparisons---" << endl;
	cout << " Bubble sort: " << compBubbleSort << endl;
	cout << " Selection sort: " << compSelectionSort << endl;
	cout << " Insertion sort: " << compInsertionSort << endl << endl;
	cout << "Number of item assignments---" << endl;

	cout << " Bubble sort: " << assignBubbleSort << endl;

	cout << " Selection sort: " << assignSelectionSort << endl;

	cout << " Insertion sort: " << assignInsertionSort << endl << endl;

	system("pause");

	return 0;

}

int minLocation(int list[], int first, int last)

{

	int loc, minIndex;
	minIndex = first;
	for (loc = first + 1; loc <= last; loc++)
		if (list[loc] < list[minIndex])

			minIndex = loc;

	return minIndex;

}//end minLocation

void swap(int list[], int first, int second, int& exchange)

{

	int temp;
	temp = list[first];
	list[first] = list[second];
	list[second] = temp;
	exchange++;

}//end swap

void selectionSort2(int list[], int length, int& compare, int& exchange)

{

	int loc, minIndex;
	for (loc = 0; loc < length; loc++)

	{

		minIndex = minLocation(list, loc, length - 1);
		swap(list, loc, minIndex, exchange);

	}

	compare = length * (length - 1) / 2;

}



void insertionSort2(int list[], int length, int& compare, int& exchange)

{

	for (int firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++)
		if (list[firstOutOfOrder] < list[firstOutOfOrder - 1])

		{

			int temp = list[firstOutOfOrder];
			int location = firstOutOfOrder;

			do
			{

				list[location] = list[location - 1];
				exchange++;
				location--;

			}

			while (location > 0 && list[location - 1] > temp);
			list[location] = temp;

		}

}

void bubbleSort2(int list[], int length, int& compare, int& exchange)

{

	for (int iteration = 1; iteration < length; iteration++)
	{
		for (int index = 0; index < length - iteration; index++)
		{
			if (list[index] > list[index + 1])
			{
				int temp = list[index];
				list[index] = list[index + 1];
				list[index + 1] = temp;
				exchange++;

			}

		}

	}

	compare = length * (length - 1) / 2;

}

void fillArray(int list[], int length)

{

	srand(time(0));
	for (int i = 0; i < length; i++)
		list[i] = rand() % 20000;

}

void copyArray(int list1[], int list2[], int length)

{

	for (int i = 0; i < length; i++)
		list2[i] = list1[i];

}


Any help would be appreciated, especially in regards to the insertion sort. Thank yeh kindly.

Is This A Good Question/Topic? 0
  • +

Replies To: Sorting issues(Practice problem)

#2 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6966
  • View blog
  • Posts: 14,572
  • Joined: 16-October 07

Re: Sorting issues(Practice problem)

Posted 17 August 2015 - 11:33 AM

You're not doing any counting in your minLocation and you kind of need to. Ideally, move that into the selection as that's all that uses it. You could try implementing a compare function and always count in that, like you do in the swap. That should keep you more honest.

If you think about it, you only need two lists, the master and the copy for sorting. Get rid of the magic numbers.

Note to mods, this is really just C++, not the technical abomination CLI C++. If you move this to regular old C++, more folks will see it.

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#3 Syre Lancaster  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 22
  • Joined: 04-May 14

Re: Sorting issues(Practice problem)

Posted 17 August 2015 - 01:49 PM

Yeah I realized too late that it was in the wrong forum. that was my bad.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1