Searching and Sorting

• Searching and sorting are among the most

common operations performed
Searching and Sorting • Ex. databases
CSE 130: Introduction to Programming in C
Spring 2005 • It’s much easier to search data that has
been sorted

• Ex. searching a telephone directory

• Compare to a linear search
1 2

Pseudocode
Binary Search If (range contains only one element):

• Method: choose an element at random Look for desired value

(usually the middle) and decide whether to Else:
search the left or right half
1. Get midpoint of range
• Ex. Searching a dictionary for a word 2. Determine which half of range contains
• At each decision point, the space to be the value
searched is cut in half
3. Search that half of the range using binary
• Requires sorted data to work properly search
• Very efficient: requires log(n) comparisons
3 4

Binary Search Example if (first > last)

return -1; // value not in array

else

• Ex. Find 29
int mid = (first + last)/2;

if (value == A[mid])

• Start: [10, 13, 14, 29, 37] return mid;

• Examine 14: [10, 13] [14] [29, 37]

else if (value < A[mid])

BinarySearch(A, first, mid-1, value);

• Find 29: [10, 13, 14] [29] [37] else

BinarySearch(A, mid+1, last, value);

5 6
 Sorting Techniques Bubble Sort
• Many sorting techniques exist: quicksort, • Method: compare pairs of adjacent items,
radix sort, mergesort, bubblesort, insertion and swap them if they are “out of order”
sort, shell sort, selection sort, etc.
• At the end of each pass, the largest
• These techniques differ in efficiency remaining element is in its proper place

• Different sorting techniques take different • Elements “bubble” to their proper places
amounts of time to sort the same data
• This is a very easy algorithm to implement
• The rate of time increase also differs • It’s also very inefficient
7 8

Pseudocode Bubble Sort Example

Start: [29, 10, 14, 37, 13]
1. Repeat N-1 times: After 1st pass: [10, 14, 29, 13, 37]
A. Repeat N-1 times: After 2nd pass: [10, 14, 13, 29, 37]
1. if A[x] > A[x+1], swap them After 3rd pass: [10, 13, 14, 29, 37]
End: [10, 13, 14, 29, 37]

9 10

Bubble Sort Code Selection Sort

for (end = N - 1; end > 0; end--)
• Method: Search for the largest remaining
{ item, and put it in its proper sorted
for (loc = 0; loc < end - 1; loc++) position
{
• Ex. Looking at an entire hand of cards and
if (A[loc] > A[loc+1])
selecting one at a time
// Swap A[loc] and A[loc+1]

} • On each pass, swap the largest item with

the last (unsorted) element
}

11 12
 Pseudocode Selection Sort Example
Start: [29, 10, 14, 37, 13]
After 1st pass: [29, 10, 14, 13, 37]
1. Repeat N-1 times:
After 2nd pass: [13, 10, 14, 29, 37]
1. Find the largest (unsorted) element
After 3rd pass: [13, 10, 14, 29, 37]
2. Swap A[last] with A[largest]
After 4th pass: [10, 13, 14, 29, 37]
End: [10, 13, 14, 29, 37]

13 14

Selection Sort Code Selection Sort Code (2)

int indexOfLargest(int A[], int size)

int currIndex, indexSoFar = 0;

for (last = N-1; last >= 1; last--)
for (currIndex = 1; currIndex < size; currIndex++) {
{
int L = indexOfLargest(A, last+1);
if (A[currIndex] > A[indexSoFar]

indexSoFar = currIndex; // Swap A[L] and A[last]

} }
return indexSoFar;

15 16

Insertion Sort Pseudocode

• Method: select one element at a time and
insert it into its proper position 1. A[0] is sorted; A[1]-A[N-1] are unsorted

• Ex. arranging a hand of cards 2. Repeat N times:

• Begin by dividing the array into two regions: 1. nextItem = first unsorted element
sorted and unsorted
2. Shift sorted elements > nextItem over
• Initially, the sorted region is empty one position (A[x] = A[x-1])

• At each step, move first unsorted item into 3. Insert nextItem into correct position
its proper position in the sorted region

17 18
Insertion Sort Example Insertion Sort Code
• Start: [29 ][ 10, 14, 37, 13] int unsorted;
for (unsorted = 1; unsorted < N; unsorted++)

• Move 10: [10, 29 ][ 14, 37, 13] {

• Move 14: [10, 14, 29 ][ 37, 13] int nextItem = a[unsorted];

int loc;

• Move 37: [10, 14, 29, 37 ][ 13] for (loc = unsorted; (loc > 0) && (a[loc-1] > nextItem); loc--)

• Move 13: [10, 13, 14, 29, 37 ][ ] a[loc] = a[loc-1]; /* shift a[loc-1] to the right */

• End: [10, 13, 14, 29, 37]

a[loc] = nextItem; /*insert nextItem into sorted region */

19 20