CHAPTER 11

SORTING: ORDERING IT TO SEARCH FASTER

Can you imagine trying to locate a word in a dictionary that is not sorted or put in order? You would have quite a bit of difficulty finding the word. Sorting makes searching not only efficient but in many applications possible. How does a computer sort the data? It is very similar to the way you sort a series of numbers or a deck of cards. There are many ways that the data can be sorted, therefore many algorithms are there to look into and analyze. Among various existing algorithms one algorithm may perform better than another one in certain circumstances. While one sort algorithm will do the job of sorting,it is important to understand various sorting techniques, trends and circumstances so that a proper algorithm can be chosen. The complexity of a sorting algorithm is measured in terms of speed (time), amount of space required for memory storage and/orits simplicity. The three categories of sorting techniques include exchange sort, selection sort and insertion sort. These categories are based on the movement and exchange of the two next items (exchange), selecting the next item (selection), and inserting the next item in the right position (insertion). In most of the sorting techniques, the unsorted data is already placed in an array and the same array is used to hold the sorted data so as not to waste memory. There are cases where an array is not used. The data may be stored in the files or even in some other data structure such as a linked list built by pointers.

SORT IT YOURSELF: DO IT YOUR WAY Imagine that there are 10 cards sitting next to each other on your desk and your task is to put them in order (sort it) from smallest to largest (ascending order). You manage to do it right away. How did you do that? Now, try to write down each step as you did the sort. Did you continuously compare each card with the next card and then exchange (swap) the cards? If not, did you pick up the smallest card and place it at the beginning? Or did you place each card in its spot as you performed the sort? If you didn’t follow any of above, then what did you do? Did you follow the same steps over and over? If I ask you to do it over would you be able to perform the same task? Be aware that others may have different approaches than you have in sorting the cards. No matter how the intermediate work is done the result should be the same- data is sorted. However one thing is common to every one. Data is scanned over and over. This is why we need a systematic approach to programming.

Now let’s consider what would have happened if all ten cards were already sorted except one card? While there are different techniques to sort a list of data, one technique may be preferable due to circumstances. This is why consideration of the three sorting approaches (exchange, selection, insertion) may be helpful.



SORT ASCENDING OR DESCENDING Data can be sorted in ascending or increasing order from smallest to largest. Alternatively data can be arranged in descending (decreasing) order from largest to smallest. Notice data can be numeric, alphabetic, or alphanumeric, such as: 111 678 999 1234 A M X a x BYE GOOD HELLO 123BYT G482KR xyzcabbies When the data is not numeric, two items are compared in terms of their ASCII character values. Remember, the ASCII value for ‘0’ is 48, A is 65, and lower ‘a’ is 97.

EXCHANGE SORTS In order to sort a series of items, two items at a time are compared, if they are not in order (for example the first item is greater than second item) they are exchanged. However, if these two items are already in order, the exchange will not take place. After the comparison is completed, a conclusion can be drawn that the second item is not the smaller one. Then the next two items are compared and so forth. For each comparison, there would be the possibility of an exchange. You may have wondered why this family of sorting is called exchange sort. Among the family of exchange sorts are bubble sorts and shell sorts. Bubble sorts compare two adjacent cells (items) while shell sorts compare elements with adistance of more than 1. By the time entire array is scanned, we can conclude that the largest element is placed at the end of the array (alternatively, the smallest item finds itself at the beginning of the array).

EXCHANGE SORT EXAMPLE: PASS ONE Given the ten unsorted cards listed below, what would happen if you compare the two adjacent items and exchange them when necessary until all cards are covered? Going through all the data is known as a pass. Since the larger data is moved one space (or slot) to the end each time by the end of the pass, the largest data will be placed at the end. Observe the unsorted data below and the data movement from the beginning to the end of (pass one). What do you conclude from this sorting approach (algorithm)?

                                (8)(3) (1) (5) (7) (10) (4) (9)(6) (2)   	
		        (3)(8)
		              (1) (8)
		                    (5) (8)
		                          (7) (8)
			                    (8) (10)
			                          (4) (10)
			                                 (9) (10)
				                            (6) (10)
				                                  (2) (10)
	               	    (3)(1) (5) (7) (8) (4) (9) (6) (2) (10)

You can observe that the largest data moved to the end and other items moved one position nearer to its sorted position (bubbling up).

Original data (8)(3)(1)(5)(7)(10)(4)(9)(6)(2) After the first pass sort (3)(1)(5)(7)(8)(4)(9)(6)(2)(10)

EXCHANGE SORT PROGRAM: FIRST PASS Let us go easy and translate the algorithm to the programming code the way that we were viewing it by comparing and swapping the two items. The items are placed in an array called slot for simplicity. You can call it any other name if you don't like slot. Remember the first element of an array starts with zero. After comparison of first two items, a user defined swap function is called. The swap function passes the array and two indices of the array that should be exchanged with each other.

if (slot[0] > slot[1] ) swap(slot, 0,1);
if (slot[1] > slot[2] ) swap(slot,1,2);
..............
if (slot[n-2] >slot[n-1] ) swap(slot,n-2,n-1);


Let us generalize this by using an index variable such as i.

if  ( slot[i] > slot[i+1]) swap(slot, i, i+1)
Let us apply a loop to move through all the slots (one pass)
for ( i=0; i < n-1; i++) 
         if  ( slot[i] > slot[i+1]) swap(slot, i, i+1)


The size of the data is n. We have given n the value 10. In C/C++, the array index begins with 0, therefore, if 10 spaces are allocated for the array they are numbered from 0 to 9. If i is 9 and we compare i with i+1, there would be an error since the array slot 10 is nonexistent. As a result, having i < n-1 sets the maximum value of i to 8.

EXCHANGE SORT WITH ALL THE PASSES (N PASSES)

With the first pass of the exchange sort only one item is sorted (e.g. largest value). Each slot is compared with the next slot and if it is not in order a swap will occur. Similarly with the second pass, the second largest value is put into the right place. Finally as the number of passes progress, the items gradually become sorted.

for (pass=1 ; pass <=n; pass ++)  {
                        for ( scan=0; scan < n; scan++) 
                               if  ( slot[scan] > slot[scan+1] ) swap(slot, scan, scan+1); }


EXCHANGE SORT: ROOM FOR IMPROVEMENT

The heart of the exchange algorithm is for every pass to scan through the entire list and compare two items, swapping them if it is necessary. An improvement for the above algorithm would be,that if all of the data gets sorted except one item. That item will then be in the sorted place (sound philosophy). Therefore the number of passes will be one less than the total. Instead of using pass<=n you will use pass<n. On every pass, one item will find its sorted place, e.g. at the first pass the last item will be sorted which will be placed at the end of the list. Therefore at the second pass we don’t need to scan to the end of the list. Generally if the size of data is nthen on each pass there will be 1 less item to be scanned from the end of the list.The improvement will be instead of scan<n to use scan<n-pass. In our example, n is 10. Therefore we need 10 passes. Do not be surprised in 9 passes (n-1) the data gets sorted. Looking at it philosophically, the last data in the last pass is automatically in the right place since everybody else is sitting in their right place (slot). We know that in the first pass the last data is ordered. In the second pass we know that the last data is already sorted and we do not have to bother to do anything but to exclude the last number. On the first pass will be scan <n-1, on the second pass will be scan <n-2. On the third pass we will have scan <n-3. As a result we can generalize it as scan <n - pass.

Consider more improvement. If there is no swap within a pass, then the list of items are already sorted. This will be explained later.

EXCHANGE SORT PROGRAM: BUBBLE SORT

The following program demonstrates an exchange sort by having two loops, one if and one swap. Items will be ordered in ascending order and at each pass, two items will be compared and the smaller one will be swapped to the left. At the end of each pass the largest data will be pushed to the end. This kind of exchange sort is called bubble sort since the smaller light data are bubbling up gradually.

1.	#include<iostream>
2.	using namespace std;
3.	swap(int slot[],int i, int j){
4.	     	int temp;
5.	     	temp=slot[i];
6.	     	slot[i]=slot[j];
7.	     	slot[j]=temp;
8.	     	return 0;
9.	}//SWAP
10.	main(){
11.	     	int scan,pass,n=10, i;
12.	     	int slot[ ]={8,3,1,5,7,10,4,9,6,2};
13.	     	for(pass=1;pass<n;pass++){
14.	        	for(scan =0; scan <n-pass; scan ++){
15.	                  if(slot[scan ]>slot[scan +1])
16.	                      	swap(slot,scan,scan+1);                      
17.	             }//end scan
18.	        }//end pass
19.	     	cout<< " SORTED ITEMS: "<<endl;
20.	     	for(i=0;i<n;i++)
21.	           cout<<slot[i]<<"  ";
22.	    	cout<<endl;
23.	     	return 0;
24.	}//MAIN

Figure 11.1a - Program to show an exchange sort

SORTED ITEMS:
1  2  3  4  5  6  7  8  9  10


Figure 11.1b - Output of Figure11.1a

EXCHANGE SORTS: SINK SORT, BUBBLE SORT, OR TURTLE SORTS In an exchange sort, each time two items are compared the larger (heavy) item moves one level down to the bottom (to the right). At the end of each pass, the largest item will be placed at the bottom. In an exchange sort, the heaviest items are gradually sinking until sunk. This is known as a sink sort. Alternatively, in exchange sort, when the light items are gradually bubbling up and the lightest item is at the top, we have a bubble sort. Due to the slow movement of items, gradually one level down or one level up, sink sort and bubble sort are also known as turtle sorts. Note that often sink sort is referred to as bubble sort as well.

PROGRAM EXECUTION TIME Every programming instruction (language construct) that is used in statements such as computation, assignment, comparison, or repetition has its own execution time due to its own hardware architecture. A program execution can be measured by the sum of the execution time of its instructions and elapsed time (the difference between start and ending time can be used to determine the execution time). However, an execution time of a program is related to how much data is used in the program. In other words, the size of the data is important in measuring the execution time. One way to measure program execution time is to look at the major expressions such as the number of comparisons or the number of exchanges in the program. The following code would be needed to compute the elapsed time for a bubble sort program.

#include 
using namespace std;
starttime=time(0);
for(pass=0; pass<10;pass++)for (int i; islot[i+1]swap(slot,i,i+1);}//END LOOP PASS
endtime=time(0);
elapsedtime=starttime-endtime;


HOW LONG DOES IT TAKE TO SORT A sort program consists of at least two loops that compare two items. Based on the result of a comparison an exchange (swap) or shuffle (shift) will take place. The number of comparisons will differ depending on the size of the data and as a result the number of swaps or shuffles will be different. For example, if you are sorting 1000 items the number of comparisons will be higher than if you were sorting 10 items. Similarly the number of swaps or shuffles will be higher as the size of the data becomes larger. Therefore the execution time of a sort depends relatively on the order of size of the data - e.g. O(N). For example if the size of the data is 10 and there are two loops (nested), there are approximately 100 comparisons. Generally the number of comparisons for the size of n will be n2.

CALCULATING NUMBER OF COMPARISON AND SWAP: BUBBLE SORT

How many comparisons and how many swaps are in a bubble sort? Roughly speaking we have n data, therefore n-1 comparisons, and for each comparison we might need an exchange (worst case). Therefore, for a data size of 10 items we need 9 comparisons and 9 exchanges (swaps). This is just for the first pass. How about the second pass? We need one less comparison and one less swap. For the second pass we need n-2, in third pass n-3, and finally n-9 which is 1. Add the numbers for each pass together we will have:

n-1 + n-2 + n-3 + n-4 +  n-5 + n-6 + n-7 + n-8 + n-9  
It seems like the sum of the first n numbers already has a mathematical formula n(n+1)/2. For above example substituting the value in the formula we will have 9*(10)/2 which is 45 comparisons needed to sort a data of size 10. Similarly 45 swaps are needed in the worst case.

CALCULATING THE SUM OF THE FIRST N NUMBERS

Mathematicians have calculated the sum of the first n numbers according to the following procedures: To find the sum of a series (9 to 1): Start with adding the reverse of the series which makes all numbers the same( e.g. 10). Count the resulting numbers. There are n number of n-1. Finally, divide the result by 2 since an additional series was added at the beginning. By observing the below computation yourself, you can figure out why the formula is n* (n+1)/2 and sum of the first 9 number is 9*(10)/2.

9      + 8     + 7     + 6    + 5      + 4    + 3    + 2    + 1 
+         +       +	        +	     +        +       +        +       +	             
1	2       3	        4	     5         6       7        8       9
||	||       ||          ||       ||         ||        ||        ||        ||
10       10      10      10     10       10     10      10     10
WORST CASE, AVERAGE CASE AND BEST CASE OF AN ALGORITHM

To analyze an algorithm and to have a better picture of how an algorithm function works there are three situations that one may have to observe: Worst case, Average case and Best case. For example, for a sorting algorithm the worst case would be when the number of comparisons and swaps are the maximum and the best case would be when the number of comparisons and swaps becomes the minimum. The average case is the mixture of all special cases including worst and best cases, and in several algorithms finding the average case is not an easy task to figure out. In an example of bubble sort the worst case would be when data is sorted in reverse (descending) and we want to sort it in ascending order. However a bubble sort can be performed best if the data is already sorted. If there is no swap within a pass, adding a condition to the bubble sort will terminate any further passes. Other questions such as what happens if only one data is not sorted and is in last position or in the first position. These are the questions that we need to answer in an average case since we need to look all special situations.

BIG-O NOTATION OR ORDER OF MAGNITUDE

One way to compare the algorithms without executing them or even writing them is to compare their order of magnitude (Big-O) function. A Big-O notation gives the rounded-off (upper bound) worst-case performance of an algorithm. An algorithm’s worst case is a situation that we need to watch out for. For example, the Big-O notation for the bubble sort is O(n2).

SWAP FUNCTION: DONE DIFFERENTLY

When two items are not in order, a swap is necessary to sort the items. For a swap, a temporary variable is needed to hold the value of the assigned variable before it is replaced. Note that, by default, pass of parameters in C++ is done by value. Any swap by value will not have impact upon calling the function. Therefore, the name of an array has to be passed with both indices. Pass the parameters by reference or pass the parameters by pointers as illustrated below:
 swap (int slot[ ], int i, int j)
{
   	int temp = slot [ i ];
       	slot [ i ] = slot[ j ];
          	slot [ j ] = temp;          
}
In the above swap function the array and the index i and j of the array are passed.

 swap (int &x, int &y)
{
	int temp = x;
	x = y;
	y = temp;
}
For the above function to swap, the address of each element of an array is passed. In C++ this passing is known as pass by reference. In order to use a swap function we need temporary memory. The following function demonstrates the swap without wasting memory.

The function call in the main program will be as follows:

swap (slot[i], slot[i+1]);

Another way to swap is to pass pointers.
  swap (int *x, int *y)
{	
int temp=*x;
	*x=*y;
	*y=temp;
}
The above swap function receives the address of each element of the array and stored in a pointer variable (this is done traditionally in C Language). The function call in main will be:

swap (&slot[i], &slot[i+1]);

SWAP WITHOUT A TEMPORARY VARIABLE

If you wonder how to swap two variables without a third variable, so you can save memory, here we have two solutions:
swap (int &x, int &y)
{
 	x = x + y;
 	y = x – y;
  	x = x – y;
 }
The above swap will save memory, but it will take longer due to the computation. Another way to swap two items without a temporary variable is to use Exclusive-OR as show below. Exclusive-OR is faster than regular addition and subtraction. The program below uses better computation because it performs by using Exclusive-OR (bit-wise operator).
 swap (int &x, int &y)
{
  x = x ^ y;
  y = x ^y;
  	  x = y ^ x;
}
For example, x = 5, y = 6. Before the swap the binary number of x is 101; binary number of y is 110. Exclusive-OR is same OR except, when there are two 1s the answer will be 0.

x = x ^ y is 011
y = x ^y is 101
x = y ^ x is 110 
After swap x =110, y =101.

Hint: do not confuse logical OR (true / false) with bit-wise OR (binary number).

SELECTION SORT

On way to sort a series of data is to select one of the data and place it its proper position (sorted position) by swapping with other data. This kind of sort is known as selection sort since its foundation is based on the selection of an item each time. The family of selection sorts includes straight selection and quick sort.

STRAIGHT SELECTION SORT In order to sort a set of data according to the straight selection, the first data is elected and is assumed to have the smallest value of all the data. Next it goes through the rest of the data and compares that value to each remaining data. If the selected value is not the smallest it will be reset to reflect the smallest value found. At the end of the first pass the smallest found is swapped and placed at the first position. For example, the first position of the array is selected as the minimum location that holds the smallest value. A loop through of the rest of an array will reset the smallest position if it is necessary. This process continues for the entire pass.

STRAIGHT SELECTION SORT ALGORITHM: SIMPLIFIED

<0l>
  • Select a next (first) slot as the smallest value.
  • Move through all the slots. If there is a smaller slot, re-assign the smallest value.
  • At the end of the pass, swap the smallest slot with the selected slot.
  • Repeat steps 1,2,3 for all passes.
  • STRAIGHT SELECTION SORT: THE FIRST PASS

    The first pass of straight selection is shown below. At the beginning number 8 is chosen as the smallest value then number 3 becomes the smallest and then number 1, which will stay until the end of the pass. At the end of the pass number 8 will be swapped with number 3.
           (8)(3)(1)(5)(7)(10)(4)(9)(6)(2)
    
          (8)  
                (3) 
                     (1)
                            (1)
                                  (1)
                                       (1)
                                            (1)
                                                 (1)
                                                      (1)
                                                            
           (1)     (8)                                         
    
    
    The following illustrates the original data aftermath of the first pass in selection sort Original data (8)(3)(1)(5)(7)(10)(4)(9)(6)(2)

    First pass (1)(3)(8)(5)(7)(10)(4)(9)(6)(2)

    STRAIGHT SELECTION PROGRAM: FIRST PASS

    In the programming of the first pass of the straight selection, the first location is set as the smallest location ( sml=0 ). A loop scans through the second element of the array and so on comparing each element of the array ( slot[scan] ) with the element in the smallest location. This will reset the sml to the new smallest value if comparison is true. The swap function will take place after the loop (first pass). Note that the location of the smallest value is used instead of the smallest value itself since the smallest location is used as the index of an array in the swap function.
    sml=0;
    for (scan=1; scan
    
    STRAIGHT  SELECTION: SECOND   PASS AND ALL  THE PASSES. 
    

    The second pass of a straight selection sort is the same as the first pass except for initial value of the smallest location (sml = 1), starting of the loop (scan = 2) and swap function sml with index 1. Select the second slot then move through the rest of the slots. If there is a slot with a smaller value then the selected slot will be reassigned. At the end of the second slot.
    (Note: the pass starts at 0)
    sml=1;
     for ( scan = 2; scan
    To make the  program general for all passes use the following steps: 
    
    • Set the smallest location to the current pass.
    • Start the loop one location after the pass
    • Swap the pass location with the smallest location.
    for (pass=0, pass
    
    
    STRAIGHT SELECTION SORT:  COMPLETE PROGRAM
    
    

    The following program demonstrates the straight selection sort; the data is stored in an array (slot). The program consists of two loops (nested), one to go through all passes and another one to scan the array on each pass. Note that a swap is done only at the end of each pass.
    1.	#include
    2.	using namespace std;
    3.	swap(int slot[],int a,int b); //PROTOTYPE
    4.	main(){
    5.	     	int pass,n=10,sml,scan,i;
    6.	     	int slot[]={8,3,1,5,7,10,4,9,6,2};
    7.	     	for(pass=0;pass
      Figure 11.2a - Program to show a selection sort 
    

    AFTER SORT
    1 2 3 4 5 6 7 8 9 10
    
    Figure 11.2b - Output of selection sort

    STRAIGHT SELECTION SORT: INTERMEDIATE PASSES

    The following program displays the output of the intermediate steps after completion of each pass. Note that at the first pass the smallest number is in the first slot. On the second pass the next smallest is in the second slot, and so on. At the ninth and tenth pass the data is already sorted. A conclusion can be drawn that the last pass is unnecessary; therefore, the number of passes equals one less than the size of the array (pass < n - 1).
    1.	#include
    2.	#include
    3.	using namespace std;
    4.	swap(int slot[],int a,int b){
    5.	    	int temp;
    6.	     	temp=slot[a];
    7.	     	slot[a]=slot[b];
    8.	     	slot[b]=temp;
    9.	     	return 0;    }//SWAP
    10.	main(){
    11.	     	int i,pass,n=10,sml;
    12.	     	int slot[10]={8,3,1,5,7,10,4,9,6,2};
    13.	     	cout<<"BEFORE SORT "<
    Figure 11.3a - Program to show all the steps of a selection sort 
    
    BEFORE SORT
    8 3 1 5 7 10 4 9 6 2
    PASSING 1         1 3 8 5 7 10 4 9 6 2
    PASSING 2         1 2 8 5 7 10 4 9 6 3
    PASSING 3         1 2 3 5 7 10 4 9 6 8
    PASSING 4         1 2 3 4 7 10 5 9 6 8
    PASSING 5         1 2 3 4 5 10 7 9 6 8
    PASSING 6         1 2 3 4 5 6 7 9 10 8
    PASSING 7         1 2 3 4 5 6 7 9 10 8
    PASSING 8         1 2 3 4 5 6 7 8 10 9
    PASSING 9         1 2 3 4 5 6 7 8 9 10
    PASSING 10         1 2 3 4 5 6 7 8 9 10
    
    AFTER SORT
    1 2 3 4 5 6 7 8 9 10
    
    Figure 11.3b - Output of Figure 11.3a

    STRAIGHT SELECTION VERSUS BUBBLE SORT How long does it take to sort with straight selection or bubble sort? Both sorts use one loop for passes and one loop to scan through the array. Both have the same number of comparisons; however, the straight selection sort does not require as many swaps as the exchange sort. The maximum number of swaps in selection sort is n, while in the exchange sort it is n2. When using the selection sort, there is another variable (memory location), which keeps track of the smallest location number. In the worst case, there is n for the first pass, n-1 for the second pass, n-2 for third and so on. Therefore, it takes just as much time as the exchange sort, the order of notation for the both sorts is O(n2).

    IMPROVING THE STRAIGHT SELECTION

    A straight selection behaves the same no matter how the data is ordered, unsorted or sorted in ascending or descending order. On each pass, the smallest item is found and placed at the beginning even if it means swapping the lowest value with itself. Another selection sort, Quick Sort optimizes the sorting process. One variation is to use a flag to determine whether a swap has occurred during a pass, this will add an extra comparison and swap. Otherwise there is no way to know if the data is sorted.

    INSERTION SORT As the data arrives, it is inserted in the proper position. An analogy would be sorting cards as they are dealt to your hand. Initially the first value (card) is automatically placed in the first slot, the second value is compared to the first and inserted either before or after the first. The possibilities for the third value are before the first, after the second or between the two. Similarly, the insertion continues either at the beginning, the end or somewhere in between. The process continues until all elements have been sorted. As the data arrives, it is inserted into an array. New data can only be inserted if the data shifts one position (slot) to the right.
    1.	#include 
    2.	using namespace std;
    3.	main(){
    4.	    	int n=0, i=0, x, slot[10];
    5.	     	cout<<"ENTER THE NUMBERS:  "<>x;
    8.	            	if(n==0) slot[n]=x;		// SLOT EMPTY
    9.	         	else{ 	i = 0;
    10.	                        	while(x>slot[i]){	//FIND INSERTION LOCATION
    11.			                i++;
    12.			                if(i==n){slot[i]=x; break; }//IF
    13.			         	}//WHILE
    14.		                  	if (ii){
    17.	    	                                          	slot[j]=slot[j-1];
    18.	                                                  	j--;    }//WHILE
    19.	      	              	slot[i]=x; }//IF
    20.	               	}//ELSE
    21.	      	n++;        
    22.	 	}//WHILE n<5
    23.	    	for(i=0; i<5;i++) cout<< slot[i]<<" ";
    24.	    	return 0;
    25.	}//MAIN
    
    Figure 11.4a - Program to show an insertion sort shows data inserted as it arrives

    ENTER THE NUMBERS:
    3
    5
    2
    8
    1
    1 2 3 5 8 
    
    Figure 11.4b - Output of Figure 11.4a

    INSERTION SORT: DATA STORED IN AN ARRAY
    1.	#include 
    2.	using namespace std;
    3.	main(){
    4.	    	int slot[10] = {8,3,1,5,7,10,4,9,6,2};
    5.	    	int i, j, x;
    6.	    	for (i = 1; i < 10; i++){	
    7.	 		x = slot[i];
    8.	                  j = i;
    9.	                  while (slot[j -1] > x){
    10.	                          	slot[j] = slot[j - 1];
    11.	                              j = j - 1;
    12.	                              if (j <= 0) break;      }//WHILE
    13.	                 	slot[j] = x;
    14.	  	}//FOR
    15.	   	cout<<"AFTER SORT: "<
    
      Figure 11.5a - Program to show an insertion       sort (data already in an array)
    
    AFTER SORT:
    1 2 3 4 5 6 7 8 9 10
    
    Figure 11.5b - Output of Figure 11.5a

    LOCATION WHERE TO INSERT A NEW ELEMENT
    i=0;
    while ((newnumber>slot[i])&& (i 
    
    
    
    DRAW BACK OF INSERTION SORT  USING ARRAY
    

    When using arrays with insertion sort, it is possible that an n-1 shift may need to be taken in order to insert a new element into the array. Using a different data structure, such as a linked list, will improve the insertion sort. Shifting is not necessary since reassigning is done using pointers.

    QUICK SORT FROM STANDARD LIBRARY:

    If you do not want to bother writing your own quick sort program, you can use a built-in function from the standard library. You must provide the header file as well as required parameters as shown in the following example:
    #include 
    using namespace std;
    void qsort (slot,10, sizeof(int), compare);
    
    The first parameter is the array (e.g. slot), second is the maximum of the array (e.g.10), the third is size of the data type (sizeof(int)), the fourth is the function name (address of the function) that indicates how the quick sort should compare the data (e.g. compare for ascending or descending).

    The compare function takes two arguments and it subtracts the second from the first and returns the result. If the result is positive the first is larger, if the result is negative the first is smaller, otherwise both are equal.

    For example: ascending (a,b)

    descending (b,a)

    both at different times will call the function compare.

    qsort( ): EXAMPLE

    The following program illustrates the use of the qsort( ) built-in function for both ascending and descending order.

    1.	#include
    2.	#include
    3.	using namespace std;
    4.	int AscenCompare(const void *x, const void *y){
    5.	    	return(*(int*) x - *(int*)y);
    6.	 	}//ASCENCOMPARE
    7.	int DescenCompare(const void *x, const void *y){
    8.	     	return(*(int*) y - *(int*)x);
    9.	 	}//DESCENCOMPARE
    10.	main(){ 
    11.	   	int slot[]={8,3,1,5,7,10,4,9,6,2};
    12.	   	int i;
    13.	   	int choice;
    14.	   	cout<<"ENTER A CHOICE, 1 FOR ASCENDING, 2 FOR DESCENDING:  ";
    15.	   	cin>>choice;
    16.	   	if (choice==1)
    17.		   	qsort(slot, 10, sizeof(int), AscenCompare);
    18.	   	else if (choice==2)
    19.		   	qsort(slot, 10, sizeof(int), DescenCompare);
    20.	   	cout<<"SORTED DATA"<
    Figure 11.6a - Quick sort from standard library
    
    
    ENTER A CHOICE, 1 FOR ASCENDING, 2 FOR DESCENDING:  1
    SORTED DATA
    1  2  3  4  5  6  7  8  9  10
    
    ENTER A CHOICE, 1 FOR ASCENDING, 2 FOR DESCENDING:  2
    SORTED DATA
    10  9  8  7  6  5  4  3  2  1
    
    Figure 11.6b - Output of Figure 11.6a

    HOW DOES QUICK SORT WORK

    Select a number from the table and call it "pivot". Arrange the numbers in such a way that all the numbers to the left of the pivot are smaller and all the numbers to the right of the pivot are larger. Any number to the left of that number should be less or equal and any number to the right of that number should be more or equal. Therefore the number is situated in the sorted position. The whole list (table) can be viewed as two sub-lists one to the left of the pivot and one to the right of the pivot. Similarly the same process can be done to each of the sub-lists until there would not be any more sub-lists (list with one element).

    1.	#include
    2.	using namespace std;
    3.	swap ( int &x, int &y){
    4.	     	int temp=x;
    5.	     	x=y;
    6.	     	y=temp;
    7.	     	return 0;   }//SWAP
    8.	int partition (int x[ ], int begin, int end){
    9.	      int pivotindex;
    10.	      int pivot = x[begin];
    11.	      int left = begin,
    12.	      right = end;
    13.	     	while (left < right) {
    14.	           	while (x[right] > pivot)
    15.	                     	right --;
    16.	                	while (left < right && x[left] <= pivot)
    17.	                    	left ++;
    18.	                   if (left < right)
    19.	                         	swap ( x[left], x[right]);
    20.	              }//WHILE
    21.	     	pivotindex=right;
    22.	     	x[begin] = x[pivotindex];
    23.	     	x[pivotindex] = pivot;
    24.	     	return pivotindex;       }//PARTITION
    25.	void quicksort ( int x[], int begin, int end){
    26.	       int pivotindex;
    27.	       if (begin < end){
    28.	             	pivotindex = partition (x, begin, end);
    29.	                  quicksort (x, begin, pivotindex - 1);
    30.	                  quicksort (x, pivotindex + 1, end);     }//IF
    31.	     }//QUICKSORT
    32.	main (){
    33.	     	int  slot[10]= { 6,2,4,1,9,7,8,3,0,5};
    34.	      quicksort (slot, 0, 9);
    35.	      int i;
    36.	      cout<<"AFTER SORT"<
       Figure 11.7a - Program to show a quick sort 
    
    AFTER SORT
    0 1 2 3 4 5 6 7 8 9
    
    ?Figure 11.7b – Output of Figure 11.7a quick sort

    DISCOVER YOUR OWN SORT

    Discover a new sort for yourself. There are several sorting algorithms to choose from. Certain situations call for a particular sorting algorithm that is preferred over the others based on speed (amount of execution necessary), space (in memory), size (amount of data needed to process) or even simplicity of use (ease of understanding).

    Quick sort was invented in the early 1960’s by C.A. Hoare and was improved or optimized) by R. Sedgewick in the late 1970’s. In discovering a new sort or improving an existing one, the question should be asked: what contribution will be made to the existing sort, or why this new sort is needed. The Exsel sort (Ebrahimi sort) encourages problem solving by the student. More complicated specifications ensure that Exsel is a better sort in comparison to either the bubble sort or straight selection sort.

    EXSEL SORT

    The Exsel sort is a combination of the bubble sort and straight selection sort in such a way that it takes the advantages of each as well as tries to eliminate the disadvantages of both bubble sort and straight selection. One advantage of the bubble sort that we can take into consideration is that if there is no swap in one pass we know the data is sorted. One advantage of the straight selection sort is that we can place the smallest numbers no matter where they are in the beginning of the data. The performance of the Exsel sort is done so that the number of comparisons and swaps in total should be less than the bubble sort or straight selection sort.

    EXSEL SORT: COMPLETE PROGRAM
    1.	#include
    2.	using namespace std;
    3.	swap (int [ ], int, int); 
    4.	main(){
    5.	    	int slot[10]={8,3,1,5,7,10,4,9,6,2};
    6.	    	int n=10,i;
    7.	    	int lower, upper, sortflag, sml, scan;
    8.	    	lower=0; 
    9.	    	upper=n-1;
    10.	    	sortflag=1;
    11.	    	while((lowerslot[scan+1]){
    17.	                 			swap(slot,scan,scan+1);
    18.	                              	sortflag=1;
    19.					if(slot[scan]
      Figure 11.8a - Exsel sort
    
    AFTER SORT:
    1 2 3 4 5 6 7 8 9 10
    
    Figure 11.8b - Output of Figure 11.8a

    MERGE SORT

    A sorting technique that sorts the items that are already sorted from two or more arrays (or files) into one array (or a file) is called a merge sort. For example suppose there are two separate arrays and that each hold sorted items and the task is to place all of the sorted items into a new array. How does merge sort work? Start by comparing the first element of each array and place the smallest into the new array. The next is to compare the second element of one array (with smaller value) with the first element of the other array and place the smaller of each into the new array. The catch is, to increment the index array of the smaller number as well as increment the index of the destination array. The sorted arrays may be of different size. After one array finishes first, the entire elements of the other array must be copied into the new array (destination array).

    MERGE SORT PROGRAM: TWO SORTED ARRAYS

    The following program demonstrates a merge sort which sorts two sorted arrays, namely slota and slotb, and places the entire sorted result into slotc. The array slota has six elements and slotb has four elements. An array of ten elements is reserved for slotc. A loop condition checks the boundaries by comparing the current index of each array with its maximum size. While both ranges are valid, the program compares the first element of slota with slotb and if slota is smaller it will copy slota to slotc otherwise copy slotb to slotc. In each case the index of the smaller array (either slota or slotb) and index slotc are incremented by one. In the above program slotb will terminate first, since the index of a slotb has reached to the end before slota. As a result there is no need to compare the remaining of slota and they are copied into slotc. The first while loop will take care of the slota. In contrast with different arrays it is possible that slota finishes before the slotb, which in this case the entire contents of slotb is copied into slotc. The last loop is designated for copying the remaining of slotb into slotc.
    1.	#include
    2.	using namespace std;
    3.	main(){
    4.	     	int slota[6]={2,4,6,8,9,10};
    5.	     	int slotb[4]={1,3,5,7};
    6.	     	int slotc[10];
    7.	     	int i=0,j=0,k=0;
    8.	     	int m=6,n=4,p=10;
    9.	     	while ((i
      Figure 11.9a - A merge sort of two sorted arrays
    
    SORTED DATA: 1 2 3 4 5 6 7 8 9 10
    
    Figure 11.9b - Output of Figure 11.9a

    INTERNAL AND EXTERNAL SORTING:

    A sorting technique that sorts the data residing in the primary memory as an array is known as internal sorting. A sorting technique that sorts the data residing in the secondary memory as a file is called external sorting. Most algorithms discussed above use internal sorting since the data is already copied into arrays. If the data is residing in a file or in several files, the algorithm will access each element from the files and perform the comparison each time.

    EXTERNAL SORT EXAMPLE: FILE MERGE SORT In the following program the data is residing in two sorted files. The program will access each file and get an item from each and the smaller will be placed in a new file. Whenever the smaller item is copied into the new file, a new item will be accessed from the file with the smaller items. This access and comparison process will continue until all of the data from a file is copied into the new file. At the termination of one file the items from the other file will be copied. Since it is not clear in advance which file will be terminated first we need to write the code for both files.
    1.	#include
    2.	#include
    3.	#include
    4.	using namespace std;
    5.	main(){  
    6.	 	char itema[10],itemb[10];
    7.	    	ifstream fina ("filea.in");
    8.	    	ifstream finb ("fileb.in");
    9.	    	ofstream fout ("filec.out");
    10.	    	fina>>itema;
    11.	    	finb>>itemb;
    12.	    	while (!fina.eof()&& !finb.eof()){
    13.	          	if (strcmp(itema,itemb)<0){fout<>itema; }
    14.	               	else {fout <>itemb;}
    15.	             	}//WHILE
    16.	    	do{ fout<>itema); 
    17.	    	do{ fout<>itemb);
    18.	     	return 0;
    19.	}//MAIN
    
    Figure 11.10a - A merge sort of two files

    apple
    apricot
    kiwi
    lime
    
    Figure 11.10b –Input data file filea.in
    banana
    cherry
    lemon
    
    Figure 11.10c –Input data file fileb.in
    apple
    apricot
    banana
    cherry
    kiwi
    lime
    lemon
    
    Figure 11.10d –Output file named filec.out of the program in Figure 11.10a

    TOPICS NOT COVERED HERE

    Sorting is a vast topic and many books and much research has been dedicated to this subject. In fact a book volume encompassing more than 700 pages on this subject "The Art of Computer Programming, Volume 3, Sorting and Searching" was written half a century ago by the computer scientist Dr. Donald Knuth. Many mathematicians as well focus on the subject of different sorting techniques and their analysis coming up with formulas that describe the behaviors of each sorting algorithm in best, average and worst cases which I did not discuss in detail here. This chapter explains different sorting techniques in an easy manner and covers three sorting categories with at least one example from each. Note that there are more than ten major sorting algorithms, which are not covered here such as tree sort, shell sort, radix sort, pointer sort and bucket sort.

    Efficiency plays a big role in selecting a sorting algorithm. While the bubble sort, straight selection, and simple insertion are easy to program they are less efficient than other sorts such as, quick sort and heap sort that are more difficult to understand. More time can be spent discussing the efficiencies of sorting algorithms than is available here.

    Due to the demands of sorting, the sort function is included in the C++ Standard Library (STL).The sort function may be used simply by including the algorithm header file.
    #include 
                    sort (slot, size);
    
    Note that for the STL, #include <algorithm>, .h is not part of the include file.

    The examples in this chapter deal only with arrays of integers for ease in swapping and shuffling. In the real world data are contained in records, each containing many fields. Each field would have to be swapped individually and the sort program would become very large. Sorting can be accomplished more easily using a linked list with pointers. Using pointers, a record can be easily inserted between two existing records by simply redirecting the pointer variables without moving the existing records. Pointers will be discussed in a subsequent chapter.

    CLOSING REMARKS AND LOOKING AHEAD

    Information around us is growing rapidly and with the engagement of web technology we are becoming overwhelmed. The sorting of information in some categories will speed up the search. There are at least ten major sorting algorithms with its own trade off, Understanding how these algorithms work is helpful in choosing an appropriate sort especially where time, space and ease of use are crucial.

    Sorting techniques are divided into three major categories: Exchange, Selection and Insertion. The naming of these sorts was adopted according to the following convention. With the Exchange Sort, the emphasis is on the actual exchange of two unordered items at each comparison. This process of compare and exchange (swap) continues until all items are covered or until a sorted list is produced. With the Selection Sort, an item is selected and assumed a particular property such as the smallest, the medium, or the largest. After a comparison, the assumption is either reset to a new item or remains the same. At the end of each pass, an item will be placed in the sorted position. This process is repeated until all items are placed in their proper position. With the Insertion Sort, as the name suggests, as each item arrives (input), it is inserted (placed) in the right (sorted) position creating a partially sorted list. To insert a new item, the existing items of the partially sorted list will be moved (shifted) one position to the right to accommodate the new item. An analogy of the Insertion Sort is to insert a new card in a hand (Poker). Two members of the Exchange Sort family are Bubble Sort and Shell Sort. Two members of the Selection Sort family are Straight Selection Sort and Quick Sort. Two members of the Insertion Sort family are Simple Insertion Sort and Tree Sort.

    The simplest and most popular among the sorts is Bubble sort. Quicksort is chosen for high performance. Having many sorting algorithms available, each with their own trade-off, requires analysis in the selection of an appropriate sort. Analysis of sorting is done by counting the number of comparisons when sorting a series of items making it independent of a particular processor speed. The number of comparisons is proportional to the size of the data. While most sorting algorithms sort N items requiring N*N comparisons, quicksort will perform by Nlog2N. One more advantage of studying sorting and its analysis is the enhancement of problem solving skills.

    Next, we will determine how sorting techniques can be used to enhance searching. Let us remember that searching has become a dominant force in computers for today and tomorrow rather than mathematical computations of yesterday.