2
\$\begingroup\$

Problem:

Write an algorithm, to find the union and intersection sorted in ascending order, between the elements of two arrays

Input Format

The first line contains an integer, n1 , denoting the size of the first array.

The second line contains n1 space-separated integers representing elements of the first array.

The third line contains an integer, n2 , denoting the size of the second array.

The fourth line contains n2 space-separated integers representing elements of the second array.

Constraints

Apart from Array, no other data structure can be used Output elements should be sorted in ascending order Array should be sorted using Bubble Sort

Output Format

First line, union of space-separated elements of both array elements, sorted in ascending order

Second line, intersection of space-separated elements of both arrays elements, sorted in ascending order


Solution:

"""
   1) Sort two arrays
   2) Find union and intersecton of two sorted arrays
"""
def swap(array, indexI, indexJ):
    temp = array[indexI]
    array[indexI] = array[indexJ]
    array[indexJ] = temp

def bubbleSort(array):
    n = len(array)
    for indexI in range(n):
        exchanges = 0
        for indexJ in range(n-1, indexI, -1):
            if array[indexJ] < array[indexJ-1]:
                swap(array, indexJ, indexJ-1)
                exchanges += 1
        if exchanges == 0:
            break
def intersection(arrayOne, arrayTwo):
    arrayOneIndex = 0
    arrayTwoIndex =0
    sizeOfArrayOne = len(arrayOne)
    sizeOfArrayTwo = len(arrayTwo)
    array = []
    while arrayOneIndex < sizeOfArrayOne and arrayTwoIndex < sizeOfArrayTwo:
        if arrayOne[arrayOneIndex] < arrayTwo[arrayTwoIndex]:
            arrayOneIndex += 1
        elif arrayOne[arrayOneIndex] > arrayTwo[arrayTwoIndex]:
            arrayTwoIndex += 1
        else:
            array.append(arrayOne[arrayOneIndex])
            arrayOneIndex += 1
            arrayTwoIndex += 1
    return array

def union(arrayOne, arrayTwo):
    arrayOneIndex = 0
    arrayTwoIndex =0
    sizeOfArrayOne = len(arrayOne)
    sizeOfArrayTwo = len(arrayTwo)
    array = []
    while arrayOneIndex < sizeOfArrayOne and arrayTwoIndex < sizeOfArrayTwo:
        if arrayOne[arrayOneIndex] < arrayTwo[arrayTwoIndex]:
            array.append(arrayOne[arrayOneIndex])
            arrayOneIndex += 1
        elif arrayOne[arrayOneIndex] > arrayTwo[arrayTwoIndex]:
            array.append(arrayTwo[arrayTwoIndex])
            arrayTwoIndex += 1
        else:
            array.append(arrayOne[arrayOneIndex])
            arrayOneIndex += 1
            arrayTwoIndex += 1
    if arrayOneIndex == sizeOfArrayOne:
        while arrayTwoIndex < sizeOfArrayTwo:
            array.append(arrayTwo[arrayTwoIndex])
            arrayTwoIndex += 1
    else:
        while arrayOneIndex < sizeOfArrayOne:
            array.append(arrayOne[arrayOneIndex])
            arrayOneIndex += 1
    return array

if __name__ == '__main__':
    sizeOne = int(input())
    try:
        arrayOne = [int(x) for x in input().split()]
    except:
        print('Invalid input')
        sys.exit()
    sizeTwo = int(input())
    try:
        arrayTwo = [int(x) for x in input().split()]
    except:
        print('Invalid syntax')
        sys.exit()
    bubbleSort(arrayOne)
    bubbleSort(arrayTwo)
    intersectionArray = intersection(arrayOne, arrayTwo)
    unionArray = union(arrayOne, arrayTwo)
    print(*unionArray, sep=" ")
    print(*intersectionArray, sep=" ")

Correctness

Input 

3
4 5 7
5
6 9 5 7 1

Output

1 4 5 6 7 9
5 7

Input

6
1 1 8 9 0 5
4
0 7 3 4

Output

0 1 3 4 5 7 8 9
0

Question:

0) How to avoid such syntax? while arrayOneIndex < sizeOfArrayOne and arrayTwoIndex < sizeOfArrayTwo

1) Does the code require better error handling?

2) Can this code get more pythonic?

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Advice 1

PEP 8 has some (minor) complains: the names of functions and their arguments should be funky_functions instead of funkyFunctions, and funky_argument instead of funkyArgument.

Advice 2

In Python, you can say

def funky1():
    for i in range(10):
        yield i

def funky2():
    arr = []
    for i in range(10):
        arr.append(i)
    return arr

So you may come up with:

def intersection(array_one, array_two):
    array_one_index = 0
    array_two_index = 0
    size_of_array_one = len(array_one)
    size_of_array_two = len(array_two)
    while array_one_index < size_of_array_one and array_two_index < size_of_array_two:
        if array_one[array_one_index] < array_two[array_two_index]:
            array_one_index += 1
        elif array_one[array_one_index] > array_two[array_two_index]:
            array_two_index += 1
        else:
            yield array_one[array_one_index]
            array_one_index += 1
            array_two_index += 1

Advice 3

Your union does not omit duplicates. You can deal with them in a following manner:

def union(array_one, array_two):
    array_one_index = 0
    array_two_index = 0
    size_of_array_one = len(array_one)
    size_of_array_two = len(array_two)
    while array_one_index < size_of_array_one and array_two_index < size_of_array_two:
        if array_one_index > 0 and array_one[array_one_index - 1] == array_one[array_one_index]:
            array_one_index += 1
            continue
        if array_two_index > 0 and array_two[array_two_index - 1] == array_two[array_two_index]:
            array_two_index += 1
            continue
        if array_one[array_one_index] < array_two[array_two_index]:
            yield array_one[array_one_index]
            array_one_index += 1
        elif array_one[array_one_index] > array_two[array_two_index]:
            yield array_two[array_two_index]
            array_two_index += 1
        else:
            yield array_one[array_one_index]
            array_one_index += 1
            array_two_index += 1

    while array_two_index < size_of_array_two:
        if array_two_index > 0 and array_two[array_two_index - 1] == array_two[array_two_index]:
            array_two_index += 1
            continue
        yield array_two[array_two_index]
        array_two_index += 1

    while array_one_index < size_of_array_one:
        if array_one_index > 0 and array_one[array_one_index - 1] == array_one[array_one_index]:
            array_one_index += 1
            continue
        yield array_one[array_one_index]
        array_one_index += 1

Advice 4

Note also that you don't need

if arrayOneIndex == sizeOfArrayOne:

in union; only one of the "leftover" loop will iterate at least once.

Hope that helps.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.