Scribd
Upload
4 views3 pages

Sorting Algorithms Explanation

The document provides an overview of various sorting algorithms, including Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Counting Sort, Radix Sort, and Bucket Sort, detailing their working principles and time complexities. Each algorithm is summarized with its best, average, and worst-case time complexities, as well as space complexity and stability. A summary table consolidates this information for quick reference.

Uploaded by

dmovie020
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
4 views3 pages

Sorting Algorithms Explanation

The document provides an overview of various sorting algorithms, including Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Counting Sort, Radix Sort, and Bucket Sort, detailing their working principles and time complexities. Each algorithm is summarized with its best, average, and worst-case time complexities, as well as space complexity and stability. A summary table consolidates this information for quick reference.

Uploaded by

dmovie020
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 - Explanation & Time Complexity

1. Bubble Sort

Working:

- Repeatedly compares and swaps adjacent elements.

- Largest values 'bubble' to the end.

Time Complexity:

- Best: O(n)

- Average/Worst: O(n²)

- Space: O(1)

2. Selection Sort

Working:

- Selects the minimum element from unsorted part and swaps it with the current element.

Time Complexity:

- Best/Average/Worst: O(n²)

- Space: O(1)

3. Insertion Sort

Working:

- Builds the sorted array by inserting elements in the correct position.

Time Complexity:

- Best: O(n)

- Average/Worst: O(n²)

- Space: O(1)

4. Merge Sort

Working:
Sorting Algorithms - Explanation & Time Complexity

- Divides array into halves, recursively sorts and merges them.

Time Complexity:

- Best/Average/Worst: O(n log n)

- Space: O(n)

5. Quick Sort

Working:

- Chooses a pivot, partitions array, and recursively sorts subarrays.

Time Complexity:

- Best/Average: O(n log n)

- Worst: O(n²)

- Space: O(log n)

6. Heap Sort

Working:

- Builds a max heap, swaps root with last, and heapifies.

Time Complexity:

- Best/Average/Worst: O(n log n)

- Space: O(1)

7. Counting Sort

Working:

- Counts occurrences of elements and calculates positions directly.

Time Complexity:

- Best/Average/Worst: O(n + k)

- Space: O(k)
Sorting Algorithms - Explanation & Time Complexity

8. Radix Sort

Working:

- Sorts numbers digit by digit using counting sort.

Time Complexity:

- Best/Average/Worst: O(nk)

- Space: O(n + k)

9. Bucket Sort

Working:

- Divides array into buckets, sorts them individually, and concatenates.

Time Complexity:

- Best: O(n + k)

- Worst: O(n²)

- Space: O(n)

Summary Table

Algorithm | Best | Avg | Worst | Space | Stable

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

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

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

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

Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes

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

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

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

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

Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n) | Yes

You might also like