Зміст курсу

Sorting Algorithms

1. Simple Algorithms

What is the Sorting Big-O Notation Overview Selection Sort Insertion Sort Counting Sort Bubble Sort Cocktail Sort

2. Divide and Conquer Algorithms

Merge Sort Quicksort

3. Problems

Problem A Problem B Problem C Problem D

Merge Sort

You have already discovered intuitive algorithms that sort an array using O(N^2) time. This time is not the limit! Now let's learn advanced and quick algorithms with less Time Complexity than O(N^2).

The first one is a Divide and Conquer recursive algorithm called Merge sort. The main idea is to divide array into two parts, sort them, and then merge these two parts. The algorithm is recursive because parts of array are sorted using Merge Sort function, too.

To see how it works, here is an example.

Halve the array.
Sort each part using Merge Sort.
Merge these two sorted arrays into one.

How to merge? You have two sorted arrays a1 and a2, let’s set pointers p1 and p2 at the beginning of each of them. temp = [] is an array to store the sorted array of elements from a1 and a2. Compare current elements: if a1[p1] < a2[p2], then put a1[p1] to temp and increase p1 by 1. Else do the same for p2.

Merge Example

Algorithm

We have to implement two functions:

mergeSort(arr) - divides arr into two same-length parts and sorts them (calls itself).

merge(m, arr) - merges two sorted subarrays arr[:m] and arr[m:]. Called inside mergeSort() function.

Time complexity: O(NlogN), and here we need an explanation.

This algorithm takes less time than all previous, since O(NlogN) < O(N^2). Why this?

To halve array until it is possible, it takes up to O(logN) operations. So the total number of sortings is O(logN).
To merge two halves, it takes up to O(N) time.
Each 'sorting' requires merging, so the total time is O(NlogN).

Space Complexity: O(1).

There is an algorithm:


              123456789101112131415161718192021222324252627282930
            
def merge(arr, m):
  i, j = 0, m # Pointers at the beginnings of subarrays
  temp = []

   # Merge sorted arrays to temp
  while i<m or j<len(arr):
    if i>=m: # Left subarray is empty
      temp.append(arr[j])
      j+=1
    elif j>=len(arr): # Right subarray is empty
      temp.append(arr[i])
      i+=1
    else:
      if arr[i] < arr[j]:
        temp.append(arr[i])
        i+=1
      else:
        temp.append(arr[j])
        j+=1
  return temp
    	
def mergeSort(arr):
  if len(arr) == 1: # Base case
    return arr
  m = len(arr) // 2

  arr[:m] = mergeSort(arr[:m])
  arr[m:] = mergeSort(arr[m:])
  return merge(arr, m)

Завдання

Copy the code of merge() and mergeSort() from the example above or implement it by yourself.

Test this algorithm for given arrays.

Завдання

Copy the code of merge() and mergeSort() from the example above or implement it by yourself.

Test this algorithm for given arrays.

Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів

Все було зрозуміло?

Секція 2. Розділ 1

Merge Sort

To see how it works, here is an example.

Halve the array.
Sort each part using Merge Sort.
Merge these two sorted arrays into one.

Merge Example

Algorithm

We have to implement two functions:

mergeSort(arr) - divides arr into two same-length parts and sorts them (calls itself).

merge(m, arr) - merges two sorted subarrays arr[:m] and arr[m:]. Called inside mergeSort() function.

Time complexity: O(NlogN), and here we need an explanation.

This algorithm takes less time than all previous, since O(NlogN) < O(N^2). Why this?

To halve array until it is possible, it takes up to O(logN) operations. So the total number of sortings is O(logN).
To merge two halves, it takes up to O(N) time.
Each 'sorting' requires merging, so the total time is O(NlogN).

Space Complexity: O(1).

There is an algorithm:


              123456789101112131415161718192021222324252627282930
            
def merge(arr, m):
  i, j = 0, m # Pointers at the beginnings of subarrays
  temp = []

   # Merge sorted arrays to temp
  while i<m or j<len(arr):
    if i>=m: # Left subarray is empty
      temp.append(arr[j])
      j+=1
    elif j>=len(arr): # Right subarray is empty
      temp.append(arr[i])
      i+=1
    else:
      if arr[i] < arr[j]:
        temp.append(arr[i])
        i+=1
      else:
        temp.append(arr[j])
        j+=1
  return temp
    	
def mergeSort(arr):
  if len(arr) == 1: # Base case
    return arr
  m = len(arr) // 2

  arr[:m] = mergeSort(arr[:m])
  arr[m:] = mergeSort(arr[m:])
  return merge(arr, m)

Завдання

Copy the code of merge() and mergeSort() from the example above or implement it by yourself.

Test this algorithm for given arrays.

Завдання

Copy the code of merge() and mergeSort() from the example above or implement it by yourself.

Test this algorithm for given arrays.

Все було зрозуміло?

Секція 2. Розділ 1

Merge Sort

To see how it works, here is an example.

Halve the array.
Sort each part using Merge Sort.
Merge these two sorted arrays into one.

Merge Example

Algorithm

We have to implement two functions:

mergeSort(arr) - divides arr into two same-length parts and sorts them (calls itself).

merge(m, arr) - merges two sorted subarrays arr[:m] and arr[m:]. Called inside mergeSort() function.

Time complexity: O(NlogN), and here we need an explanation.

This algorithm takes less time than all previous, since O(NlogN) < O(N^2). Why this?

To halve array until it is possible, it takes up to O(logN) operations. So the total number of sortings is O(logN).
To merge two halves, it takes up to O(N) time.
Each 'sorting' requires merging, so the total time is O(NlogN).

Space Complexity: O(1).

There is an algorithm:


              123456789101112131415161718192021222324252627282930
            
def merge(arr, m):
  i, j = 0, m # Pointers at the beginnings of subarrays
  temp = []

   # Merge sorted arrays to temp
  while i<m or j<len(arr):
    if i>=m: # Left subarray is empty
      temp.append(arr[j])
      j+=1
    elif j>=len(arr): # Right subarray is empty
      temp.append(arr[i])
      i+=1
    else:
      if arr[i] < arr[j]:
        temp.append(arr[i])
        i+=1
      else:
        temp.append(arr[j])
        j+=1
  return temp
    	
def mergeSort(arr):
  if len(arr) == 1: # Base case
    return arr
  m = len(arr) // 2

  arr[:m] = mergeSort(arr[:m])
  arr[m:] = mergeSort(arr[m:])
  return merge(arr, m)

Завдання

Copy the code of merge() and mergeSort() from the example above or implement it by yourself.

Test this algorithm for given arrays.

Завдання

Copy the code of merge() and mergeSort() from the example above or implement it by yourself.

Test this algorithm for given arrays.

Все було зрозуміло?

To see how it works, here is an example.

Halve the array.
Sort each part using Merge Sort.
Merge these two sorted arrays into one.

Merge Example

Algorithm

We have to implement two functions:

mergeSort(arr) - divides arr into two same-length parts and sorts them (calls itself).

merge(m, arr) - merges two sorted subarrays arr[:m] and arr[m:]. Called inside mergeSort() function.

Time complexity: O(NlogN), and here we need an explanation.

This algorithm takes less time than all previous, since O(NlogN) < O(N^2). Why this?

To halve array until it is possible, it takes up to O(logN) operations. So the total number of sortings is O(logN).
To merge two halves, it takes up to O(N) time.
Each 'sorting' requires merging, so the total time is O(NlogN).

Space Complexity: O(1).

There is an algorithm:


              123456789101112131415161718192021222324252627282930
            
def merge(arr, m):
  i, j = 0, m # Pointers at the beginnings of subarrays
  temp = []

   # Merge sorted arrays to temp
  while i<m or j<len(arr):
    if i>=m: # Left subarray is empty
      temp.append(arr[j])
      j+=1
    elif j>=len(arr): # Right subarray is empty
      temp.append(arr[i])
      i+=1
    else:
      if arr[i] < arr[j]:
        temp.append(arr[i])
        i+=1
      else:
        temp.append(arr[j])
        j+=1
  return temp
    	
def mergeSort(arr):
  if len(arr) == 1: # Base case
    return arr
  m = len(arr) // 2

  arr[:m] = mergeSort(arr[:m])
  arr[m:] = mergeSort(arr[m:])
  return merge(arr, m)

Завдання

Copy the code of merge() and mergeSort() from the example above or implement it by yourself.

Test this algorithm for given arrays.

Секція 2. Розділ 1