Ascending Sort

[stoneJax]

I am trying to create a function that will reorganize an array of ints in ascending order by doing it recursively. The program stalls with a blinking cursor and does not display any test cout statements in the function. I am not seeing why the program is not making it into the function.

Also, can we use C++ swap function to swap two elements in an array of ints, or is that only used for chars? I tried creating my own swap function but I can't test anything till I get past where I'm at.

  #include <iostream>
using namespace std;

void ascendingSort(int array[]);
void swap(int *ptr1, int *ptr2);

int main()
{
	const int SIZE = 256;
	int digits[SIZE]{};
	

	cout << "Enter digits: ";
	for (int i = 0; i < SIZE; i++) {
		cin >> digits[i];
		cout << digits[i];
	}
	ascendingSort(digits);

	system("pause");
	return 0;
}



void ascendingSort(int array[])
{
	cout << "test1";
	int start = 0, end = sizeof(array) + 1, min;

	if (start > end)
		return;

	min = start;
	while (start < end) {
		if (array[start] > array[start+1])
			swap(array[start], (array[start+1]));
	}
	 ascendingSort(array+1);

}



void swap(int *ptr1, int *ptr2)
{
	cout << "test2";
	int hold;
	hold = *ptr1;
	*ptr1 = *ptr2;
	*ptr2 = hold;
}

[salem c]

Your while loop never actually modifies start.
So it never gets anywhere near end.

Also, as sort algorithms go, it's inefficient.

[Handy Andy]

Hello stoneJax,

First question: Do you know what the value of "end" is?

Second Question: Should "end" reflect the full size of the array or just the portion used?

As I look at your code the for loop in "main" should have a way out so that one does not have to enter 256 numbers before you continue.

You could do something like: for (int i = 0; i < SIZE && i != -99; i++) or use an if statement inside the for loop.

This is a case where you could do this:

int count{};

for (count = 0; count < SIZE && count != -99; count++)
{
		cin >> digits[i];
		cout << digits[i];
}

This way when the for loop ends "count" will hold the value of how many elements of the array are used, which you can send to the function to use for the "end" value.

Another thing to consider is the value of "end".

Should you try to sort the full 256 elements of the array eventually array[start+1] will exceed the boundary of the array and there is no way to tell what it is trying to access. This is a very likely cause for the program hanging up.

"std::swap()" is found in the "<algorithm>" header file if you want to use it.

Another thing I noticed is the in the while loop the value of "start" never changes. Since "start" is always zero it becomes an endless loop.

Here is a trick for testing your code:

int main()
{
	const int SIZE = 256;
	int digits[SIZE]{ 10, 5, 200, 100, 50, 20, 1, 0, 45, 90};
	int count{ 10 };

	//cout << "Enter digits: ";
	//for (int i = 0; i < SIZE; i++)
        //{
		//cin >> digits[i];
		//cout << digits[i];
	//}

	ascendingSort(digits, count);  // <--- Added second parameter. Function needs changed. 

This way you can test the function without having to enter numbers each time the program runs.

Hope that helps,

Andy

[jonnin]

std::swap can be used with anything that has an assignment operator I think.
so yes you can use it for int, char, double, etc.

are you inventing your algorithm from scratch? If so, draw some pictures, lay out the steps it takes to do the work on paper. I think I see where you are going, it looks like a recursive bubble sort.

[stoneJax]

After looking into sizof() more I can see that it returns the number of bytes and not the length of my int array like I was trying. I originally hard coded an int array with five elements and the sizeof() gave me 4; I thought that it counted elements 0 - 4, so I just added the plus one to get 5 but that was totally wrong. For now I am just going to stick with a hard coded array of 10 elements rather than the large array above that takes user input until I get the function working.

So decided to rethink my algorithm based on selection sort, and doing so recursively. I created a function that finds the smallest value in the int array, tested it from main and it works. However, an excetion is thrown in the minIndex function when it is called from ascendingSort() function saying "write access violation." What is wrong with my ascendingSort() that is causing this?

For ascendingSort() I am trying to locate the smallest value in the array, store that to the first element, then move one element over and repeat until the end is reached.

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

void ascendingSort(int array[]);
//void swap(int *ptr1, int *ptr2);
int minIndex(int a[]);
const int SIZE = 10;

int main()
{
	int digits[SIZE]{ 10, 5, 200, 100, 50, 20, 1, 0, 45, 90 };
	
	ascendingSort(digits);
	//cout << minIndex(digits) << endl;

	system("pause");
	return 0;
}



void ascendingSort(int array[])
{
	int start = 0, end = SIZE, smallest = 0;
	
	if (start == end)
		return;
	
	smallest = minIndex(array);
	*array = smallest;
	start++;
	ascendingSort(array+1);
}



int minIndex(int a[])
{
	int smallest = a[0];

	for (int i = 0; i < SIZE; i++) {
		if (a[i] < smallest)
			smallest = a[i];
		
	}
	return smallest;
}

[jonnin]

ok. a few things.

start = 0.
if start == end which == size. this will not happen.
start++ does not work like that. every recursive call makes a new copy of the start variable at zero. to make it work like you want, you need the keyword static in front of it.
also, you are trying to do things to array as if it were a pointer. it is not a pointer. this is bad. It may work here, but I changed it because its late here and it bothered me.

sec
I have fixed it for you. changes
-minindex now actually returns the INDEX of the smallest, not the smallest value.
-swapped the values in the sort. if you have 321 and find 1 and put it at the top without swapping, your array is now 121. then you find 1 and put it at the new top and get 111. this is not useful.
- fixed the pointer abuse
-fixed minindex to iterate correctly (needs size passed in, and size is not the original array size, its the CURRENT size as you peel one off size every recursive call, see?)
-static
-removed smallest, not needed.
etc... I think its right now. If not, its a lot closer :) Take anything I say with a grain of salt, I am tired and am only trying to help -- this is complicated, and I felt you would be better off seeing it fixed than struggling to fix all these issues at once.

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


void ascendingSort(int *array);
int minindex(int *a, int size);
const int SIZE = 10;

int main()
{
	int digits[SIZE]{ 10, 5, 200, 100, 50, 20, 1, 0, 45, 90 };
	int *safe = digits;
	ascendingSort(safe);
	//cout << minIndex(digits) << endl;
     for(int i = 0; i < SIZE; i++)
		  cout << digits[i] << endl;
	//system("pause");
	return 0;
}



void ascendingSort(int *array)
{
	static int start = 0;    
		
	if (start == SIZE)
		return;
	
    int temp = 	array[0];
	int index = minindex(array, SIZE-start); 
	*array = array[index];
	array[index] = temp;
	
	start++;
	ascendingSort(array+1);
}



int minindex(int *a, int size)
{
	int smallest = 0;
	for (int i = 0; i < size; i++) 
	{
		if (a[i] < a[smallest])
			smallest = i;		
	}
	return smallest;
}

this is more code, more complicated code, and significantly slower than even a crude shell sort. You may want to check that one out (its one of my favorite algorithms).

[stoneJax]

Thanks jonnin! That is very helpful, makes sense, and it is working now. Seems like my thought process was trying to handle it correctly but I'm not grounded in the tools solid enough to apply everything correctly. There is a lot to learn and a lot to remember.

I'm curious though on a couple things. Why did you create the *safe pointer instead of passing digits? Also why is it bad to use an array like a pointer? The name of an array is just a pointer to the address of the first element correct? So this allows us to use it to our advantage for pointer manipulations.

I'll check out that algorithm too. For this I am supposed to create the function with selection sort
and doing it recursively. Maybe this can be done more efficiently but I'm happy for now.

[jonnin]

safe pointer is because you can get into trouble playing with array names as if they were pointers when you start doing pointer math on them. I *think* you code was fine as it was (give it a try with just digits now that it works?) but I was tired and I just did it to avoid any trouble while I was fixing everything. It may be a totally unnecessary change. We had a long discussion on that not long ago... the name of an array is automatically converted to a pointer for you via c++ syntax. It isn't actually a true pointer, but you can for sure use it like one most of the time, just do not attempt to change it.

You will likely never write a sort for real code; its built into the language (and many other languages as well). There are 4 or 5 sorting algorithms that you should know, not because sorting is interesting, but because they can be modified to do other things or teach an approach that is adaptable to other algorithms that you would have to write.

lets take bucket sort. this is the fastest sort but it only works on integer type values where you have a range of data that is manageable (so, a 64 or 128 bit range of ints, the bucket won't even fit in memory)

for your data, unsigned char is big enough for the biggest value (a few copies of the same entry)
lets increase size and add some extra values...

int digits[SIZE]{ 10, 5, 200, 100, 50,100, 20, 1, 0,100, 45, 90 };

and make a bucket:
unsigned char b[256] = {0};

for(int x = 0; x < SIZE; x++)
 bucket[digits[x]]++;

and bam your data is sorted.  
what can we do with that?  A lot more than just a sort.

 for(int x = 0; x < 256; x++)
  for(int y = 0; y < b[x]; y++)
    cout << x << endl;  //the sorted list. 

 for(int x = 0; x < 256; x++)
   if(b[x]) cout << x << endl;  //a deduplicated, sorted output of the list. 

int maxct = 0, index = 0;
 for(int x = 0; x < 256; x++)
        if(b[x] > maxct)
        {
           maxct = b[x];
           index = x;
       }
 cout << "there were "<< maxct << " copies of " << index << endl;

//we found that 100 was the most common value with whatever I put in # of copies.
so that is 2 modifications to the sort algorithm to do new things (deduplicate and count). The other major sort algorithms can all be twisted to do other stuff. As a side note, if you had billions of values to sort or count or whatever in the range 0-200, you only need a small array (of say long long type) to store all the data this way, as all the repeats are just stored as counters in the array.

I don't know that bubble/selection/insertion/ N*N sorts have a lot of alternate uses. Bucket, quicksort, shell, merge all do for sure.

[stoneJax]

So I tried it with just digits and it seems to be working good.

I appreciate the insight on why I can have an assignment like this (or other sorting algorithms like you mention) although I may never have to write one in real life. Nice to understand that it will train one for manipulating algorithms for a particular need.

Wow that bucket sort looks way more efficient! So the bucket sort above, say for example, whenever an index containing 100 is traversed then bucket[]++ will count 1 to it's 100th index position. Given that 100 appears 3 times in the array above, when the loop is finished then bucket[100] = 3.

This looks like a strong tool and a good one to remember!

[jonnin]

yes, that is right, 100 = 3

Its the fastest possible... touches each item only once.
unfortunately its limited to integers with a 'relative to your computer's power' range. Its useless on an array of random 64 bit ints or high precision doubles (you can multiply by 100 or something if you just have a few digits) on a typical PC. The dramatic increase in ram every computer generation lets us do a lot with it now, though (even phone numbers and ID numbers like social security fit easily). c++ lets you do some fun stuff too, you can take the address of bucket[50] to a pointer and it would support (almost, zero takes a slot) +- 50 (to sort positive/negative ints)

[stoneJax]

Thank jonnin! I appreciate all the info. I'll keep that one in my back pocket and remember to pull it out whenever I get a chance to practice it!