<p>I would like to sort an array in ascending order using <code>C/C++</code>. The outcome is an array containing element indexes. Each index is corespondent to the element location in the sorted array.</p>
<p><strong>Example</strong></p>
<pre><code>Input:  1, 3, 4, 9, 6
Output: 1, 2, 3, 5, 4
</code></pre>
<p><strong>Edit:</strong> I am using shell sort procedure. The duplicate value indexes are arbitrarily chosen based on which duplicate values are first in the original array.</p>
<h3>Update:</h3>
<p>Despite my best efforts, I haven't been able to implement a sorting algorithm for an array of pointers. The current example won't compile.</p>
<p>Could someone please tell me what's wrong?</p>
<p>I'd very much appreciate some help!</p>
<pre><code>void SortArray(int ** pArray, int ArrayLength) 
{
    int i, j, flag = 1;    // set flag to 1 to begin initial pass
    int * temp;    // holding variable orig with no *
    
    for (i = 1; (i &lt;= ArrayLength) &amp;&amp; flag; i++)
    {
        flag = 0;
        for (j = 0; j &lt; (ArrayLength - 1); j++)
        {
            if (*pArray[j + 1] &gt; *pArray[j])    // ascending order simply changes to &lt;
            { 
                &amp;temp = &amp;pArray[j];    // swap elements
                &amp;pArray[j] = &amp;pArray[j + 1];    //the problem lies somewhere in here
                &amp;pArray[j + 1] = &amp;temp;
                flag = 1;    // indicates that a swap occurred.
            }
        }
    }
};
</code></pre>

[{'answer_id': 13477, 'author': 'Patrick', 'author_id': 429, 'author_profile': 'https://Stackoverflow.com/users/429', 'pm_score': 0, 'selected': False, 'text': "<p>Well, there's a trival n^2 solution.</p>\n\n<p>In python:</p>\n\n<pre><code>newArray = sorted(oldArray)\nblankArray = [0] * len(oldArray)\nfor i in xrange(len(newArray)):\n  dex = oldArray.index(newArray[i])\n  blankArray[dex]  = i\n</code></pre>\n\n<p>Depending on how large your list is, this may work. If your list is very long, you'll need to do some strange parallel array sorting, which doesn't look like much fun and is a quick way to introduce extra bugs in your code.</p>\n\n<p>Also note that the above code assumes unique values in oldArray. If that's not the case, you'll need to do some post processing to solve tied values.</p>\n"}, {'answer_id': 13481, 'author': 'Zooba', 'author_id': 891, 'author_profile': 'https://Stackoverflow.com/users/891', 'pm_score': 4, 'selected': True, 'text': "<p>Since you're using C++, I would do it something like this. The <code>SortIntPointers</code> function can be any sort algorithm, the important part is that it sorts the array of pointers based on the <code>int</code> that they are pointing to. Once that is done, you can go through the array of pointers and assign their sorted index which will end up in the original position in the original array.</p>\n\n<pre><code>int* intArray; // set somewhere else\nint arrayLen;  // set somewhere else  \n\nint** pintArray = new int*[arrayLen];\nfor(int i = 0; i &lt; arrayLen; ++i)\n{\n    pintArray[i] = &amp;intArray[i];\n}\n\n// This function sorts the pointers according to the values they\n// point to. In effect, it sorts intArray without losing the positional\n// information.\nSortIntPointers(pintArray, arrayLen);\n\n// Dereference the pointers and assign their sorted position.\nfor(int i = 0; i &lt; arrayLen; ++i)\n{\n    *pintArray[i] = i;\n}\n</code></pre>\n\n<p>Hopefully that's clear enough.</p>\n"}, {'answer_id': 13482, 'author': 'Marius', 'author_id': 1585, 'author_profile': 'https://Stackoverflow.com/users/1585', 'pm_score': 2, 'selected': False, 'text': '<p>create a new array with increasing values from 0 to n-1 (where n is the length of the array you want to sort). Then sort the new array based on the values in the old array indexed by the values in the new array. </p>\n\n<p>For example, if you use bubble sort (easy to explain), then instead of comparing the values in the new array, you compare the values in the old array at the position indexed by a value in the new array:</p>\n\n<pre><code>function bubbleRank(A){\n  var B = new Array();\n  for(var i=0; i&lt;A.length; i++){\n    B[i] = i;\n  }\n  do{\n    swapped = false;\n    for(var i=0; i&lt;A.length; i++){\n      if(A[B[i]] &gt; A[B[i+1]]){\n        var temp = B[i];\n        B[i] = B[i+1];\n        B[i+1] = temp;\n        swapped = true;\n      }\n    }\n  }while(swapped);\n  return B;\n}\n</code></pre>\n'}, {'answer_id': 119587, 'author': 'Maciej Hehl', 'author_id': 19939, 'author_profile': 'https://Stackoverflow.com/users/19939', 'pm_score': 2, 'selected': False, 'text': '<p>Ok, here is my atempt in C++  </p>\n\n<pre><code>#include &lt;iostream&gt;\n#include &lt;algorithm&gt;\n\nstruct mycomparison\n{\n    bool operator() (int* lhs, int* rhs) {return (*lhs) &lt; (*rhs);}\n};\n\nint main(int argc, char* argv[])\n{\n    int myarray[] = {1, 3, 6, 2, 4, 9, 5, 12, 10};\n    const size_t size = sizeof(myarray) / sizeof(myarray[0]);\n    int *arrayofpointers[size];\n    for(int i = 0; i &lt; size; ++i)\n    {\n        arrayofpointers[i] = myarray + i;\n    }\n    std::sort(arrayofpointers, arrayofpointers + size, mycomparison());\n    for(int i = 0; i &lt; size; ++i)\n    {\n        *arrayofpointers[i] = i + 1;\n    }\n    for(int i = 0; i &lt; size; ++i)\n    {\n        std::cout &lt;&lt; myarray[i] &lt;&lt; " ";\n    }\n    std::cout &lt;&lt; std::endl;\n    return 0;\n}\n</code></pre>\n'}, {'answer_id': 122083, 'author': 'oz10', 'author_id': 14069, 'author_profile': 'https://Stackoverflow.com/users/14069', 'pm_score': 0, 'selected': False, 'text': '<p>Parallel sorting of vector using boost::lambda...</p>\n\n<pre><code>   std::vector&lt;int&gt; intVector;\n   std::vector&lt;int&gt; rank;\n\n   // set up values according to your example...\n   intVector.push_back( 1 );\n   intVector.push_back( 3 );\n   intVector.push_back( 4 );\n   intVector.push_back( 9 );\n   intVector.push_back( 6 );\n\n\n   for( int i = 0; i &lt; intVector.size(); ++i )\n   {\n      rank.push_back( i );\n   }\n\n   using namespace boost::lambda;\n   std::sort( \n              rank.begin(), rank.end(),\n              var( intVector )[ _1 ] &lt; var( intVector )[ _2 ] \n            );\n\n   //... and because you wanted to replace the values of the original with \n   //    their rank\n   intVector = rank;\n</code></pre>\n\n<p>Note: I used vectorS instead of arrays because it is clearer/easier, also, I used C-style indexing which starts counting from 0, not 1.</p>\n'}, {'answer_id': 33194962, 'author': 'aravinth', 'author_id': 3553385, 'author_profile': 'https://Stackoverflow.com/users/3553385', 'pm_score': 1, 'selected': False, 'text': '<p>create a new Array and use bubble sort to rank the elements</p>\n\n<pre><code>int arr[n];\nint rank[n];\n for(int i=0;i&lt;n;i++)\n    for(int j=0;j&lt;n;j++)\n       if(arr[i]&gt;arr[j])\n         rank[i]++;\n</code></pre>\n\n<p>The rank of each element will be rank[i]+1 to be in the order of 1,2,....n</p>\n'}, {'answer_id': 44255995, 'author': 'Phillip Kigenyi', 'author_id': 4991437, 'author_profile': 'https://Stackoverflow.com/users/4991437', 'pm_score': 0, 'selected': False, 'text': '<p>This is a solution in c language</p>\n\n<pre><code>#include &lt;stdio.h&gt;\n\nvoid swap(int *xp, int *yp) {\n    int temp = *xp;\n    *xp = *yp;\n    *yp = temp;\n}\n\n// A function to implement bubble sort\nvoid bubbleSort(int arr[], int n) {\n    int i, j;\n    for (i = 0; i &lt; n - 1; i++)\n\n        // Last i elements are already in place\n        for (j = 0; j &lt; n - i - 1; j++)\n            if (arr[j] &gt; arr[j + 1])\n                swap(&amp;arr[j], &amp;arr[j + 1]);\n}\n\n/* Function to print an array */\nvoid printArray(int arr[], int size) {\n    for (int i = 0; i &lt; size; i++)\n        printf("%d ", arr[i]);\n    printf("\\n");\n}\n\nint main() {\n    int arr[] = {64, 34, 25, 12, 22, 11, 98};\n    int arr_original[] = {64, 34, 25, 12, 22, 11, 98};\n    int rank[7];\n\n    int n = sizeof(arr) / sizeof(arr[0]);\n    bubbleSort(arr, n);\n\n    printf("Sorted array: \\n");\n    printArray(arr, n);\n\n    //PLACE RANK\n    //look for location of number in original array\n    //place the location in rank array\n    int counter = 1;\n    for (int k = 0; k &lt; n; k++){\n        for (int i = 0; i &lt; n; i++){\n            printf("Checking..%d\\n", i);\n            if (arr_original[i] == arr[k]){\n                rank[i] = counter;\n                counter++;\n                printf("Found..%d\\n", i);\n            }\n        }\n    }\n\n    printf("Original array: \\n");\n    printArray(arr_original, n);\n\n    printf("Rank array: \\n");\n    printArray(rank, n);\n    return 0;\n}\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/13473', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/522/']