Recursive Program

[Deadweight77]

I've been try to get an array of numbers to order them selves with a picked pivot. The numbers greater than the pivot goes one one side while the others will go on the other. I need some help on how to do this. My first problem is to first try and display the array correctly before calling the other functions in the main function. My code is of course unfinished, but I need some help along the way because my mind is on overload right now.

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

void swap(int& val1, int& val2);
int partition(int arr[], int start, int end);
void quickSort(int arr[], int start, int end);


void swap(int& val1, int& val2)
{
	int temp = val1;//putting value 1 in a temp container
	val1 = val2;
	val2 = temp;
}

int partition(int arr[], int start, int end)
{
	int pivot = arr[end];//choosing our pivot at the end of the array of numbers (you can choose the pivot in any postion)
	int i = (start - 1);//do this to continue down the path of arrays
	for (int j = start; j <= end - 1; j++)//j begins at the star of the arry and when. Now we compare the j to the pivot and move on 
	{
		if (arr[j] <= pivot)//current value being scanned is smaller than or equal to pivot
		{
			i++;//increment index
			swap(arr[i],arr[j]);//swap the two values of i and j
		}
	}
	swap(arr[i + 1], arr[end]);//swaping the pivot now infront of where the i is hence the +1
	return(i + 1);//returning the info
}

void quickSort(int arr[], int start, int end)
{
	if (start < end)//if the starting point is less than the pivot
	{
		int pi = partition(arr, start, end);
		quickSort(arr, start, pi - 1);
		quickSort(arr, pi + 1, end);
	}
}
int const MaxElements = 50;
int main()
{
	clock_t before;
	clock_t after;
	double result;
	int* num;
	int arr[] = { MaxElements };//first problem may have to do with this 
	int size, start, end;
	int sample[MaxElements];
	cout << "Enter size of set: ";
	cin >> size;
	num = new int[size];
	if (size >= MaxElements) 
	{
		cout << "set size must be less than " << MaxElements << "\n";

		system("PAUSE");
		exit(1);
	}
	for (int i = 0; i < size; i++)
	{
		cout << "Input value:";
		cin >> num[i];
		cout << arr[i] << endl;//trying to display the array here
	}

	

}

[dhayden]

When expressing a range of items in the array, I urge you to set "start" to the index of the first element and "end" to the index just past the last element in the range. This is the way the C++ standard library's iterators work. To go through the items, do for (index = start; index < end; ++index)

To print the elements in the array, let's write a function that prints a range of them. You might find it handy to call this inside partition while you're debugging your program:

void print(int arr[], unsigned from, unsigned to)
{
    for (unsigned idx=from; idx < to; ++idx) {
        cout << arr[idx] << ' ';
    }
    cout << '\n';
}

[Handy Andy]

Hello Deadweight77,

To start with I would move line 42 to between lines 4 and 5 and change the variable name to all caps. Most often I have seen it written this way:

#include <iostream>
#include <ctime>

//using namespace std;  // <--- Best not to use.
// A recent post that is worth reading. http://www.cplusplus.com/forum/beginner/258335/

constexpr size_t MAXELEMENTS{ 50 };

void swap(int& val1, int& val2);

From C++11 on you can use "constexpr" and the {}s, (the "=" is not needed), or you can just use "const" and what you have. I used "size_t", AKA "unsigned int", because its use needs to be a positive number. Negative numbers are not allowed.

Also when defining a variable as a constant capital letters are the generally accepted way for this.

In "main" you defined line 51 correctly, for the most part, so why did you get line 49 wrong. What you want is
int arr[MAXELEMENTS]{};. The empty {}s will initialize the array to all (0) zeros.

In the if statement use return 1; and use exit (1); when it is not in "main".

in the for loop. The use of line is kind of print out the array, but you are really printing out what you entered. Line 65 and 66 almost line up, but do you see any difference between them? Look close at what you enter into and what you are trying to print.

I added these for loops, at least to give you an idea and to show you what you have.

// Print out the arrays
std::cout << "\n Contents of \"arr\"\n ";

for (size_t index = 0; index < size; index++)
{
	std::cout << arr[index] << (index < size - 1 ? ", " : "\n");
}

std::cout << "\n Contents of \"num\"\n ";

for (size_t index = 0; index < size; index++)
{
	std::cout << num[index] << (index < size - 1 ? ", " : "\n");
}

At the end of "main" I use this to pause the program. This is optional.

// A fair C++ replacement for "system("pause")". Or a way to pause the program.
// The next line may not be needed. If you have to press enter to see the prompt it is not needed.
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');  // <--- Requires header file <limits>.
std::cout << "\n\n Press Enter to continue: ";
std::cin.get();

return 0;	

The "return 0;" is also optional, but sometimes makes for a good break point when debugging.

Hope that helps,

Andy