Can someone point out the mistake in my code? Sorry for misleading names of function arguments - rptr should be rvalue or somethings etc, I was constantly changing something. Most of it should be done using pointers. I think the mistake might be in partArr, returning invalid variable, but i dont really know.
#include <iostream>
const int ArSize = 10;
void swap(int *lptr, int *rptr) {
int tempV = *lptr;
*lptr = *rptr;
*rptr = tempV;
}
int partArr(int *arr, int lptr, int rptr) {
int pivot = (lptr + rptr) / 2;
int * leftP = &lptr;
int * rightP = &rptr;
while (true) {
while (arr[*rightP] >= pivot) --(*rightP);
while (arr[*leftP] <= pivot) ++(*leftP);
if(*rightP > *leftP) {
swap(leftP,rightP);
--(*rightP);
++(*leftP);
}
else {
return rptr;
}
}
}
void quickSort(int *arr, int ptrL, int ptrR) {
if (ptrR > ptrL) {
int arr_piv = partArr(arr, ptrL, ptrR);
quickSort(arr, ptrL, arr_piv - 1);
quickSort(arr,arr_piv+1,ptrR);
}
}
int main() {
int tab[ArSize] = {10, 40, 30, 4, 3, 312, 3, 4, 1};
int ptrL = tab[0];
int ptrR = tab[ArSize - 1];
quickSort(tab, ptrL, ptrR);
for (int x : tab)
std::cout << x << " ";
return 0;
}
Here
int * leftP = &lptr;
int * rightP = &rptr;
you take the addresses of the function paramters. When you call
swap(leftP,rightP);
then you swap the values of lptr
and rptr
. When you write
--(*rightP)
you decrement the value of rptr
. You never actually modify an element of the array.
I don't have a CS degree, hence when I want to sort an array I use std::sort
:
#include <algorithm>
#include <iostream>
#include <iterator>
int main() {
int tab[] = {10, 40, 30, 4, 3, 312, 3, 4, 1};
std::sort( std::begin(tab), std::end(tab));
for (int& x : tab)
std::cout << x << " ";
return 0;
}
If you need to implement it yourself as an exercise you should to learn how to use a debugger, otherwise you will always run into problems like this. Becoming better in coding is not so much about not making mistakes, but more about knowing how to detect and fix them and a debugger is made for exactly that.