OpenStudy (bgrg007):

For quicksort, how can i change it so the output returns the array of index instead of the sorted elements?

OpenStudy (anonymous):

I need to see your code so far to understand what you mean.

OpenStudy (bgrg007):

OpenStudy (bgrg007):

like for example index - 0 1 2 3 4 elements - 7 10 5 2 6 so output comes as - 3 2 4 0 1

OpenStudy (rsmith6559):

That information is destroyed during the sort. You'd have to make a copy of the unsorted data and search it after the sort for each of the items to find their original position.

OpenStudy (bgrg007):

can u show how to do it plz?

OpenStudy (bgrg007):

but essentially, this is what is required of me after implementing the regular quicksort. Change the type of key to real value (double). • Put the array index in the Quicksort algorithm. • When you change locations of two element in the array; you should change the location of the curresponding variables in the index array. • You need to return the index array as the result.

OpenStudy (anonymous):

Your approach would seem to work. Can you paste the original algorithm you are using for the quicksort?

OpenStudy (e.mccormick):

Have an array of the indices that is generated parallel to the one you are sorting. When you do the swaps for sorting the main array, also swap the index array. Then the index array will be in the sorted order.

OpenStudy (bgrg007):

//This is my original regular quicksort algorithm. Now, I have to return the index instead by following the instructions( bullets) i wrote above. #include <iostream> #include <algorithm> using namespace std; int partition(int A[], int p, int r){ int x = A[r]; int i = p-1; for (int j=p;j<r;j++) { if (A[j]<=x) { i=i+1; swap(A[j],A[i]); //exchange a[i] to a[j] } } swap(A[i+1],A[r]); //exchange a[i+1] with a[r] return i+1; } void quicksort(int A[], int p, int r) { if (p<r){ int q = partition(A,p,r); quicksort(A,p,q-1); quicksort(A,q+1,r); } } int main(){ int A[]={2,8,7,1,3,5,6,4}; int n=sizeof(A)/sizeof(A[0]); quicksort(A,0,n-1); for (int i=0;i<n;i++){ cout <<A[i]<< " "; } return 0; }

OpenStudy (e.mccormick):

Just add an int array that is the same size as your data array. Then fill it with the numbers 0 to n where n is the length - 1. In your swap, swap spots in it the same time as you swap ones in the main array. Let me give you an example of how this is useful. I needed to sort some very large files, but I only had 64K of addressable space in static addressing. So what I did was make an array of the first 4 characters and the addresses of the lines in the file. I sorted based on the first 4 characters, but swapped both the first four and address arrays. Then I loaded each block of matching first four and sorted those lines before writing them to output. Because they were already partially sorted, no block was very large. By knowing the address of each line, I was able to directly load the lines, no matter where they were in the file. What you are doing is something simple, but rather than sorting the data and the address, you are doing the data and an array that represents the indices. Then you can output the sorted indices however is needed.