Kursy Online

Lekcja – sortowanie przez scalanie (merge sort)

def sort_merge(list):

    list_len = len(list)
    sorted_list = []
    
    if list_len <= 1:
        sorted_list = list
    else:
        middle_point = list_len // 2
        list_left = sort_merge(list[:middle_point])
        list_right = sort_merge(list[middle_point:])
        
        idx_left = idx_right = 0
        while  idx_left < len(list_left) and idx_right < len(list_right):
            if list_left[idx_left] < list_right[idx_right]: sorted_list.append(list_left[idx_left]) idx_left += 1 else: sorted_list.append(list_right[idx_right]) idx_right += 1 sorted_list.extend(list_left[idx_left:]) sorted_list.extend(list_right[idx_right:]) print(f"DEBUG: {list} --> {sorted_list}")
    return sorted_list


list = [1,3,9,2,0,6,4,7,5,3]
list = sort_merge(list)

list

Rozwiązanie

import time
import random


#declarations
max_limit = 20000

my_list1 = [random.randint(0, max_limit) for i in range(max_limit)]
my_list2 = my_list1.copy()
my_list3 = my_list1.copy()
my_list4 = my_list1.copy()
my_list5 = my_list1.copy()


# functions

def sort_bubble(list):

    is_change = True

    while is_change:
        is_change = False
        for i in range(len(list)-1):
            if list[i] > list[i+1]:
                list[i],list[i+1] = list[i+1],list[i]
                is_change = True



def sort_bubble2(list):

    # don't compare values at the end of the list - they are already sorted
    max_index = len(list) - 1

    for max_not_sorted_index in range(max_index,0,-1):
        is_change = False
        for i in range(max_not_sorted_index):     
            if list[i] > list[i+1]:
                list[i],list[i+1] = list[i+1],list[i]
                is_change = True
        
        if not is_change:
            break
   

def sort_insert(list):

    # starting from 1, because this first element is already "sorted"
    # all items need to be put in place, so this loop needs to iterate for every element
    for sort_border in range(1,len(list)): 
        # we will try to put the new item into the sublist of sorted elements
        curr_idx = sort_border - 1
        value = list[curr_idx+1] # next value to be inserted into data

        while list[curr_idx] > value and curr_idx >= 0:
            list[curr_idx+1] = list[curr_idx]
            curr_idx = curr_idx-1

        #now the good position has been found and we put there the considered element
        list[curr_idx+1] = value


def sort_select(list):

    for run in range(len(list)):
        min_index = run
        for i in range(run+1, len(list)):
            if list[i] < list[min_index]:
                min_index = i
        list[run], list[min_index] = list[min_index], list[run]


def sort_merge(list):

    list_len = len(list)
    sorted_list = []
    
    if list_len <= 1:
        sorted_list = list
    else:
        middle_point = list_len // 2
        list_left = sort_merge(list[:middle_point])
        list_right = sort_merge(list[middle_point:])
        
        idx_left = idx_right = 0
        while  idx_left < len(list_left) and idx_right < len(list_right):
            if list_left[idx_left] < list_right[idx_right]:
                sorted_list.append(list_left[idx_left])
                idx_left += 1
            else:
                sorted_list.append(list_right[idx_right])
                idx_right += 1
        
        sorted_list.extend(list_left[idx_left:])
        sorted_list.extend(list_right[idx_right:])

    return sorted_list



# checking time - case sort_bubble

start = time.time()
sort_bubble(my_list1)
stop = time.time()
print(f'Sorting duration for function sort_bubble:    {stop - start}')


# checking time - case sort_bubble2

start = time.time()
sort_bubble2(my_list2)
stop = time.time()
print(f'Sorting duration for function sort_bubble2:   {stop - start}')


# checking time - case  sort_insert

start = time.time()
sort_insert(my_list3)
stop = time.time()
print(f'Sorting duration for function sort_insert:    {stop - start}')


# checking time - case  sort_select

start = time.time()
sort_select(my_list4)
stop = time.time()
print(f'Sorting duration for function sort_select:    {stop - start}')


# checking time - case  sort_merge

start = time.time()
sort_merge(my_list5)
stop = time.time()
print(f'Sorting duration for function sort_merge:    {stop - start}')