Remove duplicates from a sorted array

Question

I have this code that I have been working on for a couple of hours now trying to figure out how to implement removing duplicates within the sorted array during the insertion sort. I'm trying to do this without having to re-write the whole program but as I progress it seems that I may just have to start from scratch but before I do I was hoping to see if it was possible to do this with the code below.

The question at hand is, How can I go about removing duplicates from the sorted array before putting it back into a file?

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using std::cout;
using std::endl;
using namespace std;

//sort into an array using insertion sort
//getis info from file "numbers.txt"
//and prints the sorted numbers into "sorted_numbers.txt"
void insertSort(int a[], int length)
{
   int i, j, value;
   int old = 0;
   bool first = true;

   for(i = 1; i < length; i++)
   {
       if(first || old != a[i])
       {
           old = a[i];
           first = false;

           value = a[i];
           for (j = i - 1; j >= 0 && a[j] > value; j--)
           {
               a[j + 1] = a[j];
           }
       }
       a[j + 1] = value;
   }
}

//prints out the array in 'Run I/O'
void printarray(int arg[], int length)
{
    for(int n =0; n<length; ++n)
      cout << arg[n] << ' ';
    cout << '\n';
}

int main ()
{
    std::ifstream in;
    std::ofstream out;

    int N = 10;
    int n = 0;
    int k;
    int* a = new int(N);

    //opens the file "numbers.txt" if it exit
    //gets the chars from file and sorts them 
    //into array "a[n]" 
    in.open("numbers.txt");
    if(!in.is_open())
    {
        std::cout << "File could not be opened FILE NOT FOUND." << std::endl;

        //creates the a new file to be read from if numbers.txt does
        //not already exist and put numbers inside of it
        //to be sorted with the InsertSort function
        out.open("numbers.txt");
        out << "1" << endl;
        out << "3" << endl;
        out << "7" << endl;
        out << "4" << endl;
        out << "2" << endl;
        out << "7" << endl;
        out << "6" << endl;
        out << "9" << endl;
        out << "5" << endl;
        out << "2" << endl;

        out.close();

        //opens the new numbers.txt file and puts the 
        //numbers into an array to be sorted
        in.open("numbers.txt");

        //runs through the items in the file and
        //puts them into an array
        int x;
        while(in >> x) 
        {
            a[n] = x;
            n++; 
        }

        printarray(a,10);
        std::cout << "Read " << n << " integers from the file." << std::endl;

        //sorts the array from when it was read 
        //to the new insertion sort array
        insertSort(a,n);

        std::cout << "Integers are sorted" << std::endl;

        //writes/creates the new sorted array to a new file
        //called "sorted_numbers.txt"
        out.open("sorted_numbers.txt");
        for(k = 0;k < n;k++)
            out << a[k] << std::endl;
            printarray(a,10);
        out.close();

        delete[] a;

        in.close();
    }
    else
    {
        int x;
        while(in >> x) 
        {
            a[n] = x;
            n++;
         }

      printarray(a,10);
      std::cout << "Read " << n << " integers from the file." << std::endl;

      insertSort(a,n);

      std::cout << "Integers are sorted" << std::endl;

      //writes/creates the new sorted array to a new file
      //called "sorted_numbers.txt"
      out.open("sorted_numbers.txt");
      for(k = 0;k < n;k++)
          out << a[k] << std::endl;   
          std::cout << n << " integers stored to the file." << std::endl;
          printarray(a,10);
      out.close();

      delete[] a;
   }
   return 0;
}

Do you have to use insertion sort? If you used e.g. a quicksort, you would have the advantage that during every iteration, you already partition the input into elements before the pivot and after. If you modify that to discard any elements equal to the pivot, you would solve both tasks of sorting and making unique in one. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Sep 11, 2014 at 5:37

rcgldr · Accepted Answer · 2014-09-11 10:14:38Z

Insertion sort operates left to right and rotates a sub-array to the right (to place the smallest value on the left of the sub-array), while deletion of a duplicate shifts a sub-array to the left. As an alternative, I created and modified a "delete" sort (a reversed insertion sort) that operates right to left and rotates a sub-array to the left (to place the largest value on the right of the sub-array), and left shifts of a sub-array to delete duplicates.

void deletesort(int a[], int &length)
{
    int i, j, value;
    if(length < 2)
        return;
    for(i = length-2; i >= 0; i--){
        value = a[i];
        for (j = i+1; j < length; j++){
            if(value > a[j]){
                a[j-1] = a[j];
                continue;
            }
            if(value == a[j]){
                for( ; j < length; j++)
                    a[j-1] = a[j];
                length--;
            }
            break;
        }
        a[j-1] = value;
    }
}

Here's a delete sort that doesn't remove duplicates:

void deletesort(int a[], int length)
{
    int i, j, value;
    if(length < 2)
        return;
    for(i = length-2; i >= 0; i--){
        value = a[i];
        for (j = i+1; j < length && value > a[j]; j++)
            a[j-1] = a[j];
        a[j-1] = value;
    }
}

user657267 · Accepted Answer · 2014-09-11 00:55:23Z

0

Use the algorithm library and a std::vector

#include <algorithm>
#include <vector>
#include <fstream>

int main()
{
  std::vector<int> v;
  {
    std::ifstream is("numbers.txt");
    for (int i; is >> i; )
      v.push_back(i);
  }

  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());

  std::ofstream of("sorted_numbers.txt");
  for (auto i : v)
    of << i << '\n';

  // Or for non-c++11
  // for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); ++i)
  //   of << *i << '\n';
}

Or even a std::set for simplicity (the vector version may be faster, but probably won't matter much for your use case).

#include <algorithm>
#include <set>
#include <fstream>

int main()
{
  std::set<int> s;
  {
    std::ifstream is("numbers.txt");
    for (int i; is >> i; )
      s.insert(i);
  }

  std::ofstream of("sorted_numbers.txt");
  for (auto i : s)
    of << i << '\n';

  // Or for non-c++11
  // for (std::set<int>::const_iterator i = s.begin(); i != s.end(); ++i)
  //   of << *i << '\n';
}

edited Sep 11, 2014 at 0:55

answered Sep 11, 2014 at 0:44

user657267

21.1k5 gold badges65 silver badges81 bronze badges

6 Comments

Jaybro90 Over a year ago

While testing this code I get this error. test.cpp:19:13: error: 'i' does not name a type for (auto i : v)

user657267 Over a year ago

@Jaybro90 What compiler are you using? Does it support c++11?

Jaybro90 Over a year ago

I am using jGRASP, which I should probably download a different compiler

user657267 Over a year ago

I'll add some lines that should work if you have no c++11 support.

Jaybro90 Over a year ago

Thank you, the first solution worked, I also added it so that if the file 'numbers.txt' doesn't already exist it will create it then execute the sort and remove duplicates.

|

Collectives™ on Stack Overflow

Remove duplicates from a sorted array

2 Answers 2

Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related