For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst case than the following algorithm:
def algo_X(A): i = 0 j = len(A)-1 while i < j: if A[i] != A[j]: k = i + 1 while k < j: if A[i] == A[k]: A[k], A[j] = A[j], A[k] break elif A[j] == A[k]: A[k], A[i] = A[i], A[k] break else: k += 1 if k == j: return False i += 1 j -= 1 return True
This algorithm returns True if the elements of list passed as argument can be manipulated (swapped) in order to create a new list, which, if we read from the left or from the right, has the same order of elements (palindrome). Else returns False.
For example, this list
['a', 'a', 'b', '2', 'b', 'b', ‘2’] can be ordered so that we have a list with the same elements in the same positions, if we read at the same time from the left and from the right:
['a', 'b', '2', 'b', '2', 'b', ‘a’].
Note that this is my interpretation of the algorithm, they did not tell us what this algorithm was supposed to do.
If I am not wrong, this algorithm, in the worst case (and average case), is O(n2), and Ɵ(n) in the best case.
The exercise specifically states that I don't have necessarily to change the list (like in
algo_X), but just to return
False specifying respectively if the list can be made a palindrome or not.
We cannot use libraries, but just built-in constructs. We cannot even use slice, for example. This is because we don't "know" exactly the time complexity of those functions. I will edit my question
To make a better algorithm for the worst case, I thought I could use
merge sort, whose time complexity is always n*log(n), plus a loop, which would not make the algorithm worse, asymptotically.
This is my
merge function for my merge sort function:
def merge(A, B): ls =  a, b = 0, 0 while a < len(A) and b < len(B): if A[a] <= B[b]: ls.append(A[a]) a += 1 else: ls.append(B[b]) b += 1 while a < len(A): ls.append(A[a]) a += 1 while b < len(B): ls.append(B[b]) b += 1 return ls
This is my merge sort function:
def merge_sort(A): if len(A) < 2: # basic condition return A L = merge_sort(A[0:len(A)//2]) R = merge_sort(A[len(A)//2:]) return merge(L, R)
Finally, here's my alternative, which returns
True, if the list can be made a palindrome,
def better_algo_x(A): if len(A) < 2: return True sorted_A = merge_sort(A) odd_groups = 0 current = sorted_A c = 1 # Used to count the number of characters that are equal between them for i in range(1, len(sorted_A)): if current == sorted_A[i]: c += 1 else: if c % 2 == 1: odd_groups += 1 if odd_groups > 1: return False current = sorted_A[i] c = 1 # for the last group of characters if c % 2 == 1: odd_groups += 1 if odd_groups > 1: return False return True
I have a few questions:
Are my functions correct?
Is my analysis of the time complexity of the algorithm
better_algo_xdo what it is supposed to do?
Does it do it in n*log(n) in the worst case?
Can I still improve it? How?
Do you know (other) better alternatives for
Of course, some questions might seem silly, but I would like to hear the opinion of some experts. Of course, I have tried my algorithms.