Sorting elements in array without repetition or vectors

[cbsestudent]

Hello everybody. This is my first post here on the c++ forums :D I made a code for sorting the elements in an array in ascending order without repetition without using vectors. I'm not allowed to use vectors yet because it is out of my syllabus, so I made a very crude code which can remove up to (n-1) duplicate elements and sort it in ascending order. Is there any way of improving it ?

#include<iostream>
using namespace std;
int main( )
{
            int a[100], n, i, j, temp,k;
            cout<<"Enter the no. of elements : ";
            cin>> n;
            cout<<"Enter the array elements"<<endl;
            for(i=0; i< n; i++)
             {
                    cout<<"\t";
                    cin>>a[i];
             }
            //Bubble sorting
            for( i=0; i< n; i++)
            {
                   for(j=i; j< n-1; j++)
                    {
                           if(a[i]> a[j+1] )
                            {
                                 temp= a[i];
                                 a[i]= a[j+1];
                                 a[j+1]= temp;
                            }
                    }
           }
          // Removal of duplicate elements
          for (int k=0;k<n;k++)
          {
             for (i=0;i<n;i++)
             {
                    if (a[i]==a[i+1] || a[i]==a[i-1])
                    {
                         for (j=i;j<n;j++)
                                a[j]=a[j+1];
                         n--;
                    }
             }
          }
          cout<<"The sorted elements are : ";
          for (i=0;i<n;i++)
          {
                  cout<<a[i]<<" ";
          }
}

[TarikNeaj]

Looks good to me :)

[cbsestudent]

I realize that it works well, but it is highly inefficient. It needs n passes to ensure there are no n-plicates. Can it be made more efficient ?

[TarikNeaj]

I dont really think its inefficient. The only think you can improve on is removing the second part in the if statement

if (a[i]==a[i+1] || a[i]==a[i-1])

This is enough

if (a[i] == a[i + 1])

[D80DSL3A]

I've devised a single pass method for eliminating duplicates in a sorted array. It works under light testing so far.
See if you can find a flaw:

#include<iostream>
using std::cout;

// returns the new shorter array length
int removeDups( int a[], int sz )
{
    int currVal = a[0];// value to watch for duplicates of
    int idxRead=1, idxWrite=1;// maintain separate index values to read and write positions

    while( idxRead < sz )
    {
        if( a[idxRead] != currVal )
        {
            currVal = a[idxRead];// update current value
            a[idxWrite] = currVal;// copy new value to current write position
            ++idxWrite;// advance write pointer
        }
        ++idxRead;
    }
    return idxWrite;
}

int main ()
{
    int nums[] = {1,1,2,3,3,3,4,5,6,6,7,8,8,8,9};// 15 elements
    int SZ = sizeof( nums )/ sizeof( nums[0] );
    int newSize = removeDups( nums, SZ );// new shorter length

    cout << "newSize = " << newSize << '\n';// sb 9
    for(int i=0; i<newSize; ++i)
        cout << nums[i] << ' ';

    cout << '\n';
    return 0;
}

Removal of the duplicates before sorting would improve the sorting efficiency though. Still O(n²) but with lower n.

[cbsestudent]

@TarikNeaj
Yes, you're right :D I originally used that code to eliminate triplicated code, but now that I've introduced the k loop, I could remove it.
@fun2code
Yes, it works for all scenarios. I've tested it. Thanks :D
Thank you all for your helpful replies.

[cbsestudent]

@fun2code
BTW, Why do you do this

int SZ = sizeof( nums )/ sizeof( nums[0] );

instead of just

int SZ= sizeof( nums );

[AbstractionAnon]

int SZ= sizeof( nums );

That returns the number of bytes in the array. We want to know how many elements (ints) are in the array, hence the division by sizeof(nums[0]).

We could also have divided by sizeof(int) to produce the same result, but that would be problematic if we later changed the type of the array (perhaps to long).