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?
//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.
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?
@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