Scribd
Upload
2 views2 pages

Chapter 01 Sorting Notes

Chapter 01 discusses sorting, defining it as the arrangement of elements based on specific criteria. It outlines key properties of sorting algorithms, including time complexity, stability, and whether they are in-place. Various sorting algorithms are detailed, such as Bubble Sort, Selection Sort, Insertion Sort, Heap Sort, Counting Sort, Radix Sort, and Bucket Sort, each with their respective characteristics and complexities.

Uploaded by

ARYAN DURGE
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
2 views2 pages

Chapter 01 Sorting Notes

Chapter 01 discusses sorting, defining it as the arrangement of elements based on specific criteria. It outlines key properties of sorting algorithms, including time complexity, stability, and whether they are in-place. Various sorting algorithms are detailed, such as Bubble Sort, Selection Sort, Insertion Sort, Heap Sort, Counting Sort, Radix Sort, and Bucket Sort, each with their respective characteristics and complexities.

Uploaded by

ARYAN DURGE
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

Chapter 01 – Sorting

Sorting is the process of arranging elements based on a specific criterion such as ascending,
descending, or custom order.

Key Properties of Sorting Algorithms


• Time Complexity
• Space Complexity
• Stable or Unstable
• Comparison or Non■Comparison Based
• In■place or Not In■place

Stable Sorting Algorithm


A sorting algorithm is stable if it preserves the relative order of equal elements.

In■place Sorting
An in■place sorting algorithm does not require extra memory beyond a few variables.

Bubble Sort
Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.
Time Complexity: Best O(n), Average O(n²), Worst O(n²)
Stable: Yes | In■place: Yes | Comparison Based: Yes

Selection Sort
Selection Sort repeatedly selects the minimum element from the unsorted part and places it at the
correct position.
Time Complexity: O(n²) in all cases
Stable: No | In■place: Yes | Comparison Based: Yes

Insertion Sort
Insertion Sort builds the sorted array one element at a time by inserting elements into their correct
position.
Time Complexity: Best O(n), Average O(n²), Worst O(n²)
Stable: Yes | In■place: Yes | Comparison Based: Yes

Heap Sort
Heap Sort builds a Max Heap and repeatedly extracts the maximum element to sort the array.
Time Complexity: O(n log n) in all cases
Stable: No | In■place: Yes | Comparison Based: Yes

Counting Sort
Counting Sort counts the frequency of each element and reconstructs the array.
Time Complexity: O(n + k)
Stable: Yes (prefix sum) | In■place: No | Comparison Based: No
Radix Sort
Radix Sort sorts numbers digit by digit using stable counting sort.
Time Complexity: O(d × (n + k))
Stable: Yes | In■place: No | Comparison Based: No

Bucket Sort
Bucket Sort divides elements into buckets, sorts each bucket, and merges them.
Time Complexity: Best/Average O(n + k), Worst O(n²)
Stable: Depends | In■place: No | Comparison Based: No

You might also like