MODULE 5 – Sorting And Searching

Sorting:

1)Bubble sort:

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent
elements, and swaps them if they are in the wrong order.
The biggest (or smallest) elements "bubble" to the end (or start) after each pass.

Example:

Let's sort this array in ascending order:

[5, 3, 8, 4, 2]

Step-by-Step:

Pass 1:

• Compare 5 and 3.
→ 5 > 3, so swap → [3, 5, 8, 4, 2]

• Compare 5 and 8.
→ 5 < 8, so no swap.

• Compare 8 and 4.
→ 8 > 4, so swap → [3, 5, 4, 8, 2]

• Compare 8 and 2.
→ 8 > 2, so swap → [3, 5, 4, 2, 8]

Pass 2:

• Compare 3 and 5.
→ 3 < 5, so no swap.

• Compare 5 and 4.
→ 5 > 4, so swap → [3, 4, 5, 2, 8]

• Compare 5 and 2.
→ 5 > 2, so swap → [3, 4, 2, 5, 8]

Pass 3:
 • Compare 3 and 4.
→ 3 < 4, so no swap.

• Compare 4 and 2.
→ 4 > 2, so swap → [3, 2, 4, 5, 8]
Pass 4:

• Compare 3 and 2.
→ 3 > 2, so swap → [2, 3, 4, 5, 8]

Final Sorted Array:

[2, 3, 4, 5, 8]

Program:

#include <stdio.h>

#define MAXSIZE 500

void bubblesort(int arr[], int n);

int main() {

int arr[MAXSIZE];

int n, i;

printf("\nHow many elements do you want to sort: ");

scanf("%d", &n);

printf("\nEnter the values one by one:\n");

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

printf("Enter element %d: ", i);

scanf("%d", &arr[i]);

}
printf("\nArray before sorting:\n");

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

printf("[%d] ", arr[i]);

bubblesort(arr, n);

printf("\nArray after sorting:\n");

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

printf("[%d] ", arr[i]);

printf("\n");

return 0;

void bubblesort(int arr[], int n) {

int i, j, temp;

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

for (j = 0; j < n - i - 1; j++) { // Correct logic for adjacent comparison

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

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

Selection Sort

Selection Sort is a simple sorting algorithm.

It selects the smallest (or largest) element from the unsorted part and swaps it with the element at
the beginning.

You divide the array into two parts:

 • Sorted part (grows from left to right)

• Unsorted part (shrinks)

Example:

Sort this array in ascending order:

[5, 3, 8, 4, 2]

Step-by-Step:

Pass 1:

• Find the smallest element from [5, 3, 8, 4, 2].

→ Smallest is 2.

• Swap 2 with the first element 5.

• Array becomes: [2, 3, 8, 4, 5]

Now, [2] is sorted.

Pass 2:

• Find the smallest element from [3, 8, 4, 5].

→ Smallest is 3.

• 3 is already at the correct position. No swap needed.

Now, [2, 3] is sorted.

Pass 3:

• Find the smallest element from [8, 4, 5].

→ Smallest is 4.

• Swap 4 with 8.

• Array becomes: [2, 3, 4, 8, 5]

Now, [2, 3, 4] is sorted.

Pass 4:

• Find the smallest element from [8, 5].

 → Smallest is 5.

• Swap 5 with 8.

• Array becomes: [2, 3, 4, 5, 8]

Now, [2, 3, 4, 5] is sorted.

Final Sorted Array:

[2, 3, 4, 5, 8]

Program:

#include <stdio.h>

#define MAXSIZE 500

void selection(int elements[], int array_size);

int main() {

int elements[MAXSIZE], maxsize, i;

printf("\nHow many elements you want to sort: ");

scanf("%d", &maxsize);

printf("\nEnter the values one by one:\n");

for (i = 0; i < maxsize; i++) {

printf("Enter element %d: ", i);

scanf("%d", &elements[i]);

printf("\nArray before sorting:\n");

for (i = 0; i < maxsize; i++)

printf("[%d] ", elements[i]);

printf("\n");
selection(elements, maxsize);

printf("\nArray after sorting:\n");

for (i = 0; i < maxsize; i++)

printf("[%d] ", elements[i]);

printf("\n");

return 0;

void selection(int elements[], int array_size) {

int i, j, min_idx, temp;

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

min_idx = i;

for (j = i + 1; j < array_size; j++) {

if (elements[j] < elements[min_idx])

min_idx = j;

// Swap elements[i] with elements[min_idx]

temp = elements[i];

elements[i] = elements[min_idx];

elements[min_idx] = temp;

Insertion Sort:

Insertion Sort builds the final sorted array one element at a time.
It takes one element, finds the correct place for it in the sorted part, and inserts it there.
Imagine sorting playing cards in your hand — you pick one card at a time and insert it at the correct
position.
Example:

Sort this array in ascending

order: [5, 3, 8, 4, 2]

Step-by-Step:

Pass 1: Insert 3

• Take 3.

• Compare with 5.
→ 3 < 5, so move 5 to the

right. • Insert 3 at the correct position.

• Array becomes: [3, 5, 8, 4, 2] [3, 5] is

sorted.

Pass 2: Insert 8

• Take 8.

• Compare with 5.
→ 8 > 5, so no shifting

needed. • Insert 8 after 5.

• Array remains: [3, 5, 8, 4, 2]

[3, 5, 8] is sorted.

Pass 3: Insert 4

• Take 4.

• Compare with 8.
→ 4 < 8 → move 8 right.

• Compare with 5.
 → 4 < 5 → move 5 right.

• Compare with 3.
→ 4 > 3 → stop.

• Insert 4 after 3.

• Array becomes: [3, 4, 5, 8, 2]

[3, 4, 5, 8] is sorted.

Pass 4: Insert 2

• Take 2.

• Compare with 8, 5, 4, and 3 — 2 is smaller than all! •

Move all those elements right.

• Insert 2 at the beginning.

• Array becomes: [2, 3, 4, 5, 8]

[2, 3, 4, 5, 8] is fully sorted!

Final Sorted Array:

[2, 3, 4, 5, 8]

Program:

#include <stdio.h>

#define MAXSIZE 500

void insertionsort(int elements[], int

maxsize); int elements[MAXSIZE], maxsize;

int main() {

int i;
printf("\nHow many elements you want to sort: ");

scanf("%d", &maxsize);

printf("\nEnter the values one by one:\n");

for (i = 0; i < maxsize; i++) {

printf("Enter element %i: ", i);

scanf("%d", &elements[i]);

printf("\nArray before sorting:\n");

for (i = 0; i < maxsize; i++)

printf("[%d] ", elements[i]);

printf("\n");

insertionsort(elements, maxsize);

printf("\nArray after sorting:\n");

for (i = 0; i < maxsize; i++)

printf("[%d] ", elements[i]);

printf("\n");

return 0;

void insertionsort(int elements[], int maxsize)

{ int i, j, index;

for (i = 1; i < maxsize; i++) {

index = elements[i];

j = i;
while (j > 0 && elements[j - 1] > index)

{ elements[j] = elements[j - 1]; j = j - 1;

elements[j] = index;

}
Searching:

Linear Search

Linear Search is the simplest way to find an element in a list or

array. You check each element one-by-one from the beginning

until: • You find the element (success), or

• You reach the end without finding it (fail).

Example:

Let's say you have this list:

[5, 3, 8, 4, 2]

You want to search for 4.

Step-by-Step:

1. Check index 0 → 5 ≠ 4 → Not a match.

2. Check index 1 → 3 ≠ 4 → Not a match.

3. Check index 2 → 8 ≠ 4 → Not a match.

4. Check index 3 → 4 == 4 → Found at index 3!

Done!

Another Example: (not found case)

Search for 9 in [5, 3, 8, 4, 2]:

1. 5 → no

2. 3 → no

3. 8 → no
 4. 4 → no

5. 2 → no

→ Reached the end without finding 9.

Program:

#include <stdio.h>

int linearSearch(int arr[], int size, int target)

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

if (arr[i] == target)

return i; // Return the index if found }

return -1; // Return -1 if not found

int main() {

int arr[] = {10, 20, 30, 40, 50};

int size = sizeof(arr) / sizeof(arr[0]);

int target;

printf("Enter the number to search: ");

scanf("%d", &target);

int result = linearSearch(arr, size, target);

if (result != -1)

printf("Element found at index %d\n", result);

else

printf("Element not found\n");

return 0;

}
Binary Search

Binary Search is a fast way to find an element in a sorted array.

It divides the array into halves and keeps searching in the half where the element could

be. • Compare the middle element with the target.

• If equal → Found!

• If target < middle → Search in the left half.

• If target > middle → Search in the right half.

• Keep repeating until you find it or the array is empty.

Important:
Array must be sorted first!

Example:

Sorted array:
[2, 3, 4, 5, 8]

Let's search for 5.

Step-by-Step:

1. Start:

o Left = 0 (value 2)

o Right = 4 (value 8)

o Middle = (0+4)//2 = 2 → value is 4

2. Compare:

o Target 5 > 4

o So, search right half.

o Update: Left = 3

3. Next Step:

o Left = 3 (value 5)

o Right = 4 (value 8)
 o Middle = (3+4)//2 = 3 → value is 5

4. Compare:

o Target 5 == 5
o Found at index 3!

Another Example (not found):

Search for 7:

1. Middle = 4 → value 4 → 7 > 4 → right half

2. Middle = 5 → value 8 → 7 < 8 → left half

3. No more elements → Not found.

Step Action

Find the middle Compare with the target If smaller Search

left If bigger Search right Repeat until found or array is

empty

Program:

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {

int low = 0, high = size - 1;

while (low <= high) {

int mid = (low + high) / 2;

if (arr[mid] == target)

return mid;

else if (arr[mid] < target)

low = mid + 1;

else
high = mid - 1;

}
return -1; // Not found

int main() {

int arr[] = {10, 20, 30, 40, 50, 60, 70}; // Must be sorted

int size = sizeof(arr) / sizeof(arr[0]);

int target;

printf("Enter the number to search: ");

scanf("%d", &target);

int result = binarySearch(arr, size, target);

if (result != -1)

printf("Element found at index %d\n", result);

else

printf("Element not found\n");

return 0;