[go: up one dir, main page]
Scribd
Upload
7 views6 pages

Dsa 04

The document provides an overview of sorting and searching algorithms, highlighting their importance in data retrieval and analysis. It details several algorithms including Bubble Sort, Selection Sort, Merge Sort, Quick Sort, Linear Search, and Binary Search, along with their time and space complexities. The conclusion emphasizes the significance of these algorithms in efficient data handling and hints at future topics on advanced algorithms.

Uploaded by

22bph016
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
7 views6 pages

Dsa 04

The document provides an overview of sorting and searching algorithms, highlighting their importance in data retrieval and analysis. It details several algorithms including Bubble Sort, Selection Sort, Merge Sort, Quick Sort, Linear Search, and Binary Search, along with their time and space complexities. The conclusion emphasizes the significance of these algorithms in efficient data handling and hints at future topics on advanced algorithms.

Uploaded by

22bph016
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/ 6

Algorithms Part 1 - Sorting and Searching

Introduction to Algorithms
Algorithms are step-by-step procedures for performing tasks or solving problems. Sorting and
searching algorithms are fundamental for organizing and retrieving data efficiently.

Why Sorting and Searching?

●​ Improve data retrieval speed​

●​ Facilitate efficient data analysis​

●​ Essential in data processing​

Sorting Algorithms
Sorting is the process of arranging data in a specific order (ascending or descending).

Bubble Sort

Repeatedly swaps adjacent elements if they are in the wrong order.

●​ Time Complexity: O(n^2)​

●​ Space Complexity: O(1)​

Python Implementation:

def bubble_sort(arr):

n = len(arr)

for i in range(n):

for j in range(0, n-i-1):

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j]


Selection Sort

Selects the smallest element and swaps it with the current index.

●​ Time Complexity: O(n^2)​

●​ Space Complexity: O(1)​

Python Implementation:

def selection_sort(arr):

for i in range(len(arr)):

min_idx = i

for j in range(i+1, len(arr)):

if arr[j] < arr[min_idx]:

min_idx = j

arr[i], arr[min_idx] = arr[min_idx], arr[i]

Merge Sort

Divide and conquer algorithm that splits the array and merges sorted halves.

●​ Time Complexity: O(n log n)​

●​ Space Complexity: O(n)​

Python Implementation:

def merge_sort(arr):

if len(arr) > 1:

mid = len(arr) // 2

L = arr[:mid]
R = arr[mid:]

merge_sort(L)

merge_sort(R)

i=j=k=0

while i < len(L) and j < len(R):

if L[i] < R[j]:

arr[k] = L[i]

i += 1

else:

arr[k] = R[j]

j += 1

k += 1

Quick Sort

Divides the array around a pivot element.

●​ Time Complexity: O(n log n)​

●​ Space Complexity: O(log n)​

Python Implementation:

def quick_sort(arr):

if len(arr) <= 1:

return arr

pivot = arr[len(arr) // 2]

left = [x for x in arr if x < pivot]

middle = [x for x in arr if x == pivot]


right = [x for x in arr if x > pivot]

return quick_sort(left) + middle + quick_sort(right)

Searching Algorithms
Efficient searching techniques to find elements within a collection.

Linear Search

Checks each element sequentially.

●​ Time Complexity: O(n)​

●​ Space Complexity: O(1)​

Python Implementation:

def linear_search(arr, x):

for i in range(len(arr)):

if arr[i] == x:

return i

return -1

Binary Search

Efficiently finds an element in a sorted list by dividing the search interval in half.

●​ Time Complexity: O(log n)​

●​ Space Complexity: O(1)​

Python Implementation:

def binary_search(arr, x):


low, high = 0, len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == x:

return mid

elif arr[mid] < x:

low = mid + 1

else:

high = mid - 1

return -1

Comparison of Algorithms

Algorithm Best Worst Space


Case Case

Bubble Sort O(n) O(n^2) O(1)

Selection Sort O(n^2) O(n^2) O(1)

Merge Sort O(n log n) O(n log n) O(n)

Quick Sort O(n log n) O(n^2) O(log n)

Linear Search O(1) O(n) O(1)


Binary O(1) O(log n) O(1)
Search

Conclusion
Sorting and searching algorithms play a vital role in efficient data handling. The next part will
focus on advanced algorithms like dynamic programming and greedy methods.

You might also like