Workshop: Searching, Sorting, and Aggregating Arrays

UPI Study › Courses › Programming in C › Free lessons › Lesson 7.8 Free with a free account

Workshop: Searching, Sorting, and Aggregating Arrays

Programming in C · Chapter 7: Arrays, Strings, Input Validation, and Formatted OutputSection 7.8 · lesson 47 of 786 min · free with a free account

← Input Validation and Formatted Output in CNext lesson: Workshop: A Text Processing Utility →

Earn 3 college credits for Programming in CRecommended for credit by NCCRS · Computer Science 240 · self-paced · one payment, lifetime access
Enroll in Programming in C · $250 →Download the syllabus (PDF)

In this lesson

Linear search, bubble sort, and one-pass statistics on C arrays.

  • Write a linear search that returns the first matching index or -1
  • Implement bubble sort with a temporary variable for each swap
  • Compute the sum, average, lowest, and highest values in one loop
  • Avoid integer division by casting before computing an average

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (831 words). Read along, or search it.

Opening Question

Three Jobs for the High-Score Board

Starlight Arcade just got a screen for its high-score board. Players ask: is my 395 on there? The manager wants the scores sorted, best to worst. And the snack stand wants to know its average price. Three jobs, one tool: an array and a loop. In this workshop, you build all three as complete programs, one step at a time.

Linear Search Plan

Check Box After Box Until a Match

Program one: search the board. Plan first. The simplest search is linear search: look at the first box, then the next, until you find the value or run out of boxes. Searching for 395, four boxes are checked and rejected, the fifth matches, and the search stops. The last box is never looked at. The function should say where it found the value. Boxes start at zero, so not found can't be zero. It uses minus one, which is never a real index.

Worked Example

Return the Index or Minus One

Now the code. The loop walks the boxes. The return inside the loop ends the function the moment a match appears. Only after the loop finishes without a match does the function reach return minus one. The size comes in as count, because sizeof can't see it inside a function. Run it, and type 395. Found at index four. Sam tries to break it. Nine ninety-nine: not on the board, minus one. Three ten, the very first box: index zero. Both edges work.

Quick Check

A Score That Appears Twice

Quick check. This board holds a hundred fifty twice, in box one and box three. The same search looks for a hundred fifty. What index does it print? Pause and predict. One. The search checks box zero, then box one, finds a match, and returns at once. Box three is never looked at. Linear search reports the first match, not the last.

Bubble Sort Plan

Swap Wrong-Order Neighbors Each Pass

Program two: sort the high scores. Bubble sort repeats one small step: compare two neighbors, and swap them if they're in the wrong order. One walk along the array is a pass. Sorting biggest first, each pass carries the smallest remaining score to the end, like a bubble. That box is then finished, so each pass can stop one box earlier than the one before.

Worked Example

Watching the Array After Every Pass

The outer loop counts passes. The inner loop stops at n minus pass, one box earlier each time. A swap needs a spare box, temp. Without it, writing a i equals a i plus one would erase the old value, before you saved it. After each pass, the program prints the array, so you can watch the sort work. Run it. Pass one matches the plan. By pass three, the array is already in order, and passes four and five change nothing.

Common Mistake

Swapping Without a Spare Box

Now the common mistake: swapping with two assignments, and no spare box. Drop the temp line, and copy a i back directly. Then run it again. The scores are wrecked. After pass one, there are two 480s and two 395s, and 275 and 150 are gone. The first line had already destroyed the old a i, so both boxes ended up holding the same value. Always go through a third variable.

Aggregating

Sum, Average, Lowest, and Highest in One Pass

Program three: four answers from one pass over the snack prices. Keep four running values, and update them in the loop. The sum starts at zero. The lowest and the highest both start from the first price. The average comes after the loop: the sum divided by the count. In the loop, the sum always grows. The lowest and highest change only when a price beats them. Run it. Total twenty-eight ninety, average five seventy-eight, lowest two seventy-five, and highest twelve.

Quick Check

Starting the Lowest Price at Zero

Quick check. Priya's first try at the lowest price started the running value at zero, instead of the first price. The prices are four fifty, three twenty-five, and two seventy-five. What prints? Pause and predict. Lowest, zero. No real price is less than zero, so the test never passes, and lowest never changes. That's why the lowest and the highest start from the first price: it's a real value, so the comparison is fair.

Common Trap

Integer Division Drops the Fraction

One more trap hides in averages. Two whole numbers divide as whole numbers, losing the fraction, even when the answer goes into a float. Run it. Seven over two prints three point zero zero. The fix is to make one side a decimal first: cast total to float. Rebuild, and the average is three point five zero, the real answer.

Challenges

Three Ways to Extend the Programs

Back to the new board. Sam sorted a board that was already in order, and nothing moved. Boring, said Sam. Good, said Priya. Now try three challenges. Count the scores above a limit. Stop bubble sort early when a pass makes no swap. And write selection sort, then compare its passes.

Key Takeaways

Search, Sort, and Summarize

To recap. Linear search checks box after box, returns the first match's index, or minus one. Bubble sort swaps wrong-order neighbors through a spare box, and each pass finishes one more box. Sum, average, lowest and highest come from one pass, with lowest and highest starting at the first value. And make one side a float before you divide.

About Programming in C at UPI Study

Programming in C (Computer Science 240) is a self-paced online course of 78 video lessons in 11 chapters, from pseudocode and your first program to data types, decisions, loops, functions, arrays, strings, pointers, files, structures, dynamic memory and linked lists. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: C vs C++

Why take it here

Why students take Programming in C with UPI Study

How programs work close to the machineProgramming in C teaches how a program uses memory: variables and data types, control flow, functions, arrays and strings, pointers, files, structures and dynamic memory. C is the base for operating systems, embedded devices and many computer-science courses.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Programming in C carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Workshop: Searching, Sorting, and Aggregating Arrays

How does linear search work in C?
Linear search checks each element in order, starting at index 0, until it finds the target or runs out of elements. A typical function returns the index as soon as it finds a match and returns -1 after the loop if nothing matched, since -1 is never a valid index. Because it stops at the first match, a value stored twice is reported at its lower index.
How does bubble sort work?
Bubble sort repeatedly compares neighboring elements and swaps them when they are in the wrong order. Each walk along the array is a pass, and each pass carries the most extreme remaining value to the end, so the next pass can stop one element earlier. For n elements, at most n - 1 passes are needed, and a pass that makes no swaps means the array is already sorted.
Why do you need a temp variable to swap two values in C?
Without one, the first assignment destroys a value. If you write a[i] = a[i+1]; and then a[i+1] = a[i];, the first line has already overwritten the old a[i], so both elements end up holding the same value. A third variable saves it: temp = a[i]; a[i] = a[i+1]; a[i+1] = temp;. A sort that skips temp duplicates some values and loses others.
How do you find the minimum, maximum, and average of an array in C?
Use one loop with running values: add each element to a sum that starts at zero, and start the lowest and highest at the first element, updating them only when an element beats them. Starting the lowest at zero fails for positive prices, because nothing is ever smaller. After the loop, divide the sum by the count, casting to float if both are integers, so 7 / 2 gives 3.5, not 3.

About the Programming in C course

How many college credits is Programming in C?
Programming in C (Computer Science 240) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Programming in C cost and what is included?
$250, paid once, with lifetime access: all 78 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Programming in C take?
It is self-paced with no deadlines. The 78 lessons total about 9 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Programming in C.

78 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Programming in C →Download the syllabusEvery course with PRO →
Programming in C
3 credits · NCCRSEnroll →