Quick Sort - How to copy the remaining element back & rand the pv

First of all, thank you for everyone who took their time to help us, beginners, here to learn.

My question for the day is I need to create a Quick Sort program to sort 1000000 binary numbers.
The problem that I ran into is:
1. How do I copy/return L back to the right place since it should be a sorted number in the right sequence. //error: return value doesn't match the function type
2. how do I declare loc //location of partition index inside void quickSort? it kept giving me an error saying that: a value type void can't be used to initialize an entity of type int
3. while dealing with many numbers, I know that it would be best to randomize the PV/midpoint to get a better run time instead of picking the middle array as midpoint all the type as many of the numbers that I need to sort would be mostly sorted. How do I randomize numbers more than 100?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 //pv point for
void partition(int arr[], int L, int H) {
	int mid = (L + H) - 1; //how to randomize this??
	int pv = arr[mid]; 
	arr[mid] = arr[L]; //copy value of mid
	while (!L <= H) {//high to low
		while (!L <= H) {
			while (arr[L] <= pv)
			{
				if (arr[H] < pv) {
					arr[L] = arr[H];
					L++;
					break;
				}
				else {
					H--;
				}
			}
		}//low to high
		while (!L <= H) {
			while (arr[L] <= pv)
			{
				if (arr[L] > pv) {
					arr[H] = arr[L];
					H++;
					break;
				}
				else {
					L--;
				}
			}
		}
	}
	arr[L] = pv;
	return L; //error here
}

void quickSort(int arr[], int L, int H) {
	if (L < H) {
		//location of partition index, 
		int loc = partition(arr, L, H); //error here
		quickSort(arr, L, loc - 1);
		quickSort(arr, loc + 1, H);

	}
}
void functions do not return values.
this is a problem for line 35, where you try to return a value, and line 41, where you again expect a value, at the very least.
Last edited on
for random numbers may use http://www.cplusplus.com/reference/cstdlib/rand/

void foo(/*...*/); there `void' is used to say that the function does not return a value
you declared partition() as a function that does not return a value
if you want to return a value from the function, then don't declare it as a function that does not return a value
int/*returns an integer*/ partition(int arr[], int L, int H)

while (!L <= H) that may be written as while (L>H) so never, I guess
also, ¿how many times will you check that?

1
2
3
4
5
				if (arr[H] < pv) {
					arr[L] = arr[H];
					L++;
					break;
				}
you just lost whatever value was in `arr[L]'
@jonnin Thank you! I was able to run it but it seems to take way too long to sort only 10 numbers. Is there any better way to write the recursive? I was told not to do swap as it will slow it down.

nes555 didn't it meant that when arr[L] = arr [h], all it does is just copying the value in arr [L] to arr [H] and incrementing L pointer to the next one in arr[L]?
say that you have arr[] = {"hello", "brave", "new", "world"};
suppose that L=0, H=3
after you do arr[L] = arr[H]; you'll have arr[] = {"world", "brave", "new", "world"};
"hello" is lost forever and may never be recover

given that you want to sort the array, losing elements is not desired.


> it seems to take way too long to sort only 10 numbers
¿did it sort? ¿or you terminate the program as it was taking too long?
1
2
3
4
5
6
7
8
9
10
11
//say that you call partition(arr, 0, 9)
int partition(int arr[], int L, int H) {
	int mid = (L + H) - 1;
	int pv = arr[mid]; 
	arr[mid] = arr[L]; //copy value of mid
	while (!L <= H) {//not 0<=9, false
		//...
	}
	arr[L] = pv;
	return L; //0
}
your function does nothing

run through a debugger, interrupt it if it takes too long and see the backtrace


> I was told not to do swap as it will slow it down.
¿swap what?
now it's taking too long and you aren't using swap. first make it work, optimise later
Topic archived. No new replies allowed.