#2 DSA: Gambaran Awal

import time
import random

# Function untuk merge_sort
def mergeSort(myList):

  if len(myList) > 1:
        mid = len(myList) // 2
        left = myList[:mid]
        right = myList[mid:]

        # Recursive call on each half
        mergeSort(left)
        mergeSort(right)

        # Two iterators for traversing the two halves
        i = 0
        j = 0
        
        # Iterator for the main list
        k = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
              # The value from the left half has been used
              myList[k] = left[i]
              # Move the iterator forward
              i += 1
            else:
                myList[k] = right[j]
                j += 1
            # Move to the next slot
            k += 1

        # For all the remaining values
        while i < len(left):
            myList[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            myList[k]=right[j]
            j += 1
            k += 1

# Perlahan
# O(n^2)
def bubble_sort(our_list):

  startTime = time.time()
  
  for i in range(len(our_list)):
        # We want the last pair of adjacent elements to be (n-2, n-1)
        for j in range(len(our_list) - 1):
            if our_list[j] > our_list[j+1]:
                # Swap
                our_list[j], our_list[j+1] = our_list[j+1], our_list[j]

  timeTaken = time.time() - startTime

  print("Bubble sort ", timeTaken, "seconds")

# Lebih laju
# O(n log n)
def merge_sort(my_list):
  startTime = time.time()

  mergeSort(my_list)

  timeTaken = time.time() - startTime

  print("Merge sort: ", timeTaken, "seconds")


# Contoh argument yang boleh digunakan untuk menguji kelajuan masa
list1 = [4, 5, 0, 1]
list2 = [3, 42, 1, 2, 5, 7, 23, 4, 0, 121]
list3 = [54, 26, 93, 17, 77, 31, 44, 55, 20]

list4 = [ random.randint(0, 10000) for x in range(10000) ]

# Boleh mencuba function di sini
bubble_sort(list4)
merge_sort(list4)