Scribd
Upload
14 views4 pages

Module 5

Module 5 covers sorting and searching algorithms. It details three sorting methods: Bubble Sort, Selection Sort, and Insertion Sort, all with a time complexity of O(n²), and two searching methods: Linear Search with O(n) and Binary Search with O(log n) time complexities. The document includes algorithms and code implementations for each method.

Uploaded by

yyashas008
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
14 views4 pages

Module 5

Module 5 covers sorting and searching algorithms. It details three sorting methods: Bubble Sort, Selection Sort, and Insertion Sort, all with a time complexity of O(n²), and two searching methods: Linear Search with O(n) and Binary Search with O(log n) time complexities. The document includes algorithms and code implementations for each method.

Uploaded by

yyashas008
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/ 4

Module 5: Sorting and Searching

1. Sorting

Sorting refers to the process of arranging elements in a particular order, usually ascending or
descending. It enhances data retrieval and processing efficiency.

1.1 Bubble Sort

Bubble Sort compares adjacent elements and swaps them if they are in the wrong order.

Algorithm:

• Compare a[i] and a[i+1]

• Swap if a[i] > a[i+1]

• Repeat for all elements

Code:

void bubbleSort(int a[], int n) {

for (int i = 0; i < n - 1; i++) {

for (int j = 0; j < n - i - 1; j++) {

if (a[j] > a[j + 1]) {

int temp = a[j];

a[j] = a[j + 1];

a[j + 1] = temp;

Time Complexity: O(n²)

1.2 Selection Sort

Selection Sort selects the smallest element from the unsorted part and swaps it with the first unsorted
element.

Code:

void selectionSort(int a[], int n) {

for (int i = 0; i < n - 1; i++) {


int min = i;

for (int j = i + 1; j < n; j++) {

if (a[j] < a[min]) min = j;

if (min != i) {

int temp = a[i];

a[i] = a[min];

a[min] = temp;

Time Complexity: O(n²)

1.3 Insertion Sort

Insertion Sort builds the final sorted array one element at a time by comparing and inserting into the
correct position.

Code:

void insertionSort(int a[], int n) {

for (int i = 1; i < n; i++) {

int key = a[i];

int j = i - 1;

while (j >= 0 && a[j] > key) {

a[j + 1] = a[j];

j--;

a[j + 1] = key;

Time Complexity: O(n²)

2. Searching

Searching refers to finding the location of a target element in a data structure.


2.1 Linear Search

In Linear Search, each element is checked sequentially.

Code:

int linearSearch(int a[], int n, int key) {

for (int i = 0; i < n; i++) {

if (a[i] == key)

return i;

return -1;

Time Complexity: O(n)

2.2 Binary Search

Binary Search works on sorted arrays. It repeatedly divides the search interval in half.

Algorithm:

• Compare key with middle element

• If equal, return index

• If less, search left subarray

• If greater, search right subarray

Code:

int binarySearch(int a[], int low, int high, int key) {

while (low <= high) {

int mid = (low + high) / 2;

if (a[mid] == key)

return mid;

else if (key < a[mid])

high = mid - 1;

else

low = mid + 1;

return -1;

}
Time Complexity: O(log n)

You might also like