import time

class Sorter():

    def sort(self, sortType, inputText, divSymbol, customAlphabet = ""):
        results = {}
        array = inputText.split(self.symbolConvertor(divSymbol))
        alphabet = list(customAlphabet)

        begining = time.time()
        operationNumber = 0

        if (sortType == "bubbleSort"):
            operationNumber = self.bubbleSort(array)
        if (sortType=="mergeSort"):
            operationNumber = self.mergeSort(array)
        if (sortType=="insertionSort"):
            operationNumber = self.insertionSort(array)
        if (sortType=="customSort"):
            operationNumber = self.customSort(array, alphabet)

        end = time.time()
        duration = str(end - begining)
        results['output'] = array
        results['time'] = duration
        results['operationNum'] = operationNumber

        return results

    def symbolConvertor(self, divSymbol):
        if (divSymbol=="space"):
            return chr(32)
        if (divSymbol=="point"):
            return '.'
        return ','

    def bubbleSort(self, arr):
        operationsNum = 0
        n = len(arr)
        # Traverse through all array elements
        for i in range(n - 1):
            for j in range(0, n - i - 1):

                # traverse the array from 0 to n-i-1
                # Swap if the element found is greater
                # than the next element
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    operationsNum += 1
        return operationsNum

    def mergeSort(self, arr):
        operatorsNum = 0

        if len(arr) > 1:

            # Finding the mid of the array
            mid = len(arr) // 2

            # Dividing the array elements
            L = arr[:mid]

            # into 2 halves
            R = arr[mid:]

            # Sorting the first half
            operatorsNum += self.mergeSort(L)

            # Sorting the second half
            operatorsNum += self.mergeSort(R)

            i = j = k = 0

            # Copy data to temp arrays L[] and R[]
            while i < len(L) and j < len(R):
                if L[i] < R[j]:
                    arr[k] = L[i]
                    i += 1
                else:
                    arr[k] = R[j]
                    j += 1
                k += 1
                operatorsNum += 1

            # Checking if any element was left
            while i < len(L):
                arr[k] = L[i]
                i += 1
                k += 1
                operatorsNum += 1

            while j < len(R):
                arr[k] = R[j]
                j += 1
                k += 1
                operatorsNum += 1

        return operatorsNum

    def insertionSort(self, arr):
        operatorsNum = 0
        # Traverse through 1 to len(arr)
        for i in range(1, len(arr)):

            key = arr[i]

            # Move elements of arr[0..i-1], that are
            # greater than key, to one position ahead
            # of their current position
            j = i - 1
            while j >= 0 and key < arr[j]:
                arr[j + 1] = arr[j]
                j -= 1
                operatorsNum += 1
            arr[j + 1] = key
            operatorsNum += 1

        return operatorsNum

    def customSort(self, arr, alphabet):
        operatorsNum = 0
        if (alphabet == ""):
            return 0

        for i in range(len(arr)):
            # Find the minimum element in remaining
            # unsorted array
            min_idx = i
            for j in range(i + 1, len(arr)):
                operatorsNum += 1
                if self.compareStrByAlphabet(arr[min_idx], arr[j], alphabet):
                    operatorsNum += 2
                    min_idx = j

            # Swap the found minimum element with
            # the first element
            arr[i], arr[min_idx] = arr[min_idx], arr[i]

        return operatorsNum

    def compareStrByAlphabet(self, a, b, alphabet):
        if (a == b or len(b) == 0):
            return False
        elif len(a) == 0:
            return True
        else:
            for i in range(min(len(a), len(b))):
                if a[i] not in alphabet and b[i] not in alphabet:
                    return False
                elif a[i] not in alphabet:
                    return True
                elif b[i] not in alphabet:
                    return False

                if (a[i] != b[i]):
                    return alphabet.index(a[i]) > alphabet.index(b[i])

            return len(a) > len(b)
        return True

    def shellSort(self, arr):
        gap = len(arr) // 2  # initialize the gap

        while gap > 0:
            i = 0
            j = gap

            # check the array in from left to right
            # till the last possible index of j
            while j < len(arr):

                if arr[i] > arr[j]:
                    arr[i], arr[j] = arr[j], arr[i]

                i += 1
                j += 1

                # now, we look back from ith index to the left
                # we swap the values which are not in the right order.
                k = i
                while k - gap > -1:

                    if arr[k - gap] > arr[k]:
                        arr[k - gap], arr[k] = arr[k], arr[k - gap]
                    k -= 1

            gap //= 2

    def selectionSort(self, arr):
        for i in range(len(arr)):

            # Find the minimum element in remaining
            # unsorted array
            min_idx = i
            for j in range(i + 1, len(arr)):
                if arr[min_idx] > arr[j]:
                    min_idx = j

            # Swap the found minimum element with
            # the first element
            arr[i], arr[min_idx] = arr[min_idx], arr[i]