Sorting and Searching

Bubble sort
 Bubble sort, sometimes referred as sinking sort.
 It is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted,
comparing each pair of adjacent items and swapping them if they are in the wrong order.

The pass through the list is repeated until no swaps are needed, which indicates that the list is
 sorted.
 The algorithm gets its name from the way smaller elements "bubble" to the top of the list.
 As it only uses comparisons to operate on elements, it is a comparison sort.
Although the algorithm is simple, it is too slow for practical use, even compared to insertion sort.

Algorithm
for i ← 1 to n do
for j ← 1 to n-i do
If Array[j] > Array[j+1] then /* For decreasing order use < */
temp ← Array[j]
Array[j] ← A [j+1]
Array[j+1] ← temp

Program
#include <stdio.h>
void main()
{
int array[100], n, i, j, temp;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (i = 0; I < n; i++)
{
scanf("%d", &array[i]);
}
for (i = 0 ;i< ( n - 1 );i++)
{
for (j = 0 ; j< n - c - 1; j++)
{
if (array[j] > array[j+1]) /* For decreasing order use < */
{
2130702 – Data Structure 1
 Sorting and Searching

temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
printf("Sorted list in ascending order:\n");
for (i = 0 ;i< n ;i++ )
{
printf("%d\n", array[i]);
}
getch();
}

Example
Consider an array A of 5 element

A[0] 45

A[1] 34

A[2] 56

A[3] 23

A[4] 12

Pass-1: The comparisons for pass-1 are as follows.

Compare A[0] and A[1]. Since 45>34, interchange them.

Compare A[1] and A[2]. Since 45<56, no interchange.

Compare A[2] and A[3]. Since 56>23, interchange them.

Compare A[3] and A[4]. Since 56>12 interchange them.

At the end of first pass the largest element of the array, 56, is bubbled up to the last position in the
array as shown.

2130702 – Data Structure 2

 Sorting and Searching

45 34 34 34 34

34 45 45 45 45

56 56 56 23 23

23 23 23 56 12

12 12 12 12 56 Largest element

Pass-2: The comparisons for pass-2 are as follows.

Compare A[0] and A[1]. Since 34<45, no interchange.

Compare A[1] and A[2]. Since 45>23, interchange them.

Compare A[2] and A[3]. Since 45>12, interchange them.

34 34 34 34

45 45 23 23

23 23 45 12

12 12 12 45 Second Largest element

55 56 56 56

Pass-3: The comparisons for pass-3 are as follows.

Compare A[0] and A[1]. Since 34>23, interchange them.

Compare A[1] and A[2]. Since 34>12, interchange them.

34 23 23

23 34 12

12 12 34 Third Largest element

45 45 45

56 56 56

2130702 – Data Structure 3

 Sorting and Searching

Pass-4: The comparisons for pass-4 are as follows.

Compare A[0] and A[1]. Since 23>12, interchange them.

23 12

12 23

34
Sorted Array
34

45 45

56 56

2130702 – Data Structure 4

 Sorting and Searching

Selection Sort
 The idea of algorithm is quite simple.
 Array is imaginary divided into two parts - sorted one and unsorted one.
 At the beginning, sorted part is empty, while unsorted one contains whole array.
 At every step, algorithm finds minimal element in the unsorted part and adds it to the end of the sorted one.
 When unsorted part becomes empty, algorithm stops.

Algorithm
SELECTION_SORT (A)
for i ← 1 to n-1 do
min ← i;
for j ← i + 1 to n do
If A[j] < A[i] then
min ← j
If min!=i then
temp ← A[i]
A[i] ← A [min]
A[min] ← temp

Program
#include <stdio.h>
void main()
{
int array[100], n, i, j, min, temp;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for ( i = 0 ; i < n ; i++ )
{
scanf("%d", &array[i]);
}
for ( i = 0 ; i < ( n - 1 ) ; i++ )
{
min = i;
for ( j = i + 1 ; j < n ; j++ )
{
if ( array[min] > array[j] )
min = j;
}
5
 Sorting and Searching

if ( min != i )
{
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
printf("Sorted list in ascending order:\n");
for ( i = 0 ; i < n ; i++ )
{
printf("%d\n", array[i]);
}
getch();
}

2130702 – Data Structure 6

 Sorting and Searching

Example
Unsorted Array
Step – 1: 5 1 12 -5 16 2 12 14

Step – 2: 5 1 12 -5 16 2 12 14 Exchange 5 and -5

Sorted Sub Array Unsorted Sub Array

Step – 3: -5 1 12 5 16 2 12 14 No Exchange

Sorted Sub Array Unsorted Sub Array

-5 1 12 5 16 2 12 14 Exchange 12 and 2
Step – 4:

Sorted Sub Array Unsorted Sub Array

Step – 5: -5 1 2 5 16 12 12 14 No Exchange

Sorted Sub Array Unsorted Sub Array

-5 1 2 5 16 12 12 14 Exchange 16 and 12
Step – 6:

Sorted Sub Array Unsorted Sub Array

-5 1 2 5 12 16 12 14 Exchange 16 and 12
Step – 7:

Sorted Sub Array Unsorted Sub Array

Step – 8: -5 1 2 5 12 12 16 14 Exchange 16 and 14

Sorted Sub Array

Step – 9: -5 1 2 5 12 12 14 16 End of the Array

2130702 – Data Structure 7

 Sorting and Searching

Linear/Sequential Search
 In computer science, linear search or sequential search is a method for finding a particular value in a list that
consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.
 Linear search is the simplest search algorithm.
 It is a special case of brute-force search. Its worst case cost is proportional to the number of elements in the
list.

Algorithm
# Input: Array A, integer key
# Output: first index of key in A,
# or -1 if not found

Algorith: Linear_Search
for i = 0 to last index of A:
if A[i] equals key:
return i
return -1

Program
#include <stdio.h>
void main()
{
int array[100], key, i, n;

printf("Enter the number of elements in array\n");

scanf("%d",&n);

printf("Enter %d integer(s)\n", n);

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

{
printf("Array[%d]=", i);
scanf("%d", &array[i]);
}

printf("Enter the number to search\n");

scanf("%d", &key);

| 2130702 – Data Structure 16

 Sorting and Searching

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

{
if (array[i] == key) /* if required element found */
{
printf("%d is present at location %d.\n", key, i+1);
break;
}
}
if (i == n)
{
printf("%d is not present in array.\n", search);
}
getch();
}

Example

Search for 1 in given array: 2 9 3 1 8

th
Comparing value of i index with element to be search one
by one until we get seache element or end of the array

(a) 2 9 3 1 8

(b) 2 9 3 1 8

(c) 2 9 3 1 8

(d) 2 9 3 1 8 Element found at ith index

2130702 – Data Structure 17

 Sorting and Searching

Binary Search
 If we have an array that is sorted, we can use a much more efficient algorithm called a Binary Search. In binary
 search each time we divide array into two equal half and compare middle element with search element.
 If middle element is equal to search element then we got that element and return that index otherwise if
middle element is less than search element we look right part of array and if middle element is greater than
search element we look left part of array.

Algorithm
# Input: Sorted Array A, integer key
# Output: first index of key in A, or -1 if not found

Algorith: Binary_Search (A, left, right)

while left <= right
middle = index halfway between left, right
if D[middle] matches key
return middle
else if key less than A[middle]
right = middle -1
else
left = middle + 1
return -1

Program
#include <stdio.h>
void main()
{
int i, first, last, middle, n, key, array[100];

printf("Enter number of elements\n");

scanf("%d",&n);
printf("Enter %d integers in sorted order\n", n);
for ( i = 0 ; i < n ; i++ )
{
scanf("%d",&array[i]);
}
printf("Enter value to find\n");
scanf("%d",&key);
2130702 – Data Structure 18
 Sorting and Searching

first = 0;
last = n - 1;
middle = (first+last)/2;

while( first <= last )

{
if (array[middle] == key)
{
printf("%d found at location %d.\n", key, middle+1);
break;
}
else if ( array[middle]>key )
{
Last=middle - 1;
}
else
first = middle + 1;

middle = (first + last)/2;

}
if ( first > last )
{
printf("Not found! %d is not present in the list.\n", key);
}
getch();
}

Example

Find 6 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.

Step 1 --> (middle element is 19 > 6): Search in left part

-1 5 6 18 19 25 46 78 102 114
Step 2 --> (middle element is 5 < 6): Search in Right part
-1 5 6 18
Step 3 --> (middle element is 6 == 6): Element Found
6 18

2130702 – Data Structure 19