Sorting Algorithms

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

• Time Complexity:
  • Best Case: O(n)
  • Worst Case: O(n^2)
  • Average Case: O(n^2)
• Space Complexity: O(1)

Selection Sort

Selection Sort is an in-place comparison sorting algorithm that divides the input list into two parts: a sorted sublist and an unsorted sublist.

• Time Complexity:
  • Best Case: O(n^2)
  • Worst Case: O(n^2)
  • Average Case: O(n^2)
• Space Complexity: O(1)

Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time.

• Time Complexity:
  • Best Case: O(n)
  • Worst Case: O(n^2)
  • Average Case: O(n^2)
• Space Complexity: O(1)

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, sorts each half separately, and then merges them.

• Time Complexity:
  • Best Case: O(n log n)
  • Worst Case: O(n log n)
  • Average Case: O(n log n)
• Space Complexity: O(n)

Quick Sort

Quick Sort is a divide-and-conquer algorithm that selects a 'pivot' element from the array and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot.

• Time Complexity:
  • Best Case: O(n log n)
  • Worst Case: O(n^2)
  • Average Case: O(n log n)
• Space Complexity: O(log n)