Skip to content

Sort

Selection Sort

Idea:

  1. Find the minimum element in the unsorted part of the array.
  2. Swap it with the first element of the unsorted part.
  3. Selection sort the remaining unsorted items

Computational Complexity:

  1. Time Complexity: O(N^2)
  2. Space Complexity: O(1)

Heap Sort

Idea:

Naive approach: 1. Insert all elements into a mac heap and create an output array. 2. Repeat the following steps: - Remove the largest element from the heap - Place it at the end of the output array

In-place approach: 1. Build a max heap from the input array. 2. Swap the first element with the last element of the heap. 3. Reduce the size of the heap by 1. 4. Heapify the root element.

Computational Complexity:

  1. Time Complexity: O(NlogN)
  2. Space Complexity: O(1)

Merge Sort

Idea:

  1. Divide the array into two halves.
  2. Recursively sort the two halves.
  3. Merge the two sorted halves.

Computational Complexity:

  1. Time Complexity: O(NlogN) (Faster than Heapsort)
  2. Space Complexity: O(N)

Insertion Sort

Idea:

  1. Start from the second element and compare it with the previous elements.
  2. If the current element is smaller, shift the previous elements to the right.

Computational Complexity:

  1. Time Complexity: O(N)
  2. Space Complexity: O(1)

Quick Sort

Idea:

  1. Choose a pivot element.
  2. Partition the array such that all elements less than the pivot are on the left and all elements greater than the pivot are on the right.
  3. Repeat the process for the left and right subarrays.

Computational Complexity:

  1. Time Complexity: O(NlogN) (Average case)
  2. Space Complexity: O(logN)