[go: up one dir, main page]
Scribd
Upload
10 views2 pages

Exp 9

Uploaded by

Ansh Dabholkar
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
10 views2 pages

Exp 9

Uploaded by

Ansh Dabholkar
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

EXPERIMENT NO 09

AIM: Write a C Program to Implement sorting algorithms - bubble, merge, quick.

Software / Language: C

Description:

Sorting is one of the most fundamental algorithms in computer science, used to arrange the elements of a
list in a specific order, typically ascending or descending. Different sorting algorithms have different time and
space complexities, making them suitable for various scenarios. In this theory, we'll explore three widely
used sorting algorithms: Bubble Sort, Merge Sort, and Quick Sort, and provide a C program for each.

1. Bubble Sort

Overview:

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares
adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is
sorted.

Steps:

1. Start at the beginning of the list.

2. Compare each pair of adjacent elements.

3. Swap them if they are in the wrong order.

4. Continue the process until no more swaps are needed.

Time Complexity:

• Best Case (Already Sorted): O(n)

• Worst and Average Case: O(n²)

2. Merge Sort

Overview:

Merge Sort is a divide-and-conquer algorithm. It divides the input array into two halves, recursively sorts
each half, and then merges the sorted halves back together. It ensures that the result is a sorted array.

Steps:

1. Divide the array into two halves.

2. Recursively sort the two halves.

3. Merge the two sorted halves into a single sorted array.

Time Complexity:

• Best, Worst, and Average Case: O(n log n)


3. Quick Sort

Overview:

Quick Sort is another divide-and-conquer algorithm. It picks a pivot element and partitions the array around
the pivot, ensuring that elements on the left are smaller than the pivot and elements on the right are greater.
This process is repeated recursively for the left and right sub-arrays.

Steps:

1. Choose a pivot element.

2. Partition the array such that elements smaller than the pivot are on the left, and elements greater are on the
right.

3. Recursively apply the above steps to the left and right sub-arrays.

Time Complexity:

• Best and Average Case: O(n log n)

• Worst Case (when the array is already sorted or nearly sorted): O(n²)

Conclusion:

• Bubble Sort is a simple and easy-to-implement algorithm, but it is inefficient for large datasets due to its
O(n²) time complexity.
• Merge Sort is more efficient, with a time complexity of O(n log n) for all cases, making it a stable and
reliable option for large datasets.
• Quick Sort is usually the fastest among the three, with an average time complexity of O(n log n), but it
can degrade to O(n²) in the worst case. However, it is highly efficient in practice with good pivot
selection.

Result:

Upon executing the C program that implements the sorting algorithms Bubble Sort, Merge Sort, and Quick
Sort, the result will display the input array in its sorted order for each algorithm. Each algorithm correctly
sorts the array by rearranging the elements in ascending order.

Each algorithm will process the array differently based on its specific logic, but the final sorted result will be
the same.

You might also like