📒
Notes
Cloud ComputingData Science/AIGame Development
  • Home
  • Big O
  • Data Structures & Algorithms
    • Data Structures
      • Array
      • Stack
      • Queue
      • Linked List
      • Binary Tree
    • Algorithms
      • Searching
      • Sorting
      • Graphs
        • Searching
        • Minimum Spanning Tree
        • Shortest Path Algorithms
      • String Algorithms
  • Object Oriented Programming
  • Languages
    • HTML/CSS
      • CSS
    • C++
    • C#
      • Types
      • Keywords
        • Modifiers
          • Access Modifiers
        • Method Parameters
      • Operators and Expressions
      • Collections
      • Constructors
      • Delegates
      • Indexers
      • Concepts
      • Features
        • LINQ
          • Operators
          • Working with Data
          • Methods
          • Resources
        • Asynchronous Programming
        • Reflection
    • Dart
    • GraphQL
    • JavaScript
      • Variable and Parameter
      • Built-in objects
        • Array
        • Built-in Functions
      • Functions
      • Classes
      • Prototype
      • Libraries
        • jQuery
        • React
          • Components
          • State and Lifecycle
          • Hooks
            • useState
            • useEffect
          • Resources
      • Testing Framework
      • Web APIs
    • Kotlin
      • Basics
    • Python
      • Basics
      • Data Structures
      • Functions
      • Resources
        • Flask
    • SQL
      • Basics
      • Operators
      • JOINs
      • Aggregations
      • Subqueries
      • Views
      • Functions
        • Window Functions
      • Stored Procedures
      • Performance Tuning
      • Extras
    • Resources
  • 🌐Web Frameworks
    • Angular
      • Templates
      • Directives
        • Attribute Directives
        • Structural Directives
    • ASP.NET
      • Fundamentals
        • Dependency Injection
        • Middleware
        • Session & State Management
      • Web apps
        • MVC
          • Controllers
            • Filters
          • Models
            • Model Binding
            • Model Validation
          • Views
            • Tag Helpers
            • View Components
          • Features
        • Client-side development
      • Web APIs
        • Controller-based APIs
        • Minimal APIs
        • OpenAPI
        • Content Negotiation
      • SignalR
      • Host and Deploy
        • IIS
      • Security
    • Django
      • The Request/Response Cycle
    • Terminologies
      • Web Server
        • Internet Information Services
    • Resources
  • 📱App Frameworks
    • Introduction
      • Resources
    • Xamarin
      • Lifecycle
      • Custom Renderers & Effects
      • Behaviors
      • Triggers
      • Gestures
      • Commands
      • Dependency Service in XF
      • Libraries
      • Showcase
    • .NET MAUI
      • Controls
      • Navigation
      • Storage Options
  • Multi-Platform Frameworks
    • .NET
      • .NET Framework
        • ADO.NET
        • WCF
      • Fundamentals
        • Logging
        • Testing
      • Advanced
        • Asynchronous Programming
        • Parallel Programming
        • Threading
        • Memory Management
          • Garbage Collection
    • Flutter
  • Object-Relational Mappers
    • Entity Framework
      • Application Models
      • Configuration
      • Setting Up
      • Advanced
  • Databases
    • Introduction
      • DBMS Architecture
      • Normalization
      • Database Transaction Models
    • Relational Databases
      • Microsoft SQL Server
        • Basics
        • Functions
        • Stored Procedures
        • Error Handling
        • Log Shipping
        • Querying and Manipulating JSON data
        • Statements
        • Topics
        • Extras
    • Non-Relational Databases
      • MongoDB
      • Redis
        • Data Structures
        • Introduction
        • Managing Database
  • Tools
    • Version Control
      • Git
        • Setup and Config
        • Basics
          • Sharing and Updating Projects
        • Resources
      • Perforce Helix
    • GitHub
    • Powershell
  • Software Development
    • Software Development Life Cycle
    • Software Design Patterns
      • GoF Design Patterns
      • Architectural Patterns
        • MVC
        • MVVM
        • N-tier Architecture
        • Onion Architecture
        • Data Transfer Objects
      • CQRS
    • Software Design Principles
      • S.O.L.I.D. Priniciple
  • System Design
    • Topics
      • Load Balancing
  • Topics
    • JWT
    • Caching
      • Static vs Dynamic Caching
    • OSI model
      • HTTP
    • Glossary
    • API
      • SOAP
      • REST
    • Microservices
    • WebHooks
    • Practice
    • Operating Systems
      • Windows
    • Architecture
  • 🔖Bookmarks
  • 🔗Resources
Powered by GitBook
On this page
  • Selection Sort
  • Bubble Sort
  • Insertion Sort
  • Quick Sort
  • Merge Sort

Was this helpful?

  1. Data Structures & Algorithms
  2. Algorithms

Sorting

PreviousSearchingNextGraphs

Last updated 2 years ago

Was this helpful?

Selection Sort

  • Selection sort is a simple algorithm, but inefficient.

  • First, find the smallest element using a linear scan and move it to the front (swap). Then, find the second smallest and move it, again doing a linear scan. Continue doing this until all the elements are in place.

void Swap(int[] array, int index1, int index2){
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

void SelectionSort(int[] array){
    var n = array.Length - 1;
    for(int i = 0; i <= n; i++){
        var minIdx = i;
        for(int j = i + 1; j <= n; j++){
            if(array[j] < array[minIdx]){
                minIdx = j;
            }
        }
        Swap(array, minIdx, i);
    }
}

Time Complexity: O(n^2)

Space Complexity: O(1)

Bubble Sort

  • In this algorithm, we start at the beginning of the array and swap the first two elements if the first is greater than the second. Then, we go to the next pair, and so on, continuously making sweeps of the array until it is sorted.

void BubbleSort(int[] array){
    var n = array.Length;
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - i - 1; j++){
            if(array[j] > array[j + 1]){
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    } 
}

Time Complexity: O(n^2)

Space Complexity: O(1)

Insertion Sort

void InsertionSort(int[] array){
    var n = array.Length - 1;
    for(int i = 1; i <= n; i++){
        var unsortedItem = array[i];
        var comparingItemIndex = i - 1;
        
        while(comparingItemIndex >= 0 && unsortedItem < array[comparingItemIndex]){
            array[comparingItemIndex + 1] = array[comparingItemIndex];
            comparingItemIndex--;
        }
        array[comparingItemIndex + 1] = unsortedItem;
    }
}

Time Complexity: O(n^2)

Space Complexity: ?

Quick Sort

Quicksort is another sorting algorithm based on the Divide and Conquer programming technique. In this algorithm, an element is first chosen as the pivot, and the entire array is then partitioned around this pivot.

As you've probably guessed, a good pivot is crucial for an efficient sort. The pivot can either be a random element, the media element, the first element, or even the last element.

Implementations of quicksort often differ in the way they choose a pivot. In the average case, quicksort will sort a large array with a good pivot in just O(nlogn) time.

The general pseudocode of quicksort repeatedly partitions the array on the pivot and positions it in the correct position of the subarray. It also places the elements smaller than the pivot to its left and elements greater than the pivot to its right.

void Swap(int[] array, int index1, int index2){
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

int Partition(int[] array, int lowIdx, int highIdx){
    var pivot = array[highIdx];
    var possibleIdx = lowIdx - 1;
    for(int i = lowIdx; i < highIdx; i++){
        if(array[i] <= pivot){
            possibleIdx++;
            Swap(array, i, possibleIdx);
        }
    }
    possibleIdx++;
    Swap(array, possibleIdx, highIdx);
    
    return possibleIdx;
}

void QuickSort(int[] array, int startIdx, int endIdx){
    if(startIdx < endIdx){
        var pivotIdx = Partition(array, startIdx, endIdx);
        if(startIdx < pivotIdx - 1)              // sort left half 
            QuickSort(array, startIdx, pivotIdx - 1);
        if(pivotIdx < endIdx)                    // sort right half
            QuickSort(array, pivotIdx, endIdx);      
    }
}

Time Complexity: O(n^2) Worst case O(n log n) Average case

Space Complexity:

O(log n)

Merge Sort

Divide and Conquer Programming Technique

  • Merge sort divides the array in half, sorts each of those halves, and then merge them back together.

  • Each of those halves has the same sorting algorithm applied to it.

void MergeSort(int[] array){
    int[] helper = new int[array.Length];
    MergeSort(array, helper, 0, array.Length - 1);
}
void MergeSort(int[] array, int[] helper, int lowIdx, int highIdx){
    if(lowIdx < highIdx){
        int middleIdx = (lowIdx + highIdx) / 2;
        MergeSort(array, helper, lowIdx, middleIdx);        //sort left half
        MergeSort(array, helper, middleIdx + 1, highIdx);   //sort right half
        Merge(array, helper, lowIdx, middleIdx, highIdx);
    }
}

void Merge(int[] array, int[] helper, int lowIdx, int middleIdx, int highIdx){
    /* Copy both halves into a helper array */
    for(int i = lowIdx; i <= highIdx; i++){
        helper[i] = array[i];
    }
    int helperLeft = lowIdx;
    int helperRight = middleIdx + 1;
    int currentIdx = lowIdx;
    
    while(helperLeft <= middleIdx && helperRight <= highIdx){
        // if left element is smaller than the right element
        if(helper[helperLeft] <= helper[helperRight]){
            array[currentIdx] = helper[helperLeft];
            helperLeft++;
        }
        // else if right element is smaller than the left element
        else{
            array[currentIdx] = helper[helperRight];
            helperRight++;
        }
        currentIdx++;
    }
    int remaining = middleIdx - helperLeft;
    for(int i = 0; i <= remaining; i++){
        array[currentIdx + i]  = helper[helperLeft + i];
    }
}

Time Complexity: O(n log n)

Space Complexity: O(n)

The space complexity being O(n) is due to the auxiliary space used to merge the parts of the array.

Selection Sort
Merge Sort
Sorting Algorithms Animationstoptal
Logo