[go: up one dir, main page]
Scribd
Upload
9 views4 pages

31 - Rohan - Gondhali - 4582355 - SYIT (A) Case Study 2.

The document provides an overview of three sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort, detailing their implementation processes. It compares their time and space complexities, noting that all have O(n²) time complexity in worst and average cases, but Insertion Sort performs better in practice, especially with nearly sorted data. Additionally, it highlights the stability of Bubble and Insertion Sort, while discussing the scenarios in which each algorithm may be preferred.

Uploaded by

Sandeep Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
9 views4 pages

31 - Rohan - Gondhali - 4582355 - SYIT (A) Case Study 2.

The document provides an overview of three sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort, detailing their implementation processes. It compares their time and space complexities, noting that all have O(n²) time complexity in worst and average cases, but Insertion Sort performs better in practice, especially with nearly sorted data. Additionally, it highlights the stability of Bubble and Insertion Sort, while discussing the scenarios in which each algorithm may be preferred.

Uploaded by

Sandeep Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

CASE STUDY

Implementation

Bubble Sort :-
Bubble Sort is the simplest sorting algorithm that works by repeatedly
swapping the adjacent elements if they are in the wrong order. This algorithm is
not suitable for large data sets as its average and worst-case time complexity are
quite high.
● We sort the array using multiple passes. After the first pass, the maximum
element goes to end (its correct position). Same way, after second pass,
the second largest element goes to second last position and so on.
● In every pass, we process only those elements that have already not
moved to correct position. After k passes, the largest k elements must
have been moved to the last k positions.
● In a pass, we consider remaining elements and compare all adjacent and
swap if larger element is before a smaller element. If we keep doing this,
we get the largest (among the remaining elements) at its correct position.

Selection Sort :-
Selection Sort is a comparison-based sorting algorithm. It sorts an array by
repeatedly selecting the smallest (or largest) element from the unsorted portion
and swapping it with the first unsorted element. This process continues until the
entire array is sorted.
● First we find the smallest element and swap it with the first element. This
way we get the smallest element at its correct position.
● Then we find the smallest among remaining elements (or second
smallest) and swap it with the second element.
● We keep doing this until we get all elements moved to correct position.
Insertion Sort :-
Insertion sort is a simple sorting algorithm that works by iteratively inserting
each element of an unsorted list into its correct position in a sorted portion of
the list. It is like sorting playing cards in your hands. You split the cards into
two groups: the sorted cards and the unsorted cards. Then, you pick a card from
the unsorted group and put it in the right place in the sorted group.
● We start with second element of the array as first element in the array is
assumed to be sorted.
● Compare second element with the first element and check if the second
element is smaller then swap them.
● Move to the third element and compare it with the first two elements and
put at its correct position
● Repeat until the entire array is sorted.

Time Complexity And Space Complexity

Bubble Sort:
1.Time complexity: O(n^2) in the worst and average cases, O(n) in the
best case (when the input array is already sorted)
2.Space complexity: O(1)
Selection Sort:
1.Time complexity: O(n^2) in all cases (worst, average, and best)
2.Space complexity: O(1)

Insertion Sort:
1.Time complexity: O(n^2) in the worst and average cases, O(n) in the
best case (when the input array is already sorted)
2.Space complexity: O(1)
Sorting Space
Algorithm Time Complexity Complexity

Best Average Worst


Worst Case
Case Case Case

Bubble Sort O(N) O(N2) O(N2) O(1)

Selection
O(N2) O(N2) O(N2) O(1)
Sort

Insertion
O(N) O(N2) O(N2) O(1)
Sort

Comparison

1. Bubble Sort, Selection Sort, and Insertion Sort all have the same worst-
case and average-case time complexity of O(n²). However, Insertion Sort
generally performs better in practice, especially on nearly sorted data, due
to fewer swaps and comparisons, making it more efficient in average
scenarios compared to Bubble Sort and Selection Sort.
2. Insertion Sort has the best-case time complexity of O(n) when the input
array is already sorted, which is not possible for Bubble Sort and
Selection Sort.
3. Selection Sort and Insertion Sort both have the same space complexity of
O(1), while Bubble Sort also has a space complexity of O(1).
4. Bubble Sort and Insertion Sort are stable sorting algorithms, meaning that
they preserve the relative order of equal elements in the sorted array,
while Selection Sort is not stable.
5. In terms of performance, Insertion Sort tends to perform better than
Bubble Sort and Selection Sort for small datasets, while Bubble Sort and
Selection Sort may perform better than Insertion Sort for larger datasets
or datasets that are partially sorted.
Overall, each algorithm has its own advantages and disadvantages, and
the choice of which algorithm to use depends on the specific
requirements of the problem at hand.

You might also like