6.1 Definition of Sorting

Sorting is the process of arranging the items in a collection into a defined order, according to a rule that can be applied to every pair of items. The rule may place numbers from smallest to largest, names alphabetically, or dates from earliest to latest. Example: a SACCO keeps the records of its members in a list, and arranging them by member number lets the clerk find any member quickly instead of reading every record from the beginning.

In computing, sorting is carried out on data held in structures such as arrays and lists. A sorting algorithm is a finite, step-by-step set of instructions that compares items and rearranges them until the whole collection satisfies the chosen order.

Ascending and descending order

Every sort has a direction. Ascending order places the smallest or earliest item first and the largest or latest item last, while descending order does the opposite. The direction is chosen according to the need: a list of fee arrears may be most useful with the largest balance first, whereas a register is most useful in alphabetical order.

Example: the numbers 45, 12, 78, 23 are arranged as follows.

Ascending: 12, 23, 45, 78

Descending: 78, 45, 23, 12

Basic terms used in sorting

A few terms appear in every discussion of sorting. Understanding them makes it easier to read and write sorting algorithms.

Example: a secondary school stores each student as a record containing the admission number, the name and the mean mark. Sorting the records by mean mark produces a ranking, while sorting by name produces an alphabetical class list from the same data.

• Collection: the group of items to be sorted, usually stored in an array or a list.
• Record: a single item made up of one or more fields, such as a student with an admission number, a name and a mark.
• Key: the field on which the order is based. Sorting students by mean mark uses the mean mark as the key.
• Comparison: the test that decides which of two items should come first, for example checking whether one key is greater than another.
• Swap: the exchange of the positions of two items in the collection, which is the basic way in which items are moved into place.
• Pass: one complete scan through the collection during which comparisons and swaps are made.

Why sorting is important

Sorted data is easier for people to read and much faster for computers to search. Many everyday systems depend on sorted data, and sorting is one of the most frequently performed operations in programming.

• Faster searching: a sorted list can be searched using binary search, which repeatedly halves the portion being examined. A county land registry with sorted plot numbers can locate a plot in a few steps instead of checking every entry.
• Easier reading and reporting: a bank statement is arranged by transaction date so that a customer can follow the movement of money from the first entry to the last.
• Scheduling and priority: a hospital arranges its appointments by time so that the reception desk and the doctors see patients in the correct sequence.
• Ranking and selection: a logistics company can sort deliveries by distance or by weight to decide which should be dispatched first.
• Finding duplicates and gaps: when records are sorted, identical or missing entries sit next to each other. A hotel sorting bookings by room number and check-in date can quickly spot two guests booked into the same room on the same night.
• Supporting other algorithms: merging lists, removing duplicates and grouping records all work more simply and efficiently when the data is already in order.

Sorting different kinds of data

Sorting rules depend on the type of data being compared. A programmer must choose a rule that matches the data, otherwise the result may look correct to the computer but wrong to the user.

Example: a supermarket sorts its stock list by unit price in Ksh, then by product name, so that items with the same price appear in alphabetical order.

• Numbers: compared by value, so 9 comes before 30. If numbers are stored as text, they are compared character by character and "30" would wrongly come before "9".
• Text: compared character by character using the character codes of the computer. In many systems all capital letters come before small letters, so "Zawadi" would appear before "achieng" unless the case is ignored.
• Dates: compared by year first, then month, then day. Storing dates in a year-month-day format makes this comparison straightforward.
• Records with several keys: the primary key is compared first, and the secondary key is used only when the primary keys are equal. A school may sort by class and then by mean mark within each class.
• Mixed or missing values: blank entries and special values need a clear rule, such as placing them at the end of the list.

Requirements of a correctly sorted result

A sorting algorithm is correct only when its output satisfies two conditions. First, the items must be in the required order, so that every item comes before or equal to the item that follows it in the chosen direction. Second, the output must contain exactly the same items as the input, with none lost, added or changed. For example, if a list of five loan amounts is sorted, the result must still contain those same five amounts, now arranged from smallest to largest.