Sorting and Searching

Sudeshna Sarkar
7th Feb 2017
 Searching an Array:
Linear and Binary Search

Spring 2012 Programming and Data Structure 2

 Searching
Check if a given element (key) occurs in the
array.
Two methods to be discussed:
If the array elements are unsorted.
Linear search
If the array elements are sorted.
Binary search

Spring 2012 Programming and Data Structure 3

 Linear Search
Basic idea:
Start at the beginning of the array.
Inspect every element to see if it matches the key.
Time complexity:
A measure of how long an algorithm takes to run.
If there are n elements in the array:
Best case:
match found in first element (1 search operation)
Worst case:
no match found, or match found in the last element (n
search operations)
Average: (n + 1) / 2 search operations

Spring 2012 Programming and Data Structure 4

 Linear search
/* If key appears in a[0..size-1], return its location, pos, s.t.
a[pos] == key. If key is not found, return -1 */
int linear_search (int a[], int size, int key)
{
int pos = 0;
while ((pos < size) && (a[pos] != key))
pos++;
if (pos<n)
return pos; /* Return the position of match */
return -1} ; /* No match found */
}

Spring 2012 Programming and Data Structure 5

 Linear search: Recursive
/* If key appears in a[0..size-1], return its location, pos, s.t.
a[pos] == key. If key is not found, return -1 */
int rec_linear_search (int a[], int size, int key)
{
if (size == 0)
return -1;
if (a[size-1] == key))
return size-1;
return rec_linear_search (a, size-1, key) ;
}

Spring 2012 Programming and Data Structure 6

 Binary Search
Binary search works if the array is sorted.
Look for the target in the middle.
If you dont find it, you can ignore half of the
array, and repeat the process with the other half.
In every step, we reduce the number of
elements to search in by half.

Spring 2012 Programming and Data Structure 8

 The Basic Strategy
x[m]>key

no yes
0 n-1

x: Elements in ascending order

L m R

<=key >key
L R L R
Look at [(L+R)/2]. Move L or R to the middle
depending on test.
Repeat search operation in the reduced interval.
Spring 2012 Programming and Data Structure 9
 Contd.
/* If key appears in x[0..size-1], return its location, pos s.t. x[pos]==key.
If not found, return -1 */

int bin_search (int x[], int size, int key)

{
int L, R, mid;
_________________;
while ( ____________ )
{
__________________;
}
_________________ ;
}

Spring 2012 Programming and Data Structure 10

 The basic search iteration
/* If key appears in x[0..size-1], return its location, pos s.t. x[pos]==key. If not
found, return -1 */

int bin_search (int x[], int size, int key)

{
int L, R, mid;
_________________;
while ( ____________ )
{
mid = (L + R) / 2;
if (x[mid] > key)
R = mid;
else L = mid;
}
_________________ ;
}

Spring 2012 Programming and Data Structure 11

 Loop termination
/* If key appears in x[0..size-1], return its location, pos s.t. x[pos]==key. If not
found, return -1 */

int bin_search (int x[], int size, int key)

{
int L, R, mid;
_________________;
while ( L+1 != R )
{
mid = (L + R) / 2;
if (x[mid] <= key)
L = mid;
else R = mid;
}
_________________ ;
}

Spring 2012 Programming and Data Structure 12

 Return result
/* If key appears in x[0..size-1], return its location, pos s.t. x[pos]==key. If not
found, return -1 */

int bin_search (int x[], int size, int key)

{
int L, R, mid;
_________________;
while ( L+1 != R )
{
mid = (L + R) / 2;
if (x[mid] <= key)
L = mid;
else R = mid;
}
if (L >= 0 && x[L] = = key) return L;
else return -1;
}

Spring 2012 Programming and Data Structure 13

 Initialization
/* If key appears in x[0..size-1], return its location, pos s.t. x[pos]==key. If not
found, return -1 */

int bin_search (int x[], int size, int key)

{
int L, R, mid;
L = -1; R = size;
while ( L+1 != R )
{
mid = (L + R) / 2;
if (x[mid] <= key)
L = mid;
else R = mid;
}
if (L >= 0 && x[L] = = key) return L;
else return -1;
}

Spring 2012 Programming and Data Structure 14

 Binary Search Examples
Sorted array

-17 -5 3 6 12 21 45 63 50

Trace : L= -1; R= 9; x[4]=12;

binsearch (x, 9, 3); L= -1; R=4; x[1]= -5;
L= 1; R=4; x[2]=3;
binsearch (x, 9, 145); L=2; R=4; x[3]=6;
binsearch (x, 9, 45); L=2; R=3; return L;

We may modify the algorithm by checking equality with x[mid].

Spring 2012 Programming and Data Structure 15

 Is it worth the trouble ?
Suppose there are 1000 elements.
Ordinary search
If key is a member of x, it would require 500 comparisons on the average.
Binary search
after 1st compare, left with 500 elements.
after 2nd compare, left with 250 elements.
After at most 10 steps, you are done.

Spring 2012 Programming and Data Structure 16

 Recursive Binary Search
int rbSearch (int x[], int key, int first, int last) {
int midPoint;
if(first > last) // base case 1
return false;
else {
midPoint = (first + last)/2;
if (key < x[midPoint])
return rbSearch (x, key, first, midPoint-1);
else
if (key == x[midPoint]) // base case 2
return 1;
else
return rbSearch (x, key, midPoint+1, last);
}
}
 Recursive Binary Search
int rbSearch (int x[], int key, int first, int last) {
int midPoint;
if(first > last) // base case 1
return false;
midPoint = (first + last)/2;
if (key < x[midPoint])
return rbSearch (x, key, first, midPoint-1);
else
if (key == x[midPoint]) // base case 2
return 1;
else
return rbSearch (x, key, midPoint+1, last);
}
 Time Complexity
If there are n elements in the array.
Number of searches required:
log2n 2k= n,
For n = 64 (say). Where k is the number of steps.

Initially, list size = 64.

After first compare, list size = 32.
After second compare, list size = 16. log264 = 6
After third compare, list size = 8.
.
After sixth compare, list size = 1.
Spring 2012 Programming and Data Structure 19
 Sorting
Given an array x[0], x[1], ... , x[size-1]
reorder entries so that
x[0]<=x[1]<= . . . <=x[size-1]
 Sorting Problem
Input: A list of elements
Output: A list of elements in sorted (non-increasing/non-
decreasing) order
0 size-1
x: Unsorted list
Original list:
10, 30, 20, 80, 70, 10, 60, 40, 70
Sorted in non-decreasing order:
Sorted list 10, 10, 20, 30, 40, 60, 70, 70, 80
Sorted in non-increasing order:
80, 70, 70, 60, 40, 30, 20, 10, 10

Spring 2012 Programming and Data Structure 21

 Example
Swap

x: 3 12 -5 6 72 21 -7 45
Swap

x: -7 -5 3 6 12 21 72 45
x: -7 12 -5 6 72 21 3 45
Swap x: -7 -5 3 6 12 21 72 45
x: -7 -5 12 6 72 21 3 45
x: -7 -5 3 6 12 21 45 72
x: -7 -5 3 6 72 21 12 45

x: -7 -5 3 6 72 21 12 45
 Selection Sort
General situation :
0 k size-1
x: smallest elements, sorted remainder, unsorted

Steps :
Find smallest element, mval, in x[k..size-1]
Swap smallest element with x[k],
Increase k.

0 k mval size
x: smallest elements, sorted

swap
 Subproblem: Find smallest element
/* Yield location of smallest element in x[k .. size-1];*/
int min_loc (int x[ ], int k, int size)
int j, pos; /* x[pos] is the smallest element found so far */
pos = k;
for (j=k+1; j<size; j++)
if (x[i] < x[pos])
pos = j;
return pos;
}
 Selection Sort
/* Sort x[0..size-1] in non-decreasing int min_loc (int x[ ], int k, int size)
order */ int j, pos;
pos = k;
for (j=k+1; j<size; j++)
int selsort (int x[ ], int size) { if (x[i] < x[pos])
int k, m; pos = j;
for (k=0; k<size-1; k++) { return pos;
m = min_loc (x, k, size); }
temp = a[k];
a[k] = a[m];
a[m] = temp;
}
}
 Example
Swap for (k=0; k<size-1; k++) {
k pos
pos = k;
x: 3 12 -5 6 72 21 -7 45 for (j=k+1; j<size; j++) {
if (x[j] < x[pos])
Swap pos = j;
k pos
}
x: -7 12 -5 6 72 21 3 45 temp = x[k];
x[k] = x[pos];
Swap x[pos] = temp;
}
x: -7 -5 12 6 72 21 3 45
x: -7 -5 3 6 12 21 72 45
x: -7 -5 3 6 72 21 12 45
x: -7 -5 3 6 12 21 72 45
x: -7 -5 3 6 72 21 12 45
x: -7 -5 3 6 12 21 45 72
 Analysis
How many steps are needed to sort n things ?
Total number of steps proportional to n2
No. of comparisons?
(n-1)+(n-2)++1= n(n-1)/2

Of the order of n2

Worst Case? Best Case? Average Case?

Spring 2012 Programming and Data Structure 27

 Insertion Sort
General situation :
0 i size-1
x: smallest elements, sorted remainder, unsorted

i Compare and
Shift till x[i] is
larger.

j size-1
0

Spring 2012 Programming and Data Structure 28

 Insertion Sort
#define MAXN 100
void InsertSort (int list[MAXN], int size);
int main () {
int index, size;
int numbers[MAXN];
/* Get Input */
size = readarray (numbers) ;
printarray (numbers, size) ;
InsertSort (numbers, size) ;
printarray (numbers, size) ;
}
void InsertSort (int list[ ], int size) {
for (i=1; i<size; i++)
item = list[i] ;
for ( j=i-1; ( j >= 0)&& (list[ j ] > item); j--)
list[ j+1 ] = list[ j ];
list[j+1] = item ;
}
}
 Time Complexity
Number of comparisons and shifting:
o Worst Case?

1+2+3+ +(n-1) = n(n-1)/2

o Best Case?

1+1+ (n-1) times = (n-1)

Spring 2012 Programming and Data Structure 31

 Complete Insertion Sort
#include <stdio.h> /* Sort x[0..size-1] in non-decreasing order */
#define SIZE 100
int main ( ) {
int i, j, x[SIZE], size, temp;
printf("Enter the number of elements: ");
scanf("%d",&size);
printf("Enter the elements: ");
for(i=0;i<size;i++)
scanf("%d",&x[i]);
for (i=1; i<size; i++) {
temp = x[i] ;
for (j=i-1; (j>=0)&& (x[j] > temp); j--)
x[j+1] = x[j];
x[j+1] = temp ;
}
for(i=0;i<size;i++) /* print the sorted (non-decreasing) list */
printf("%d ",x[i]);
return 0;
}
 Insertion Sort Example
for (i=1; i<size; i++) {
temp = x[i] ;
for (j=i-1; (j>=0)&& (x[j] > temp); j--)
Input: x[j+1] = x[j];
3 12 -5 6 72 21 -7 45 x[j+1] = temp ;
3 12 -5 6 72 21 -7 45 }
-5 3 12 6 72 21 -7 45 -5 3 6 12 21 72 -7 45
-5 3 6 12 72 21 -7 45 -7
-5 3 6 12 72 21 -7 45 -5 3 6 12 21 72 __ 45
-5 3 6 12 21 72 -7 45 -5 3 6 12 21 __ 72 45
-5 3 6 12 __ 21 72 45
-7 -5 3 6 12 21 72 45
-5 3 6 __ 12 21 72 45
-7 -5 3 6 12 21 45 72 -5 3 __ 6 12 21 72 45
Output: -5 __ 3 6 12 21 72 45
__ -5 3 6 12 21 72 45
-7 -5 3 6 12 21 72 45
END