.

[lindsayy]

.

[Handy Andy]

Hello lindsayy,

What have you done so far?

Can not help you if you do not post any code that does not work.

Are you required to use an array or can you use a vector or something else? It helps to know.

Andy

[markyrocks]

I've been working on a variety of sorting functions. The last one is getting a little out of hand I'm not done with it but i'm thinking that it might actually turn out fairly decent. I'm trying to work out ways to try to predict where an element should be and search around that area and do various things to get the thing in order. Anyways take a look, maybe it will give you some ideas.

https://pastebin.com/Zs9tTDyA

[lindsayy]

.https://onlinegdb.com/M4kgD3h81

#include <iostream>
using namespace std;

int main()
{
    int count = 1;
    int array[]={1,2,4,3,5,6,8,7,9,11,10,12,13};
    
    int size;
    size = sizeof array/sizeof array[0];
   
   for (int i = 0; i < size-1; i++)         // for loop to find how many sorted runs
   {
        if (array[i] > array[i+1])
        count++;
    }
    cout<<"sorted runs is "<<count<<endl;
    
    int pst = 0;                             //initialization of position for the start of every runs
    
    int* pos= new int[size];             //creating new array to store the value of new sorted runs position

    for (int j = 0; j < size; j++)            //loop to find position for the start of sorted runs and store it in pos array
    {
        if (array[j] > array[j+1])
        pos[pst] = j+1;
        pst++;
        
    }
    
    cout<<"sorted runs start at index "<< pos[0]<<endl;     //printing the first sorted runs,which is index 0
    for (int k = 0; k < size; k++)                        //loop to print the rest sorted runs position
    {
        
        if (array[k] > array[k+1])
        {
        cout<<"sorted runs start at index "<< pos[k]<<endl;
        }
    }
    
    


    return 0;
}

[lastchance]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


struct Run{ int first, last, pos; };


template<typename T> ostream & operator << ( ostream &out, const vector<T> &V )
{
   for ( T e : V ) out << e << " ";
   return out;
}


int main()
{
   vector<int> A = {1,2,4,3,5,6,8,7,9,11,10,12,13};
   cout << "Original array:\n" << A << "\n\n";

   // Find sorted runs
   vector<Run> runs;
   Run R{ 0, 0, 0 };
   for ( int i = 1; i < A.size(); i++ )
   {
      if ( A[i] < A[i-1] )          // wind up current run and start a new one
      {
         R.last = i - 1;
         runs.push_back( R );
         R = Run{ i, i, i };
      }
   }
   R.last = A.size() - 1;
   runs.push_back( R );
   
   cout << "Runs are (first:last):\n";
   for ( auto r : runs ) cout << r.first << " : " << r.last << '\n';


   // Merge sorted runs
   vector<int> B;
   while ( !runs.empty() )
   {
      auto it = min_element( runs.begin(), runs.end(), [&A]( Run a, Run b ){ return A[a.pos] < A[b.pos]; } );
      B.push_back( A[it->pos] );
      it->pos++;
      if ( it->pos > it->last ) runs.erase( it );
   }
   cout << "\nSorted array:\n" << B << "\n\n";
}

Original array:
1 2 4 3 5 6 8 7 9 11 10 12 13 

Runs are (first:last):
0 : 2
3 : 6
7 : 9
10 : 12

Sorted array:
1 2 3 4 5 6 7 8 9 10 11 12 13 

[seeplus]

@markrocks. It's not recommended to start a global name name with _ It's allowed, but reserved for the implementation writers. At some point this will bite..... See http://cplusplus.com/forum/general/95813/

[lindsayy]

I tried to solve the mergesort..but i can only do the sorting if the sorted data is 2

https://onlinegdb.com/3AvXarY50

#include <iostream>
using namespace std;


void mergesort(int* array ,int count)
{
      for(int n=0 ;array[n] > array[n+1];n++ )
        {   
            while(count>=0)
            {
                for(int o=0 ;array[o] > array[o+1];o++)
                {
                    if(array[n]>array[o])
                    {
                        for (int p=array[o]-1; p>=array[n]+1; p--) 
                        {
                        array[p] = array[p-1];
                        }
                        array[n] = array[o];
                    }
                }
            count--;
                
            }
        }
}
int main()
{
    int count = 1;
    int array[]={1,2,4,3,5,6,8};
    
    int size; 
    size = sizeof array/sizeof array[0];
   
   for (int i = 0; i < size-1; i++)         // for loop to find how many sorted runs
   {
        if (array[i] > array[i+1])
        count++;
    }
    cout<<"sorted runs is "<<count<<endl;
    
    int pst = 0;                             //initialization of position for the start of every runs
    
    int* pos= new int[size];             //creating new array to store the value of new sorted runs position

    for (int j = 0; j < size; j++)            //loop to find position for the start of sorted runs and store it in pos array
    {
        if (array[j] > array[j+1])
        pos[pst] = j+1;
        pst++;
        
    }
    
    cout<<"sorted runs start at index "<< pos[0]<<endl;     //printing the first sorted runs,which is index 0
    for (int k = 0; k < size-1; k++)                        //loop to print the rest sorted runs position
    {
        
        if (array[k] > array[k+1])
        {
        cout<<"sorted runs start at index "<< pos[k]<<endl;
        }
    }
    
    mergesort(array,count);
    
    cout<<"sorted array"<<endl;
    
       for (int q=0; q<size; q++) 
       {
        cout <<array[q] << " ";
        }
    cout << endl;
    
    
    


    return 0;
}

[lindsayy]

thank you @lastchance but i dont know how to use vector,since I didn't learn that yet

[lindsayy]

thank you @ markyrocks

[markyrocks]

@seeplus I'm just playing around. I just start to run out of names when I'm doing random stuff like this. I wouldn't do that in anything serious I was working on.

Seeing this thread had got me thinking about doing an insertion sort and a merge sort....and it is a pita for sure. I'm having issues of my own lol. But I'm trying to do everything with pointers which is kinda a handicap especially when you start getting into ppp's which is what's basically required for insertion and merge.

I'm also kinda irritated bc I had previously done what was supposed to be a heap sort but I totally missed the whole point of it. I'm going to have to revisit that. I was shuffling strictly linearly when I needed to be 3d....

[jonnin]

c++ has a sort but the algorithms are kinda cool to play with.
if it helps the useful ones ... intro, shell, merge, counting, bucket come to mind.
intro: fastest/best general purpose, unless its grown another leg and a new name. parallel friendly
shell: if you cannot use recursion, or do not want to (back end of intro/quick/etc type). It may also be one of the best big-O studies available, you can spend weeks on it, for 1/3 a page of code.
merge: parallel friendly
counting: O(1) on limited types of data
bucket O(1) if 'sort of sorted' is good enough(there are times when full sorting isnt needed), or can be chained down to a counting sort making it still O(1) but requires multiple passes to get there. Chained is parallel friendly.

*** all sorting is parallel friendly if you chop up the data and merge (not merge sort, just a merge) back together. When I say that above, I mean the algorithm is friendly to it without these extra external handlers.

[lastchance]

lindsayy wrote:

thank you @lastchance but i dont know how to use vector,since I didn't learn that yet

Well the version with vectors is much easier (and, I think, more efficient):
http://www.cplusplus.com/forum/beginner/278448/#msg1202071

However, if you are hell bent on not using vectors, then:

#include <iostream>
using namespace std;

struct Run{ int first, last, pos; };

int main()
{
   int A[] = {1,2,4,3,5,6,8,7,9,11,10,12,13};
   int N = sizeof A / sizeof A[0];
   cout << "Unsorted array: ";
   for ( int i = 0; i < N; i++ ) cout << A[i] << " ";
   cout << "\n\n";
   

   // Count sorted runs
   int nruns = 1;
   for ( int i = 1; i < N; i++ ) if ( A[i] < A[i-1] ) nruns++;
   
   // Find sorted runs
   Run *runs = new Run[nruns];
   int nr = 0;
   runs[nr] = Run{ 0, 0, 0 };
   for ( int i = 1; i < N; i++ )
   {
      if ( A[i] < A[i-1] )          // wind up current run and start a new one
      {
         runs[nr].last = i - 1;
         runs[++nr] = Run{ i, i, i };
      }
   }
   runs[nruns-1].last = N - 1;
      
   cout << "Runs are (first:last):\n";
   for ( int j = 0; j < nruns; j++ ) cout << runs[j].first << " : " << runs[j].last << '\n';


   // Merge sorted runs
   int *B = new int[N];
   for ( int i = 0; i < N; i++ )
   {
      nr = -1;
      for ( int j = 0; j < nruns; j++ )
      {
         if ( runs[j].pos <= runs[j].last && ( nr == -1 || A[runs[j].pos] < A[runs[nr].pos] ) ) nr = j;
      }
      B[i] = A[runs[nr].pos];
      runs[nr].pos++;
   }
   cout << "\nSorted array: ";
   for ( int i = 0; i < N; i++ ) cout << B[i] << " ";
   
   delete [] runs;
   delete [] B;
}

nsorted array: 1 2 4 3 5 6 8 7 9 11 10 12 13 

Runs are (first:last):
0 : 2
3 : 6
7 : 9
10 : 12

Sorted array: 1 2 3 4 5 6 7 8 9 10 11 12 13

[lindsayy]

Thankyou @lastchance..may i know how did u get the runs[j].first value in line34?..because I only see how you find runs[j].last which is in loop line 25..but not runs[j].first

[lastchance]

Line 22 (for the first run) and line 28 for the later ones set runs[nr].first on initialisation, as 0 and i respectively. The .first member never needs superseding, whereas the .last member must be updated at the end of that run (lines 27 or 31).

(The line numbers are as in my post above.)

[lindsayy]

i see..@lastchance,do you mind explaining some of my question?

1)what does pos in struct Run means? and also nr in line 21
2)for line 22,are you assigning 0 to first,last and pos? if not..what is it?
3)and my last question is how does line 28 works?

Thank you so much!! @lastchance for giving me ur time

[lastchance]

1)what does pos in struct Run means? and also nr in line 21
2)for line 22,are you assigning 0 to first,last and pos? if not..what is it?
3)and my last question is how does line 28 works?

In struct run:
.first is the first index in A of this run , .last is the last index in A of this run.
.pos is the position of the current index in A when it comes to merging runs; thus .pos starts as the same as .first, and increases by one each time until it exceeds .last. (At this point that run is used up and not used for any more merging. This is actually the first part of the test for minimum available index of A in line 44.)


nr is just being using as an index of the run; essentially, n (number) of r (run).


runs[nr] = Run{ 0, 0, 0 };
assigns values 0, 0, 0 to .first, .last and .pos members respectively of the item runs[nr]. Similarly, for the other assignment on line 28. The .first and .pos values are the correct starting points. .last will need updating later when the length of the run is known.


runs[++nr] = Run{ i, i, i };
is just abbreviating two lines to one:

   nr++;      // increments the run number
   runs[nr] = Run{ i, i, i };    // assigns i, i, i to the members of this next run 

If you write the ++ before nr, then it means that nr will be incremented BEFORE it become the relevant index of runs[]

[lindsayy]

i see,then when value of i in for loops in line 23 is 1..

for ( int i = 1; i < N; i++ )
   {
      if ( A[i] < A[i-1] )          // wind up current run and start a new one
      {
         runs[nr].last = i - 1;
         runs[++nr] = Run{ i, i, i };
      }
   }

then what is the value of I in runs[++nr] = Run{ i, i, i }; ?

[lindsayy]

btw your code uses ectra array right to merge the element?....is it possible to only use array A to merge the element?

[lastchance]

@lindsay,
The value of i between lines 23 and 30 loops between 1 and N-1 (the last index of A).

In Run{i,i,i} the value of i is just that loop counter (which coincides with an index in A).

An extra array is used to merge the data, because the method works by merging, not lots of swapping. If you want values back in A at the end then you could simply copy them back.