Scribd
Upload
2 views3 pages

Sorting Algorithms Revision

The document compares various sorting algorithms, highlighting Merge Sort's advantages over Bubble and Selection Sort, including faster performance and stability. It explains the partitioning process in QuickSort and differentiates between Min Heap and Max Heap. Additionally, it provides a table summarizing the time complexity and characteristics of several sorting techniques.

Uploaded by

kramu.mail1981
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 views3 pages

Sorting Algorithms Revision

The document compares various sorting algorithms, highlighting Merge Sort's advantages over Bubble and Selection Sort, including faster performance and stability. It explains the partitioning process in QuickSort and differentiates between Min Heap and Max Heap. Additionally, it provides a table summarizing the time complexity and characteristics of several sorting techniques.

Uploaded by

kramu.mail1981
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
You are on page 1/ 3

Sorting Algorithms: Key Concepts & Comparisons

1. Advantages of Merge Sort over Bubble and Selection Sort

1. Faster Performance:

- Merge Sort is faster with time complexity O(n log n) compared to O(n²) for Bubble and Selection Sort.

2. Stable Sort:

- Merge Sort is stable, preserving the order of equal elements. Selection Sort is not stable.

3. Efficient for Large Data:

- Suitable for large datasets. Bubble and Selection become slow with more elements.

4. Consistent Time:

- Merge Sort always runs in O(n log n) time, regardless of input order.

2. Partitioning Process in QuickSort

- Choose a pivot (often the last element).

- Arrange elements so smaller ones are on the left and larger ones on the right of the pivot.

- The pivot ends up in its correct position.

- This step divides the array for recursive sorting on both sides.

Example:

Array: [8, 3, 1, 7, 0, 10, 2], Pivot = 2

After partition: [1, 0, 2, 7, 8, 10, 3]

3. Difference Between Min Heap and Max Heap (with Diagrams)

Min Heap:

- Root is the smallest.


Sorting Algorithms: Key Concepts & Comparisons

- Every parent <= its children.

Example:

/ \

3 5

/\ /\

7 8 10 6

Max Heap:

- Root is the largest.

- Every parent >= its children.

Example:

10

/ \

7 9

/\ /\

3 6 2 5

Use Case:

- Min Heap: Min Priority Queue

- Max Heap: Max Priority Queue

4. Sorting Techniques Time Complexity Comparison

| Sorting Technique | Best Case | Average Case | Worst Case | Stable? | Extra Space |

|-------------------|-------------|--------------|------------|---------|------------------|

| Bubble Sort | O(n) | O(n²) | O(n²) | Yes | No (O(1)) |

| Selection Sort | O(n²) | O(n²) | O(n²) | No | No (O(1)) |

| Insertion Sort | O(n) | O(n²) | O(n²) | Yes | No (O(1)) |

| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes | Yes (O(n)) |
Sorting Algorithms: Key Concepts & Comparisons

| Quick Sort | O(n log n) | O(n log n) | O(n²) | No | No (O(log n)) |

| Heap Sort | O(n log n) | O(n log n) | O(n log n) | No | No (O(1)) |

| Radix Sort | O(nk) | O(nk) | O(nk) | Yes | Yes (O(n + k)) |

| Counting Sort | O(n + k) | O(n + k) | O(n + k) | Yes | Yes (O(k)) |

You might also like