Scribd
Upload
4 views2 pages

Sorting Notes All

The document provides definitions and complexities for five sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort. Bubble Sort has a best time complexity of O(n) and worst of O(n^2), while Selection and Insertion Sort both have O(n^2) complexities. Merge Sort and Quick Sort are more efficient with O(n log n) average complexities, though Quick Sort can degrade to O(n^2) in the worst case.

Uploaded by

g7055282
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 views2 pages

Sorting Notes All

The document provides definitions and complexities for five sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort. Bubble Sort has a best time complexity of O(n) and worst of O(n^2), while Selection and Insertion Sort both have O(n^2) complexities. Merge Sort and Quick Sort are more efficient with O(n log n) average complexities, though Quick Sort can degrade to O(n^2) in the worst case.

Uploaded by

g7055282
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

Bubble Sort

Definition:
Bubble Sort compares adjacent elements and swaps them if they are in wrong order.

Time Complexity:
Best: O(n)
Worst: O(n^2)
Average: O(n^2)

Space Complexity:
O(1)

Selection Sort
Definition:
Selection Sort finds the minimum element and places it at the beginning in every iteration.

Time Complexity:
Best: O(n^2)
Worst: O(n^2)
Average: O(n^2)

Space Complexity:
O(1)

Insertion Sort
Definition:
Insertion Sort inserts each element into its correct position in the sorted left side.

Time Complexity:
Best: O(n)
Worst: O(n^2)
Average: O(n^2)

Space Complexity:
O(1)

Merge Sort
Definition:
Merge Sort is a divide and conquer algorithm, splitting array in half, sorting them, then merging.

Time Complexity:
Best: O(n log n)
Worst: O(n log n)
Average: O(n log n)

Space Complexity:
O(n)

Quick Sort
Definition:
Quick Sort picks a pivot element and partitions the array around pivot recursively.

Time Complexity:
Best: O(n log n)
Worst: O(n^2)
Average: O(n log n)

Space Complexity:
O(log n)

You might also like