πŸ“–
Wiki
CNCFSkywardAIHuggingFaceLinkedInKaggleMedium
  • Home
    • πŸš€About
  • πŸ‘©β€πŸ’»πŸ‘©Freesoftware
    • πŸ‰The GNU Hurd
      • πŸ˜„The files extension
      • πŸ“½οΈTutorial for starting
      • 🚚Continue Working for the Hurd
      • πŸš΄β€β™‚οΈcgo
        • πŸ‘―β€β™€οΈStatically VS Dynamically binding
        • 🧌Different ways in binding
        • πŸ‘¨β€πŸ’»Segfault
      • πŸ›ƒRust FFI
    • πŸ§šπŸ»β€β™‚οΈProgramming
      • πŸ“–Introduction to programming
      • πŸ“–Mutable Value Semantics
      • πŸ“–Linked List
      • πŸ“–Rust
        • πŸ“–Keyword dyn
        • πŸ“–Tonic framework
        • πŸ“–Tokio
        • πŸ“–Rust read files
  • πŸ›€οΈAI techniques
    • πŸ—„οΈframework
      • 🧷pytorch
      • πŸ““Time components
      • πŸ““burn
    • 🍑Adaptation
      • 🎁LoRA
        • ℹ️Matrix Factorization
        • πŸ“€SVD
          • ✝️Distillation of SVD
          • 🦎Eigenvalues of a covariance matrix
            • 🧧Eigenvalues
            • πŸͺCovariance Matrix
        • πŸ›«Checkpoint
      • 🎨PEFT
    • πŸ™‹β€β™‚οΈTraining
      • πŸ›»Training with QLoRA
      • 🦌Deep Speed
    • 🧠Stable Diffusion
      • πŸ€‘Stable Diffusion model
      • πŸ“ΌStable Diffusion v1 vs v2
      • πŸ€Όβ€β™€οΈThe important parameters for stunning AI image
      • ⚾Diffusion in image
      • 🚬Classifier Free Guidance
      • ⚜️Denoising strength
      • πŸ‘·Stable Diffusion workflow
      • πŸ“™LoRA(Stable Diffusion)
      • πŸ—ΊοΈDepth maps
      • πŸ“‹CLIP
      • βš•οΈEmbeddings
      • πŸ• VAE
      • πŸ’₯Conditioning
      • 🍁Diffusion sampling/samplers
      • πŸ₯ Prompt
      • πŸ˜„ControlNet
        • πŸͺ‘Settings Explained
        • 🐳ControlNet with models
    • πŸ¦™Large Language Model
      • ☺️SMID
      • πŸ‘¨β€πŸŒΎARM NEON
      • 🍊Metal
      • 🏁BLAS
      • πŸ‰ggml
      • πŸ’»llama.cpp
      • 🎞️Measuring model quality
      • πŸ₯žType for NNC
      • πŸ₯žToken
      • πŸ€Όβ€β™‚οΈDoc Retrieval && QA with LLMs
      • Hallucination(AI)
    • 🐹diffusers
      • πŸ’ͺDeconstruct the Stable Diffusion pipeline
  • 🎹Implementing
    • πŸ‘¨β€πŸ’»diffusers
      • πŸ“–The Annotated Diffusion Model
  • 🧩Trending
    • πŸ“–Trending
      • πŸ“–Vector database
      • 🍎Programming Languages
        • πŸ“–Go & Rust manage their memories
        • πŸ“–Performance of Rust and Python
        • πŸ“–Rust ownership and borrowing
      • πŸ“–Neural Network
        • 🎹Sliding window/convolutional filter
      • Quantum Machine Learning
  • 🎾Courses Collection
    • πŸ“–Courses Collection
      • πŸ“šAcademic In IT
        • πŸ“Reflective Writing
      • πŸ“–UCB
        • πŸ“–CS 61A
          • πŸ“–Computer Science
          • πŸ“–Scheme
          • πŸ“–Python
          • πŸ“–Data Abstraction
          • πŸ“–Object-Oriented Programming
          • πŸ“–Interpreters
          • πŸ“–Streams
      • 🍎MIT Algorithm Courses
        • 0️MIT 18.01
          • 0️Limits and continuity
          • 1️Derivatives
          • 3️Integrals
        • 1️MIT 6.042J
          • πŸ”’Number Theory
          • πŸ“ŠGraph Theory
            • 🌴Graph and Trees
            • 🌲Shortest Paths and Minimum Spanning Trees
        • 2️MIT 6.006
          • Intro and asymptotic notation
          • Sorting and Trees
            • Sorting
            • Trees
          • Hashing
          • Graphs
          • Shortest Paths
          • Dynamic Programming
          • Advanced
        • 3️MIT 6.046J
          • Divide and conquer
          • Dynamic programming
          • Greedy algorithms
          • Graph algorithms
Powered by GitBook
On this page

Was this helpful?

Edit on GitHub
  1. Courses Collection
  2. Courses Collection
  3. MIT Algorithm Courses
  4. MIT 6.006
  5. Sorting and Trees

Sorting

A comparison sort cannot perform better than O(n log n) on average.

Non-comparison sorts can have better performance in certain situations, but are often limited by the range of values in the input data.

Binary insertion sort

def insertion_sort(arr):
    """
    The time complexity is O(n^2), less efficient than advance sorting algorithms like
    quick soer and mergesort.
    """
    for i in range(1, len(arr)):
        key=arr[i]
        j=i-1
        while j>=0 and arr[j]>key:
            arr[j+1]=arr[j]
            j-=1
        arr[j+1]=key
    return arr
    
    
# implementation of binary insertion with bisect
def binary_insertion_sort(arr):
    """
    bisect moudle provides a simple and efficient way to perform binary search
    on sorted sequences. bisect_left help find the index at which a value
    should be inserted into a sorted sequence, while maintaining the order of the sequence.
    """
    for i in range(1, len(arr)):
        x=arr[i]
        j=bisect.bisect_left(arr,x,0,i)
        # this is an effectively shifts all the elements in the range [j,i-1] one
        # position to the right, to make room for the new element that will be 
        # inserted at index 'j'
        arr[j+1:i+1]=arr[j:i]
        arr[j]=x
    return arr

Heap sort

Worst-case time complexity is O(n log n) and O(1) for space complexity, it an efficient sorting algortihn for large inputs.

def heap_sort(arr):
    # Heapify the array
    n=len(arr)
    for i in range(n//2-1,-1,-1):
        heapify(arr, n, i)

    # Extract elements from the heap one by one
    for i in range(n-1,0,-1):
        arr[i],arr[0]=arr[0],arr[i]
        heapify(arr,i,0)
    return arr

def heapify(arr, n, i):
    """
    This function takes an array, the size of the heap n, and the index i of the
    root of the subtree being heapified.
    It recursively swaps elements in the subtree to maintain the max heap property,
    where the parent node is greater than or equal to its child nodes.
    """
    largest =i
    l=2*i+1
    r=2*i+2
    
    if l<n and arr[l]>arr[largest]:
        largest=l
    if r<n and arr[r] >arr[largest]:
        largest=r
    if largest !=i:
        arr[i], arr[largest] =arr[largest], arr[i]
        heapify(arr, n, largest)

arr=[64,25,12,22,11]
assert heap_sort(arr)== [11,12,22,25,64]

Insertion sort

O(n^2) but it still useful for small input sizes

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key=arr[i]
        j=i-1
        while j>=0 and arr[j]>key:
            arr[j+1]=arr[j]
            j-=1
        arr[j+1]=key
    return arr

arr=[64,25,12,22,11]
assert insertion_sort(arr)==[11,12,22,25,64]

Merge sort

def merge_sort(arr):
    """
    Time Complexity is O(n log n)
    It is more efficient than Insertion sort and Bubble sort,
    less than Quick sort in most case.
    """
    if len(arr)>1:
        mid=len(arr)//2
        left_half=arr[:mid]
        right_half=arr[mid:]
        
        merge_sort(left_half)
        merge_sort(right_half)
        
        i=j=k=0
        while i<len(left_half) and j<len(right_half):
            if left_half[i]<right_half[j]:
                arr[k]=left_half[i]
                i+=1
            else:
                arr[k]=right_half[j]
                j+=1
            k+=1
        while i<len(left_half):
            arr[k]=left_half[i]
            i+=1
            k+=1
        while j<len(right_half):
            arr[k]=right_half[j]
            j+=1
            k+=1
    return err

Quick sort

def quick_sort(arr):
    """
    O(n log n) in the average case, O(n^2) in the worst case(only when the pivot
    selection strategy is poor)
    So, we can use a random pivot or selecting the median of these elementsthon
    """
    if len(arr)<=1:
        return arr
    else:
        pivot=arr[0]
        less=[]
        greater=[]
        for i in arr[1:]:
            if i<=pivot:
                less.append(i)
            else:
                greater.append(i)
        # recursively calls itself on the two sub-arrays
        return quick_sort(less)+[pivot]+quick_sort(greater)

References

PreviousSorting and TreesNextTrees

Last updated 1 year ago

Was this helpful?

🎾
πŸ“–
🍎
2️
LogoSorting algorithmWikipedia