Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Algorithms

Sorting

In data structures, sorting refers to the process of rearranging a collection of elements (such as numbers, strings, or objects) into a specific order, typically ascending or descending. This is achieved using sorting algorithms, which are designed to efficiently organize data for better analysis, retrieval, and manipulation.

Common sorting algorithms:

  • Bubble Sort: Simple but inefficient for large datasets. Repeatedly compares adjacent elements and swaps them if they are in the wrong order.

  • Insertion Sort: Efficient for small or partially sorted datasets. Iterates through the list, inserting each element into its correct position in the sorted part of the list.

  • Selection Sort: Divides the list into sorted and unsorted parts. Repeatedly finds the smallest element in the unsorted part and swaps it with the first element of the unsorted part.

  • Quick Sort: Divide and conquer algorithm that is generally efficient for large datasets. It works by recursively partitioning the list into smaller sublists and sorting them independently.

  • Merge Sort: Another divide and conquer algorithm that is efficient for large datasets. It works by recursively dividing the list into halves, sorting them independently, and then merging them back together in sorted order.

  • Heap Sort: Efficient algorithm that uses a heap data structure to achieve O(n log n) time complexity in all cases. It's in-place, stable, and versatile, also used for priority queues.

Example

    public static void InsertionSort(int[] arr)
    {
        int n = arr.Length;

        // Iterate through the array, starting from the second element
        for (int i = 1; i < n; i++)
        {
            int key = arr[i]; // Store the current element to be inserted
            int j = i - 1;

            // Shift elements greater than the key to the right
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }

            // Insert the key in its correct position
            arr[j + 1] = key;
        }
    }

Complexity

  • Time complexity: O(N^2)

  • Space complexity: O(1)

Factors to consider when choosing a sorting algorithm:

  • Time complexity: How long the algorithm takes to run in terms of the number of elements to be sorted.

  • Space complexity: How much extra memory the algorithm requires during its execution.

  • Stability: Whether the algorithm preserves the relative order of elements with equal keys.

  • Nature of the input data: Some algorithms are more efficient for certain types of data (e.g., partially sorted data).

Complexity Table

Algorithm
Best-case Time Complexity
Average-case Time Complexity
Worst-case Time Complexity
Space Complexity
Stability

Bubble Sort

O(n)

O(n^2)

O(n^2)

O(1)

Stable

Insertion Sort

O(n)

O(n^2)

O(n^2)

O(1)

Stable

Selection Sort

O(n^2)

O(n^2)

O(n^2)

O(1)

Unstable

Merge Sort

O(n log n)

O(n log n)

O(n log n)

O(n)

Stable

Quick Sort

O(n log n)

O(n log n)

O(n^2)

O(log n)

Unstable

Heap Sort

O(n log n)

O(n log n)

O(n log n)

O(1)

Stable

PreviousRecursionNextSearching

Last updated 1 year ago