Finding and ordering what is in the array
Linear search and selection sort are short enough to write from memory, and understanding them is what makes the faster algorithms in Unit V make sense.
After this lesson
You should be able to
- Write a linear search that reports the position or a clear 'not found'.
- Trace selection sort through one full pass.
- Swap two array elements correctly using a temporary.
Linear search, and how to report failure
Look at each element in turn and stop at the first match. The interesting design question is not the loop, it is what to return when the value is absent. Returning -1 works because it is not a valid subscript, so the caller can always tell the two cases apart.
Returning 0 for 'not found' would be a bug, because 0 is a perfectly good position — the first one. Choosing an impossible value as the failure signal is the general technique.
int index_of(const int data[], int n, int target)
{
for (int i = 0; i < n; i++)
if (data[i] == target)
return i; /* found: leave immediately */
return -1; /* impossible subscript = not found */
}Swapping needs a third variable
To exchange two values you cannot just assign one to the other — the first assignment overwrites the value you still need. Save it in a temporary first. This is three lines and every sorting algorithm depends on getting it right.
Write it once as a function and every sort in the rest of the course can use it.
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}Selection sort: find the smallest, put it in front
Scan the whole array for the smallest value and swap it into position 0. Then scan from position 1 for the smallest of what remains and swap it into position 1. Repeat. After each pass, one more element is in its final place.
The outer loop stops at n - 1, not n. When only one element is left it is already the largest, so a final pass would compare it with nothing. Understanding that is the difference between memorising the code and knowing it.
void selection_sort(int data[], int n)
{
for (int i = 0; i < n - 1; i++) {
int smallest = i;
for (int j = i + 1; j < n; j++)
if (data[j] < data[smallest])
smallest = j;
if (smallest != i)
swap(&data[i], &data[smallest]);
}
}Try it yourself
Sort an array of six marks in ascending order and then report the position of a mark the user asks for.
Need a hint?
Remember that sorting moves elements, so a position found before sorting is meaningless afterwards.
Check the worked solution
The order of operations matters: search after sorting, and report the position in the sorted array — searching first would give a position that sorting immediately invalidates. Printing 'not in the list' rather than -1 is the caller's job, which is exactly why index_of returns a signal instead of printing one.
#include <stdio.h>
#define SIZE 6
void swap(int *a, int *b);
void selection_sort(int data[], int n);
int index_of(const int data[], int n, int target);
int main(void)
{
int marks[SIZE] = {72, 45, 91, 38, 66, 45};
int target, pos;
selection_sort(marks, SIZE);
printf("Sorted: ");
for (int i = 0; i < SIZE; i++)
printf("%d ", marks[i]);
printf("\n");
printf("Search for: ");
scanf("%d", &target);
pos = index_of(marks, SIZE, target);
if (pos == -1)
printf("%d is not in the list\n", target);
else
printf("%d is at position %d\n", target, pos);
return 0;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void selection_sort(int data[], int n)
{
for (int i = 0; i < n - 1; i++) {
int smallest = i;
for (int j = i + 1; j < n; j++)
if (data[j] < data[smallest])
smallest = j;
if (smallest != i)
swap(&data[i], &data[smallest]);
}
}
int index_of(const int data[], int n, int target)
{
for (int i = 0; i < n; i++)
if (data[i] == target)
return i;
return -1;
}Quick check
Why does selection sort's outer loop run to n - 1 instead of n?
Why this lesson exists
Syllabus mapping
Searching and Sorting an Array · Array Arguments
Maps to course outcomes CO4, CO6.