-1

On the wikipedia article about quicksort, there's a sketch of a particular way to code it (the "simplest"), which I attempted

#include <cstdlib>
#include <iostream>

using namespace std;

int partition(int list[10], int high, int low);
void quicksort(int list[10], int high, int low);

int partition(int list[], int high, int low){
    int pivot = list[high];
    int i = list[low];
    int swap_temp;

    for (int j=0; j<high; j++){
        if (list[j]<pivot){
            swap_temp=list[high];
            list[high]=list[j];
            list[j]=swap_temp;
            i++;
        }
    }

    swap_temp = list[high];
    list[high]=list[i];
    list[i]=swap_temp;
    return i;
}

void quicksort(int list[], int high, int low){
    if (low<high){
        int p=partition(list, high, low);
        quicksort(list,low,p-1);
        quicksort(list,p+1,high);  
    }
}

int main() {

    int list[10]={3,5,1,6,34,224,23,62,124,57};
    int low=0, high=10;

    quicksort(list,low,high);

    for (int k=0; k<high; k++){
        cout << list[k] << endl;
    }
    return 0;
}

This compliles fine, but the output is just the original list, completely untouched. I've looked around about passing arrays to functions, and what I've done here has worked in other programs (I specifically wrote one to check, which took an array of integers and doubled each entry, and it was fine). The algorithm is entirely specified here. Why doesn't the program alter the array?

FireGarden
  • 201
  • 1
  • 7
  • 3
    You never change the list. Return it in the quicksort and then reassign – Andrew Li Aug 28 '16 at 16:51
  • 3
    The right tool to solve such problems is your debugger. You should step through your code line-by-line *before* asking on Stack Overflow. For more help, please read [How to debug small programs (by Eric Lippert)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). At a minimum, you should \[edit] your question to include a [Minimal, Complete, and Verifiable](http://stackoverflow.com/help/mcve) example that reproduces your problem, along with the observations you made in the debugger. – πάντα ῥεῖ Aug 28 '16 at 16:53
  • @AndrewL. I don't understand, I've got other code that passes a list to a (void) function, which returns nothing, though it does change the array. Moreover, how can I return an array, I didn't think that was possible. – FireGarden Aug 28 '16 at 17:08
  • @πάνταῥεῖ I don't have any bugs in the usual sense, this code compiles and runs! Also the code I provide *is* minimal, complete, and verifyable - just copy/paste, compile and run, and you'll see the problem! – FireGarden Aug 28 '16 at 17:10
  • You [can](http://stackoverflow.com/questions/3473438/return-array-in-a-function). C++ is passed by value. – Andrew Li Aug 28 '16 at 17:10
  • 1
    @FireGarden Read my comment again, read the links again. You didn't step through your code with the debugger, did you? – πάντα ῥεῖ Aug 28 '16 at 17:12
  • 2
    @AndrewL. I doubt this is the problem actually. The array decays to a pointer and will be passed further on. – πάντα ῥεῖ Aug 28 '16 at 17:13
  • Fyi, that array should be indexed 0..9 *only*. You initialize `high` to be 10, and on initial entry into`quicksort` save your pivot value via `list[10]`, which invokes undefined behavior. Probably the single most common problem when translating a 1-based wiki algorithm to C or C++ code. – WhozCraig Aug 28 '16 at 17:24
  • @FireGarden some places you are comparing with wrong values , please have a look to the correction suggested by Abhishek. – sanjeev Aug 28 '16 at 18:32

1 Answers1

1

You should right correct partition and quicksort function. I think you by mistake you pass low and high reverse order in quicksort function and for loop inside partition function you should start from low. following code is work for you.

#include <cstdlib>
#include <iostream>


using namespace std;


int partition(int list[10], int high, int low);

void quicksort(int list[10], int high, int low);


int partition(int list[], int low, int high){
int pivot = list[high];
int i = low-1;
int swap_temp;

for (int j=low; j<high; j++){
    if (list[j]<pivot){
    i++;
        swap_temp=list[j];
        list[j]=list[i];
        list[i]=swap_temp;

    }
}

i++;
swap_temp = list[high];
list[high]=list[i];
list[i]=swap_temp;
return i;

}


void quicksort(int list[], int low, int high){
if (low<high){
    int p=partition(list, low, high);
    quicksort(list,low,p-1);
    quicksort(list,p+1,high);  
}

}


int main() {

int list[10]={3,5,1,6,34,224,23,62,124,57};
int low=0, high=10;

quicksort(list,low,high-1);

for (int k=0; k<high; k++){
    cout << list[k] << endl;
}
return 0;

}
Abhishek
  • 379
  • 1
  • 8