Bubble sort and Selection Sort

Sorting in C – Notes

What is Sorting?

Sorting is the process of arranging data in ascending or descending order.
Sorting makes searching faster and helps organize data efficiently.

---

Bubble Sort Algorithm

Definition

Bubble Sort is a simple sorting algorithm that:

• Compares adjacent elements one by one

• Swaps them if they are in the wrong order

• Repeats until no swaps are needed

It is called bubble sort because smaller elements “bubble” to the top.

---

Working (Ascending Order)

1. Compare 1st and 2nd elements → swap if needed

2. Compare 2nd and 3rd → swap if needed

3. Continue till end of array

4. Repeat process n−1 times

5. Stop early if no swaps occur in a pass

Algorithm for Bubble Sort (Ascending Order)

1. Start

2. Read the number of elements n

3. Read the array elements

4. Repeat for i = 0 to n − 2

   • Set flag = 0 (to check if swapping happens)

   • For j = 0 to n − i − 2

     • If arr[j] > arr[j+1]

       • Swap arr[j] and arr[j+1]

       • Set flag = 1

   • If flag == 0, break (array already sorted)

5. Print the sorted array

6. Stop

Example Trace

Input array: [5, 3, 1, 7, 9]

Pass 1:
5↔3 → [3,5,1,7,9]
5↔1 → [3,1,5,7,9]

Pass 2:
3↔1 → [1,3,5,7,9]

Pass 3:
No swaps → Stop

Final result: [1,3,5,7,9]

---

Bubble Sort Function

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++)
        {
            if(arr[j] > arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

---

Bubble Sort with Flag Optimization

void bubbleSort(int arr[], int n)
{
    int i, j, temp, flag;

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

        if(flag == 0)
            break;
    }
}

---

Bubble Sort – Simple Program

#include <stdio.h>

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

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

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

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

    printf("The sorted array is\n");
    for(i=0;i<n;i++)
        printf("%d\n",arr[i]);
}

---

Selection Sort

Definition

Selection Sort works by:

• Dividing array into sorted and unsorted parts

• Finding the minimum element from unsorted part

• Swapping it with first unsorted element

Algorithm for Selection Sort (Ascending Order)

1. Start

2. Read the number of elements n

3. Read the array elements

4. For i = 0 to n − 2

   • Assume the current position is the minimum: min = i

   • For j = i + 1 to n − 1

     • If arr[j] < arr[min], then set min = j

   • If min ≠ i, swap arr[i] and arr[min]

5. Repeat until the array is sorted

6. Print the sorted array

7. Stop

---

Selection Sort Function

void selectionsort(int arr[], int n)
{
    int i, j, minidx, temp;

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

        for(j=i+1;j<n;j++)
            if(arr[j] < arr[minidx])
                minidx = j;

        if(minidx != i)
        {
            temp = arr[minidx];
            arr[minidx] = arr[i];
            arr[i] = temp;
        }
    }
}

---

Selection Sort – Simple Program

#include <stdio.h>

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

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

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

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

        if(minidx!=i)
        {
            temp = arr[minidx];
            arr[minidx] = arr[i];
            arr[i] = temp;
        }
    }

    printf("The sorted array is\n");
    for(i=0;i<n;i++)
        printf("%d\n",arr[i]);
}

---

Bubble Sort + Count Unique & Duplicate Numbers

#include <stdio.h>

void bubblesort(int arr[100], int n)
{
    int i,j,temp,flag,count,dup=0,uniq=0;

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

    for(i=0;i<n;i+=count)
    {
        count=1;
        for(j=i+1;j<n;j++)
            if(arr[i]==arr[j])
                count++;

        if(count>1) dup++;
        else uniq++;
    }

    printf("Number of unique elements=%d duplicate elements=%d\n",uniq,dup);
}

int main(void)
{
    int arr[100], n, i;

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

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

    bubblesort(arr,n);

    printf("The sorted array is\n");
    for(i=0;i<n;i++)
        printf("%d\n",arr[i]);
}

---

Sorting Strings Alphabetically (Using strcmp & strcpy)

#include <stdio.h>
#include <string.h>

int main()
{
    int i, j, n;
    char temp[100];
    char str[10][100];

    printf("Enter number of strings (max 10): ");
    scanf("%d", &n);

    printf("Enter %d strings:\n", n);
    for(i=0;i<n;i++)
        scanf("%s", str[i]);

    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(strcmp(str[i],str[j])>0)
            {
                strcpy(temp,str[i]);
                strcpy(str[i],str[j]);
                strcpy(str[j],temp);
            }
        }
    }

    printf("\nStrings in alphabetical order:\n");
    for(i=0;i<n;i++)
        printf("%s\n",str[i]);

    return 0;
}