Scribd
Upload
8 views2 pages

Sorting Algorithms

The document outlines the time and space complexities of various sorting algorithms including Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Counting Sort, Radix Sort, Bucket Sort, and Shell Sort. Each algorithm is presented with its best, worst, and average case time complexities, along with space complexities. The information serves as a comparative reference for understanding the efficiency of different sorting methods.

Uploaded by

Arijit Chakrabarty
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
8 views2 pages

Sorting Algorithms

The document outlines the time and space complexities of various sorting algorithms including Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Counting Sort, Radix Sort, Bucket Sort, and Shell Sort. Each algorithm is presented with its best, worst, and average case time complexities, along with space complexities. The information serves as a comparative reference for understanding the efficiency of different sorting methods.

Uploaded by

Arijit Chakrabarty
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/ 2

1.

Bubble Sort

● Best Case: O(n)O(n)O(n)


● Worst Case: O(n2)O(n^2)O(n2)
● Average Case: O(n2)O(n^2)O(n2)
● Space Complexity: O(1)O(1)O(1)

2. Selection Sort

● Best Case: O(n2)O(n^2)O(n2)


● Worst Case: O(n2)O(n^2)O(n2)
● Average Case: O(n2)O(n^2)O(n2)
● Space Complexity: O(1)O(1)O(1)

3. Insertion Sort

● Best Case: O(n)O(n)O(n)


● Worst Case: O(n2)O(n^2)O(n2)
● Average Case: O(n2)O(n^2)O(n2)
● Space Complexity: O(1)O(1)O(1)

4. Merge Sort

● Best Case: O(nlog⁡n)O(n \log n)O(nlogn)


● Worst Case: O(nlog⁡n)O(n \log n)O(nlogn)
● Average Case: O(nlog⁡n)O(n \log n)O(nlogn)
● Space Complexity: O(n)O(n)O(n)

5. Quick Sort

● Best Case: O(nlog⁡n)O(n \log n)O(nlogn)


● Worst Case: O(n2)O(n^2)O(n2)
● Average Case: O(nlog⁡n)O(n \log n)O(nlogn)
● Space Complexity: O(log⁡n)O(\log n)O(logn) (for recursive stack space)

6. Heap Sort

● Best Case: O(nlog⁡n)O(n \log n)O(nlogn)


● Worst Case: O(nlog⁡n)O(n \log n)O(nlogn)
● Average Case: O(nlog⁡n)O(n \log n)O(nlogn)
● Space Complexity: O(1)O(1)O(1)

7. Counting Sort
● Best Case: O(n+k)O(n + k)O(n+k)
● Worst Case: O(n+k)O(n + k)O(n+k)
● Average Case: O(n+k)O(n + k)O(n+k)
● Space Complexity: O(k)O(k)O(k) (where kkk is the range of the input)

8. Radix Sort

● Best Case: O(nk)O(nk)O(nk)


● Worst Case: O(nk)O(nk)O(nk)
● Average Case: O(nk)O(nk)O(nk)
● Space Complexity: O(n+k)O(n + k)O(n+k) (where kkk is the range of the input)

9. Bucket Sort

● Best Case: O(n+k)O(n + k)O(n+k)


● Worst Case: O(n2)O(n^2)O(n2)
● Average Case: O(n+k)O(n + k)O(n+k)
● Space Complexity: O(n+k)O(n + k)O(n+k) (where kkk is the number of buckets)

10. Shell Sort

● Best Case: O(nlog⁡n)O(n \log n)O(nlogn)


● Worst Case: O(n2)O(n^2)O(n2)
● Average Case: O(n3/2)O(n^{3/2})O(n3/2) (depending on gap sequence)
● Space Complexity: O(1)O(1)O(1)

You might also like