[go: up one dir, main page]
Scribd
Upload
3 views3 pages

Discrete Structures

The document provides a detailed report on sorting algorithms, specifically Bubble Sort and Insertion Sort. It explains their definitions, working principles, examples, time and space complexities, as well as their pros and cons. Both algorithms are comparison-based and have quadratic time complexity in average and worst cases, making them inefficient for large datasets.

Uploaded by

bsce24008
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as RTF, PDF, TXT or read online on Scribd
3 views3 pages

Discrete Structures

The document provides a detailed report on sorting algorithms, specifically Bubble Sort and Insertion Sort. It explains their definitions, working principles, examples, time and space complexities, as well as their pros and cons. Both algorithms are comparison-based and have quadratic time complexity in average and worst cases, making them inefficient for large datasets.

Uploaded by

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

Ayesha Khalid BSCE-24008

DISCRETE STRUCTURES

📘 Sorting Algorithms: Detailed Report

🔷 Introduction to Sorting

Sorting is the process of arranging data in a particular order—ascending or descending. It is a


fundamental operation used in searching, data analysis, and optimization.

Two basic sorting algorithms are:

Bubble Sort

Insertion Sort

🔶 1. Bubble Sort

📌 Definition:

Bubble Sort is a comparison-based sorting algorithm in which each pair of adjacent elements is
compared and swapped if they are in the wrong order. This process is repeated until the array is sorted.

🧠 Working Principle:

Starts at the beginning of the list.

Compares each pair of adjacent elements.

Swaps them if the first is greater than the second.

After each pass, the largest unsorted element "bubbles up" to its correct position.

🔁 Example:

Given array: [5, 1, 4, 2, 8]

Pass 1:

Compare 5 and 1 → Swap → [1, 5, 4, 2, 8]

Compare 5 and 4 → Swap → [1, 4, 5, 2, 8]


Compare 5 and 2 → Swap → [1, 4, 2, 5, 8]

Compare 5 and 8 → No swap

Pass 2:

Compare 1 and 4 → No swap

Compare 4 and 2 → Swap → [1, 2, 4, 5, 8]

Remaining elements are already sorted

... and so on.

Time Complexity:

Case Time Complexity

Best Case (Sorted) O(n)

Average Case O(n²)

Worst Case (Reversed) O(n²)

🧮 Space Complexity:

O(1) (In-place sorting)

✅ Pros:

Simple to implement.

Easy to understand.

❌ Cons:

Inefficient for large datasets.

High number of swaps and comparisons.

🔶 2. Insertion Sort

📌 Definition:

Insertion Sort is a comparison-based sorting algorithm that builds the final sorted array one element at a
time. It is much like sorting playing cards in your hands.

🧠 Working Principle:

Starts with the second element.


Compares it with the first element and inserts it at the correct position.

Repeats this for all remaining elements.

🔁 Example:

Given array: [5, 1, 4, 2, 8]

Step 1: 1 is compared with 5 → Insert before 5 → [1, 5, 4, 2, 8]

Step 2: 4 is compared with 5 → Insert before 5 → [1, 4, 5, 2, 8]

Step 3: 2 is compared and inserted → [1, 2, 4, 5, 8]

Step 4: 8 already in correct place

Time Complexity:

Case Time Complexity

Best Case (Sorted) O(n)

Average Case O(n²)

Worst Case (Reversed) O(n²)

🧮 Space Complexity:

O(1) (In-place sorting)

✅ Pros:

Simple to implement.

Efficient for small data sets or nearly sorted data.

Fewer swaps compared to Bubble Sort.

❌ Cons:

Not efficient for large datasets.

Still has quadratic time complexity in the average and worst case.

You might also like