Sorting and Searching

 

                                 Sorting in C 

Sorting means arranging data in a specific order — for numbers, it can be in ascending (small to large) or descending (large to small) order, and for alphabets, it can be in ascending (A to Z) or descending (Z to A) order.

1. Bubble Sort

2. Selection Sort

---

1. Bubble Sort

Theory

• Bubble Sort works by repeatedly comparing adjacent elements of the array.

• If two adjacent elements are in the wrong order, they are swapped.

• After the first pass, the largest element “bubbles up” to the end of the array.

• After each pass, one less comparison is needed because the last elements are already sorted.

---

⚙️ Algorithm (Step-by-Step Explanation)

Let’s assume the array has n elements: arr[0], arr[1], ..., arr[n-1]

Algorithm:

Step 1: Start
Step 2: Input the number of elements (n) and the array elements.
Step 3: Repeat steps 4–6 for i = 0 to n-2
Step 4:   Repeat for j = 0 to n-i-2
Step 5:      If arr[j] > arr[j+1]
                Swap arr[j] and arr[j+1]
Step 6:   End inner loop
Step 7: End outer loop
Step 8: Display the sorted array
Step 9: Stop

---

Example: Bubble Sort

Let’s take an example array:

A = [5, 3, 4, 1, 2]

---

Pass 1
Current array → [3, 4, 1, 2, 5]

---

Pass 2
Current array → [3, 1, 2, 4, 5]

---

Pass 3
Current array → [1, 2, 3, 4, 5]

---

Pass 4
Compare 1 and 2 → already in correct order 
No swaps needed.

---

[1, 2, 3, 4, 5]

We want to arrange these numbers in ascending order (small to large) using Bubble Sort.

We start from the beginning and compare each pair of numbers one by one.

1. Compare 5 and 3 → 5 is greater, so we swap them → [3, 5, 4, 1, 2]

2. Compare 5 and 4 → 5 is greater, swap → [3, 4, 5, 1, 2]

3. Compare 5 and 1 → 5 is greater, swap → [3, 4, 1, 5, 2]

4. Compare 5 and 2 → 5 is greater, swap → [3, 4, 1, 2, 5]

After Pass 1, the largest number (5) has moved to the end of the array.

Now we repeat the process for the remaining unsorted part [3, 4, 1, 2] (excluding the last number which is already sorted).

1. Compare 3 and 4 → already in order 

2. Compare 4 and 1 → 4 is greater, swap → [3, 1, 4, 2, 5]

3. Compare 4 and 2 → 4 is greater, swap → [3, 1, 2, 4, 5]

After Pass 2, the second largest number (4) is now in the second last position.

Now check the remaining [3, 1, 2].

1. Compare 3 and 1 → 3 is greater, swap → [1, 3, 2, 4, 5]

2. Compare 3 and 2 → 3 is greater, swap → [1, 2, 3, 4, 5]

 After Pass 3, 3 is in the correct position.

Now only [1, 2] left to check.

Final Sorted Array:

---

C Program for Bubble Sort

#include <stdio.h> 

int main() {
    int A[10];
    int x, y, t;

    printf("Enter 10  elements: ",);
    for(x = 0; x < 10; x++)
        scanf("%d", &A[x]);

    for(x = 0; x < 10-1; x++) {
        for(y = 0; y < 10-x-1; y++) {
            if(A[y] > A[y+1]) {
                t = A[y];
                A[y] = A[y+1];
                A[y+1] = t;
            }
        }
    }

    printf("Sorted array in ascending order:\n");
    for(x = 0; x < 10; x++)
        printf("%d ", A[x]);

    return 0;
}

---

2. Selection Sort

Theory

• In Selection Sort, we divide the list into two parts:

  • Sorted part (on the left)

  • Unsorted part (on the right)

• Each time, we find the smallest element in the unsorted part and swap it with the first element of the unsorted part.

• After every pass, the sorted part grows by one element.

---

⚙️ Algorithm (Step-by-Step Explanation)

Let array = arr[0], arr[1], ..., arr[n-1]

Algorithm:

Step 1: Start
Step 2: Input number of elements (n) and array elements.
Step 3: Repeat for i = 0 to n-2
Step 4:     min = i
Step 5:     Repeat for j = i+1 to n-1
Step 6:         If arr[j] < arr[min]
                    min = j
Step 7:     Swap arr[i] and arr[min]
Step 8: Display the sorted array
Step 9: Stop

---

Algorithm Explanation (Example)

Suppose the array = [5, 3, 4, 1, 2]

Pass	Smallest Element Selected	Array after pass
1	Smallest = 1 → Swap with 5	[1,3,4,5,2]
2	Smallest in remaining (2) → Swap with 3	[1,2,4,5,3]
3	Smallest in remaining (3) → Swap with 4	[1,2,3,5,4]
4	Smallest in remaining (4) → Swap with 5	[1,2,3,4,5]

 Final Sorted Array: 1, 2, 3, 4, 5

---

C Program for Selection Sort

#include <stdio.h>

int main() {
    int arr[100], n, i, j, min, temp;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements: ", n);
    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    for(i = 0; i < n-1; i++) {
        min = i;
        for(j = i+1; j < n; j++) {
            if(arr[j] < arr[min])
                min = j;
        }
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }

    printf("Sorted array in ascending order:\n");
    for(i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

---

Difference Between Bubble Sort and Selection Sort

Feature	Bubble Sort	Selection Sort
Working Principle	Compares and swaps adjacent elements repeatedly.	Finds minimum element and swaps with correct position.
Number of Swaps	Many swaps per pass.	Fewer swaps (only one per pass).
Efficiency	Less efficient on large data.	Slightly more efficient than Bubble Sort.
Time Complexity (Best/Worst)	O(n) / O(n²)	O(n²) for all cases.
Adaptive Nature	Adaptive (can detect if array is already sorted).	Non-Adaptive.
Stability	Stable (doesn’t change equal elements order).	Unstable (may change equal element order).
Example Usage	Small datasets or learning.	When swaps must be minimized.

---

                        Searching 

Searching is the process of finding the location (position or index) of a specific element (called a key) in a list or array.

There are mainly two types of searching methods in C:

1. Sequential (Linear) Search

2. Binary Search

1- Sequential Search (Linear Search)

Sequential Search (also called Linear Search) is the simplest searching technique. It checks each element of the array one by one until the desired element (key) is found. If the element is found, its position is returned; otherwise, the search ends after checking all elements.
Use Sequential Search when the list is unsorted or small in size.

---

 Algorithm (Step-by-Step Explanation)
arr[0], arr[1], ..., arr[n-1]
and we want to search for a value called key.
Step 2: Input number of elements n and the array elements.
Step 3: Input the element to search (key).
Step 4: Repeat for i = 0 to n–1
  If arr[i] == key, then
   Print “Element found at position i”
   Stop
Step 5: If loop ends, print “Element not found”
Step 6: Stop

---

 Example: Sequential Search
Search for key = 12
→ 15 ≠ 12
→ 25 ≠ 12
→ 30 ≠ 12
→ 12 = 12  (found at position 4)

---

 C Program for Sequential Search
#include <stdio.h>
int main() {
int A[10], n, i, e, found = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter array elements:\n");
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
printf("Enter element to search: ");
scanf("%d", &e);
for(i = 0; i < n; i++) {
if(A[i] == e) {
printf("Element found at position %d\n", i + 1);
break;
}
}
if(i==n)
printf("Element not found in the array.\n");
return 0;
}

---

                 2. Binary Search

Binary Search is a fast searching technique, but it works only when the array is sorted (either ascending or descending order). It repeatedly divides the search range into halves:

Compare the middle element with the key.
If key == middle → found 
If key < middle → search in the left half
If key > middle → search in the right half
Use Binary Search only on sorted arrays.

---

 Algorithm 
arr[0], arr[1], ..., arr[n-1]
and we want to search for value key.
Step 2: Input number of elements n and the sorted array.
Step 3: Input element to search (key).
Step 4: Set low = 0, high = n – 1
Step 5: Repeat while low <= high
  mid = (low + high) / 2
  If arr[mid] == key, print “Element found at position mid” and stop
  Else if arr[mid] < E, set low = mid + 1
  Else set high = mid – 1
Step 6: If not found, print “Element not found”
Step 7: Stop

---

 Example: Binary Search
Search E = 30
arr[mid] = 30 = E 

---

#include <stdio.h>
int main() {
    int A[10], n, e, l, h, m, found = 0;
 printf("Enter 10 elements in ascending order:\n");
    for(int i = 0; i < 10; i++)
        scanf("%d", &A[i]);
    printf("Enter element to search: ");
    scanf("%d", &e);
    l = 0;
    h = 10 - 1;
    while(l <= h) {
        m = (l + h) / 2;
        if(A[m] == e) {
            printf("Element found at position %d\n", m + 1);
            break;
        }
        else if(A[m] < e)
            l = m + 1;
        else
            h = m - 1;
    }
    if( l>h )
        printf("Element not found in the array.\n");
    return 0;
}

Each step cuts the search space in half → very fast compared to Sequential Search.

Important Point:

Let’s assume the array has n elements sorted in ascending order:

Algorithm:

Step 1: Start

Array = [10, 20, 30, 40, 50]

 low = 0, high = 4 → mid = 2

 Element 30 found at position 3.

Difference Between Sequential Search and Binary Search

Point	Sequential Search	Binary Search
Definition	Each element is checked one by one until the desired element is found.	The middle element is compared, and the search range is divided in half each time.
Array Condition	The array does not need to be sorted.	The array must be sorted.
Process	Check the first element, then the second, and so on until the element is found.	Take the middle element → compare → if smaller, search the left part; if larger, search the right part.
Efficiency	Less efficient (slow) — takes more time on large lists.	Highly efficient (fast) — works quickly on large lists.
Memory Requirement	Low	Slightly higher, because mid-value calculation is needed.
Algorithm Type	Simple, step-by-step search	Divide and Conquer method
Example	Searching a name one by one in a roll number list.