Remove elements repeted

[lrcvs]

Hi:

1) Thank you very much everyone!

2) LOL, I've been working erroneously well all my life!

I modified the program a bit.
(I hope I did not have more errors)

Code: Select all

'lrcvs 01.10.17

'program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x

CLS
x = 30000000            'x = number of array elements
DIM s (x)AS INTEGER     'this is the main array
DIM t (x)AS INTEGER     'this is the auxiliary array

RANDOMIZE, 3
FOR n = 1 TO x
    s(n) = (INT(RND * x) + 1)     'here we write the values in the main array
    'print s(n);" ";              'show elements of auxiliary array
NEXT n

PRINT
PRINT "init array of "; x; " elements, some repeated"
PRINT

ordenar2 (s(),1,x)      'sort the elements

'******************************************************************************
'remove elements repeted

f = 1      'f = counter for the main array
c = 1      'c = counter for the auxiliary array

t(c) = s(c)

WHILE f < x
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array

'for n = 1 to c-1
'    print t(n);" ";
'next n


PRINT
PRINT "there are ";c;" unique elements"
PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB

[caseih]

I modified the program a bit.
(I hope I did not have more errors)

Did you compile your program with -exx to detect out-of-bounds array access? If not, why not?

[lrcvs]

Hi

I have modidied the entry of values in the array to "0"

Code: Select all

'lrcvs 01.10.17

'Program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x

CLS
x = 20 '<<< elements    'x = number of array elements
DIM s (x)AS INTEGER     'This is the main array
DIM t (x)AS INTEGER     'This is the auxiliary array

RANDOMIZE, 3
FOR n = 0 TO x
    s(n) = (INT(RND * x) + 1)     'Here we write the values in the main array
    print s(n);" ";              'show elements of auxiliary array
NEXT n

print
PRINT "Init array of "; x; " elements, some repeated"
print

ordenar2 (s(),0,x)      'sort the elements

'******************************************************************************
'Remove elements repeted

f = 0       'f = counter for the main array
c = 0      'c = counter for the auxiliary array
t(c) = s(c)
WHILE f < x    
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array
for n = 0 to c
    print t(n);" "; 
next n


PRINT
PRINT "There are ";c+1;" unique elements"
PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB

[lrcvs]

Hi

My apologies, now is perfect.

Code: Select all

'lrcvs 01.10.17

'Program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x,z

CLS
x = 15 '<<< elements    'x = number of array elements
DIM s (x)AS INTEGER     'This is the main array
DIM t (x)AS INTEGER     'This is the auxiliary array

RANDOMIZE, 3

FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)     'Here we write the values in the main array
    print s(n);" ";              'show elements of auxiliary array
NEXT n
print
PRINT "Init array of "; x; " elements, some repeated"
print

ordenar2 (s(),0,x-1)      'sort the elements

'******************************************************************************
'Remove elements repeted

f = 0       'f = counter for the main array
c = 0      'c = counter for the auxiliary array
t(c) = s(c)
WHILE f < x-1
    
'Here we compare an element of the main array with the following of the main array 
'comparing them, if they are equal, the counter (f) of the main array advances one step, and so on
'comparing them, if they are different, we add the element of the main array to the auxiliary array and increase "c" and advance the main counter (f)
'the process is repeated until the end of the main carray
    
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array
for n = 0 to c
    print t(n);" "; 
next n


PRINT
PRINT "There are ";c+1;" unique elements"
PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB

Regards

[fxm]

'Dim s(n)' defines an array of n+1 elements (from index '0' to index 'n').
So to define an array of n elements:
Dim s(n-1)
or
Dim s(0 To n-1)
which is more explicit:

Code: Select all

x = 15 '<<< elements    'x = number of array elements
DIM s (0 TO x-1)AS INTEGER     'This is the main array
DIM t (0 TO x-1)AS INTEGER     'This is the auxiliary array

[lrcvs]

Hi, fxm:

Thank you very much for your observation.

I modify the program with your indications.

Code: Select all

'lrcvs 01.10.17

'Program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x,z

CLS

x = 15 '<<< elements    'x = number of array elements
DIM s (0 TO x-1)AS INTEGER     'This is the main array
DIM t (0 TO x-1)AS INTEGER     'This is the auxiliary array

RANDOMIZE, 3

FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)     'Here we write the values in the main array
    print s(n);" ";              'show elements of auxiliary array
NEXT n
print
PRINT "Init array of "; x; " elements, some repeated"
print

ordenar2 (s(),0,x-1)      'sort the elements

'******************************************************************************
'Remove elements repeted

f = 0       'f = counter for the main array
c = 0      'c = counter for the auxiliary array
t(c) = s(c)
WHILE f < x-1
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array
for n = 0 to c
    print t(n);" "; 
next n


PRINT
PRINT "There are ";c+1;" unique elements"
PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB

Regards

[lrcvs]

Hi:

Part # 2:

With the previous program, we obtain the unique elements of a list / array (or remove the repeated ones.)

Now, we show the original list / array, without the repeated elements and in the initial order.

Code: Select all

'lrcvs 01.10.17

'program to eliminate repeated elements in an array.

'1) we sort the initial array, using quicksort.

'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER c,f,n,x,v,w

CLS

x = 20 '<<< elements    'x = number of array elements
DIM s (0 TO x-1)AS INTEGER     'this is the main array
DIM t (0 TO x-1)AS INTEGER     'this is the auxil_1 array
DIM r (0 TO x-1)AS INTEGER     'this is the auxil_2 array
DIM u (0 TO x-1)AS INTEGER     'this is the auxil_3 array

RANDOMIZE, 3

FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)     'here we write the values in the main array
    u(n) = s(n)
    PRINT s(n);" ";              'show elements of auxiliary array
NEXT n


PRINT
PRINT "init array of "; x; " elements, some repeated"
PRINT

ordenar2 (s(),0,x-1)      'sort the elements + auxil_2 array


'******************************************************************************
'remove elements repeted

f = 0       'f = counter for the main array
c = 0      'c = counter for the auxiliary array
t(c) = s(c)
r(c) = s(c)
WHILE f < x-1
    IF s(f + 1) = t(c)  THEN
        f = f + 1
    ELSE
        c = c + 1
        t(c) = s(f + 1)
    END IF
WEND

'******************************************************************************
'show elements of auxiliary array
FOR n = 0 TO c
    PRINT t(n);" ";
NEXT n
PRINT

'clasification
FOR v = 0 TO c
    FOR w = 0 TO x-1
        IF u(w) = t(v) THEN r(w) = 1:EXIT FOR
    NEXT w
NEXT v

PRINT "there are ";c+1;" unique elements"
PRINT

'show the list / original array, without the repeated elements
FOR n = 0 TO x-1
    IF r(n) = 1 THEN PRINT u(n);" ";
NEXT n
PRINT
PRINT "list / original array, without the repeated elements"

PRINT
PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y
    i = inicio
    j = final
    y = s(INT(i + j) / 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
        
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB

**********************************************************************************
5 6 3 1 19 11 2 18 14 6 4 2 12 13 19 6 6 13 3 15
init array of 20 elements, some repeated

1 2 3 4 5 6 11 12 13 14 15 18 19
there are 13 unique elements

5 6 3 1 19 11 2 18 14 4 12 13 15
list / original array, without the repeated elements
***********************************************************************************

Regards

[counting_pine]

Dim s(0 To n-1)
which is more explicit

Yes, its meaning is much more obvious.

[lrcvs]

Code: Select all

'lrcvs 2019.jul.21
'program to eliminate repeated elements in an array.
'1) we sort the initial array, using quicksort.
'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".
'3)It is a small improvement of the previous code, year 2017.

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER n,x

CLS
x = 110 '<<< elements    'x = number of array elements
DIM s (0 TO x-1)AS INTEGER     'this is the main array
RANDOMIZE, 3

'show elements..................................................................
PRINT "the original array"
FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)
    PRINT s(n);" ";
NEXT n

'qsort..........................................................................
ordenar2 (s(),0,x-1)

'show elements sort.............................................................
PRINT:PRINT:PRINT "show the original array sort"
FOR n = 0 TO x-1
    PRINT s(n);" ";
NEXT n

'show the original array, without the repeated elements.........................
PRINT:PRINT:PRINT "show the original array, without the repeated elements"
FOR n = 0 TO x-1
    IF s(n) <> s(n+1) THEN PRINT s(n);" ";
NEXT n

PRINT:PRINT:PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y,n
    i = inicio
    j = final
    y = s((i + j) \ 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
    END SUB

Regards

[fxm]

The last array element must not be tested with the next, otherwise error: "out of bounds array access".

Perhaps:

Code: Select all

'show the original array, without the repeated elements.........................
PRINT:PRINT:PRINT "show the original array, without the repeated elements"
FOR n = 0 TO x-2
    IF s(n) <> s(n+1) THEN PRINT s(n);" ";
NEXT n
PRINT s(x-1);

[lrcvs]

Hi, fxm:

As always, thank you for your observations.

Apologies

[ShawnLG]

There is a much faster way to remove repeated elements from an array. You can use a hash table to remember what elements are accounted for. Hash tables run in constant time O(1) . Much faster than using quicksort.

Code: Select all

'Hashtable using quadratic probing by ShawnLG
const hNULL = -1
type hashtable
    declare constructor(byval s as integer)'Initialize hash table size
    declare destructor()
    declare sub push(key as integer)'Push key onto table
    declare function check(key as integer) as integer' Check if key is on the table
    private:
    dim as integer ptr ht
    dim as integer size
end type

constructor hashtable(byval s as integer)
    this.ht = new integer[s+1]
    for i as integer = 0 to s
        this.ht[i] = hNULL'Null the table
    next i
    this.size = s
end constructor

destructor hashtable()
    delete[] this.ht
end destructor
 
sub hashtable.push(key as integer)
    dim as integer index = key mod this.size 'hash function
    do
        if this.ht[index] = hNULL then 'check if current slot is free
            this.ht[index] = key 'put the key value in the available slot
            exit do' where done!
        else 'jump to next index
            index = (index shr 1)mod this.size 'perform quadratic hop to next slot
        end if
    loop
end sub

function hashtable.check(key as integer) as integer
    dim as integer index = key mod this.size ' hash function
    do
        if this.ht[index] = hNULL then 'check if key does not exist
            return -1
        elseif this.ht[index] = key then 'check if we found the key
            return key
        else ' jump to next index
            index = (index shr 1) mod this.size 'perform quadratic hop to next slot
        end if
    loop
end function




'lrcvs 2019.jul.21
'program to eliminate repeated elements in an array.
'1) we sort the initial array, using quicksort.
'2) we remove the repeated elements, skipping the ones that are the same
'and reducing the time of "cleaning the repeated elements".
'3)It is a small improvement of the previous code, year 2017.

DECLARE SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)

DIM AS INTEGER n,x

CLS
x = 110 '<<< elements    'x = number of array elements
dim as hashtable h = x * 10'need plenty of room on the hash table 
DIM s (0 TO x-1)AS INTEGER     'this is the main array
RANDOMIZE, 3

'show elements..................................................................
PRINT "the original array"
FOR n = 0 TO x-1
    s(n) = (INT(RND * x) + 1)
    PRINT s(n);" ";
NEXT n

'qsort...........................................................................
'ordenar2 (s(),0,x-1)

'show elements sort.............................................................
'PRINT:PRINT:PRINT "show the original array sort"
'FOR n = 0 TO x-1
'    PRINT s(n);" ";
'NEXT n

'show the original array, without the repeated elements.........................
PRINT:PRINT:PRINT "show the original array, without the repeated elements"
FOR n = 0 TO x-1
    'IF s(n) <> s(n+1) THEN PRINT s(n);" ";
    if h.check(s(n)) <> s(n) then
        h.push(s(n))' keep tabs on what we have.
        print s(n);" ";
    end if
NEXT n

PRINT:PRINT:PRINT "end"
SLEEP
END

'******************************************************************************
SUB ordenar2 (s()AS INTEGER,inicio AS INTEGER,final AS INTEGER)
    'quick sort
    DIM AS INTEGER i,j,y,n
    i = inicio
    j = final
    y = s((i + j) \ 2)
    WHILE i < j
        WHILE s(i) < y
            i = i + 1
        WEND
        WHILE s(j) > y
            j = j - 1
        WEND
        IF i <= j THEN
            SWAP s(i), s(j)
            i = i + 1
            j = j - 1
        END IF
    WEND
    IF j > inicio THEN ordenar2(s(),inicio,j)
    IF i < final THEN ordenar2(s(),i,final)
END SUB