(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)

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);

if  ( slot[i] > slot[i+1]) swap(slot, i, i+1)

for ( i=0; i < n-1; i++) 
         if  ( slot[i] > slot[i+1]) swap(slot, i, i+1)

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

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

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

#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;

n-1 + n-2 + n-3 + n-4 +  n-5 + n-6 + n-7 + n-8 + n-9  

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

 swap (int slot[ ], int i, int j)
{
   	int temp = slot [ i ];
       	slot [ i ] = slot[ j ];
          	slot [ j ] = temp;          
}

 swap (int &x, int &y)
{
	int temp = x;
	x = y;
	y = temp;
}

  swap (int *x, int *y)
{	
int temp=*x;
	*x=*y;
	*y=temp;
}

swap (int &x, int &y)
{
 	x = x + y;
 	y = x – y;
  	x = x – y;
 }

 swap (int &x, int &y)
{
  x = x ^ y;
  y = x ^y;
  	  x = y ^ x;
}

x = x ^ y is 011
y = x ^y is 101
x = y ^ x is 110 

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

      (8)  
            (3) 
                 (1)
                        (1)
                              (1)
                                   (1)
                                        (1)
                                             (1)
                                                  (1)
                                                        
       (1)     (8)                                         

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.