Scribd
Upload
13 views2 pages

Quick Sort vs. Selection Sort Explained

The document explains Quick Sort and Selection Sort algorithms, highlighting Quick Sort as a Divide and Conquer algorithm that efficiently sorts arrays by partitioning around a pivot, while Selection Sort is a simpler comparison-based method that repeatedly selects the smallest element. Quick Sort has an average time complexity of O(n log n), whereas Selection Sort has a time complexity of O(n²) in all cases. The document also compares the two algorithms in terms of their characteristics and suitability for large data sets.

Uploaded by

robatakele2024
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
13 views2 pages

Quick Sort vs. Selection Sort Explained

The document explains Quick Sort and Selection Sort algorithms, highlighting Quick Sort as a Divide and Conquer algorithm that efficiently sorts arrays by partitioning around a pivot, while Selection Sort is a simpler comparison-based method that repeatedly selects the smallest element. Quick Sort has an average time complexity of O(n log n), whereas Selection Sort has a time complexity of O(n²) in all cases. The document also compares the two algorithms in terms of their characteristics and suitability for large data sets.

Uploaded by

robatakele2024
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

Design and Analysis of Algorithms

1. Explain quick sort and selection sort with example in divide and conquer
algorithm.

 QUICK SORT (Divide and Conquer Algorithm)

Quick Sort is an efficient sorting algorithm that follows the Divide and Conquer strategy.

Steps (Divide and Conquer Strategy):

1. Divide: Choose a "pivot" element from the array. Partition the array into two subarrays:
o Elements less than the pivot.
o Elements greater than the pivot.
2. Conquer: Recursively apply Quick Sort to the left and right subarrays.
3. Combine: Since the subarrays are sorted in-place, no work is needed to combine them.

Example:

Let’s sort the array: [10, 7, 8, 9, 1, 5]

1. Choose pivot (e.g., last element = 5)


2. Partition:
o Elements less than 5: [1]
o Pivot = 5
o Elements greater than 5: [10, 7, 8, 9]

Array becomes: [1, 5, 10, 7, 8, 9]

3. Recursively sort [1] (already sorted)


4. Recursively sort [10, 7, 8, 9]
o Pivot = 9
o Less: [7, 8], Greater: [10]
o Becomes: [7, 8, 9, 10]

Final sorted array: [1, 5, 7, 8, 9, 10]

Time Complexity:

 Best Case: O(n log n)


 Average Case: O(n log n)
 Worst Case: O(n²) (if pivot is always the smallest or largest)

1
Design and Analysis of Algorithms

 SELECTION SORT (NOT Divide and Conquer)

Selection Sort is a simple comparison-based algorithm. It repeatedly selects the smallest (or
largest) element from the unsorted part and moves it to the beginning.

Steps:

1. Find the smallest element in the unsorted array.


2. Swap it with the first unsorted element.
3. Move the boundary of the sorted part by one.
4. Repeat until all elements are sorted.

Example:

Array: [29, 10, 14, 37, 13]

1. Find min: 10 → Swap with 29 → [10, 29, 14, 37, 13]


2. Find min from [29, 14, 37, 13]: 13 → Swap with 29 → [10, 13, 14, 37, 29]
3. Next min in [14, 37, 29]: 14 → already in place
4. Next min in [37, 29]: 29 → Swap with 37 → [10, 13, 14, 29, 37]

Final sorted array: [10, 13, 14, 29, 37]

Time Complexity:

 Best Case: O(n²)


 Average Case: O(n²)
 Worst Case: O(n²)

Difference between Quick Sort and Selection Sort:

Feature Quick Sort Selection Sort


Algorithm Type Divide and Conquer Simple Sorting
Time Complexity O(n log n) average O(n²) always
In-Place Yes Yes
Recursion Used Yes No
Suitable For Large Data Yes No

You might also like