Scribd
Upload
3 views3 pages

Sorting Algorithms Notes

The document provides an overview of three sorting algorithms: Selection Sort, Bubble Sort, and Insertion Sort, including their implementations in Python. It details their uses, when to apply them, and relevant LeetCode question types. A time complexity table is also included, showing the performance of each algorithm in best, average, and worst-case scenarios.

Uploaded by

Rishabh but i think there is no fake thing like god
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

Sorting Algorithms Notes

The document provides an overview of three sorting algorithms: Selection Sort, Bubble Sort, and Insertion Sort, including their implementations in Python. It details their uses, when to apply them, and relevant LeetCode question types. A time complexity table is also included, showing the performance of each algorithm in best, average, and worst-case scenarios.

Uploaded by

Rishabh but i think there is no fake thing like god
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Sorting Algorithms Notes

Selection Sort
class Solution:
def selectionSort(self, nums):

n = len(nums)

# Traverse the array


for i in range(n):

# Assume current index has minimum element


min_index = i

# Find minimum element


for j in range(i + 1, n):
if nums[j] < nums[min_index]:
min_index = j

# Swap minimum element with current element


nums[i], nums[min_index] = nums[min_index], nums[i]

return nums

# Driver Code
obj = Solution()

arr = [64, 25, 12, 22, 11]

print([Link](arr))

Uses
• Used when memory usage must be low
• Performs minimum number of swaps
• Good for small datasets
• Easy to understand for beginners

When to Use
• Small arrays
• When swapping cost is expensive
• Educational purposes and interviews

LeetCode Question Types


• Basic sorting implementation questions
• Find minimum/maximum repeatedly
• Questions where minimum swaps matter

Bubble Sort
class Solution:
def bubbleSort(self, nums):

n = len(nums)
# Traverse the array
for i in range(n):

# Last i elements are already sorted


for j in range(0, n - i - 1):

# Swap if elements are in wrong order


if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]

return nums

# Driver Code
obj = Solution()

arr = [64, 34, 25, 12, 22, 11, 90]

print([Link](arr))

Uses
• Very simple sorting algorithm
• Used for learning sorting concepts
• Detects whether array is already sorted

When to Use
• Very small datasets
• Beginner coding practice
• When simplicity is more important than speed

LeetCode Question Types


• Adjacent swapping problems
• Detect if array is sorted
• Simulation-based questions

Insertion Sort
class Solution:
def insertionSort(self, nums):

# Traverse from second element


for i in range(1, len(nums)):

key = nums[i]
j = i - 1

# Shift larger elements


while j >= 0 and nums[j] > key:
nums[j + 1] = nums[j]
j -= 1

# Insert key at correct position


nums[j + 1] = key

return nums

# Driver Code
obj = Solution()

arr = [12, 11, 13, 5, 6]


print([Link](arr))

Uses
• Efficient for small or nearly sorted arrays
• Used in hybrid sorting algorithms
• Faster than Bubble and Selection Sort for small inputs

When to Use
• Nearly sorted data
• Small datasets
• Online sorting (data comes one by one)

LeetCode Question Types


• Nearly sorted arrays
• Linked list sorting
• Online processing problems

Time Complexity Table


Algorithm Best Average Worst

Selection Sort O(n²) O(n²) O(n²)


Bubble Sort O(n) O(n²) O(n²)
Insertion Sort O(n) O(n²) O(n²)

Complexity Formula
T(n) = O(n²)
T(n) = O(n log n)

You might also like