Course Content‎ > ‎Session 3‎ > ‎

Sorting

Insertion Sort

The array is divided into two parts: sorted and unsorted. In each pass the first element of the unsorted sublist is picked up and transferred into the sorted sublist by inserting it at the appropriate place. It will take n-1 passes to sort an array of size n.

    public void insertionSort (int[] list,  int last )
    {
        /*Local Declarations*/
        int current ;
        
        /*Statements*/
        for ( current = 1 ; current <= last ; current++ )
            insertOne( list, current) ;
            
        return ;
        
    } /* insertionSort */
         
    void insertOne (int[] list, int current )
    {
        /* Sorts current element in unsorted list into its proper location in 
           sorted portion of the list--one sort pass.
           Pre:  list must contain at least one element; current identifies
                 the beginning of the unsorted list.
           Post: next element placed into its proper location
        */
        
        /*Local Declarations*/
        int walker ;
        int located ;
        int temp ;
         
        /*Statements*/
        located = FALSE ;
        temp = list[ current ] ;
        
        for  ( walker = current - 1 ; walker >= 0 && !located ; )
        {
            if ( temp < list[ walker ] )
            {
                list[ walker + 1] = list[ walker ] ;
                walker-- ;
            } /* if */
            else
                located = TRUE;
        }
                
        list [ walker + 1 ] = temp ;
            
        return ;
        
    }/* insertOne */



Bubble Sort

Using a for loop the lowest element is bubbled to the beginning of the unsorted segment of  he array.  The process is accomplished by a function called bubbleUp. bubbleUp makes one pass through the data. Whenever it finds two elements out of sequence, it exchanges them. It then continues with the next element. This allows smallest number to be bubbled to the  beginning of the array, while at the same time adjacent elements along the way are rearranged. Here is the code segment illustrating bubble sort:

    public void bubbleSort  (int[] list, int last)
    {
        /*Local Declarations*/
        int current ;

        /*Statements*/
        for(current = 0; current <= last ; current++)
            bubbleUp ( list, current, last );

        return ;

    } /* bubbleSort */
     

    void bubbleUp (int[] list, int current, int last)
    {    
        /* Move the lowest element in unsorted portion of an array to the current
           element in the unsorted portion
           Pre:  list must contain at least one element current identifies 
                 beginning of unsorted data last identifies the end of the 
                 unsorted data
           Post: Array segment has been rearranged so that lowest element is now 
                 at beginning of unsorted portion.
        */
        
        /*Local Declarations*/
        int walker;
        int temp ;
         
        /*Statements*/
        for ( walker = last ; walker > current ; walker-- )
        {
            if ( list[ walker ]  < list[ walker - 1 ] )
            {
                temp = list[walker] ;
                list[walker] = list[walker - 1] ;
                list[walker - 1] = temp ;
            } /* if */
        }
        
        return ;
    } /* bubbleUp */


Selection Sort

List is divided into sublists, sorted or unsorted, which are divided by an imaginary wall. Find the smallest element from the unsorted sublist and swap it with the element in the beginning of the unsorted list. After each selection the wall between the sublist moves one element ahead, increasing the number in the sorted list and decreasing the number in the unsorted list. Each time we move one element from the unsorted list to the sorted list, it completes a sort pass. We would go thru  n-1 passes for sorting an array of n elements.

    public void selectionSort (int[] list, int last )
    {
        /*Local Declarations*/
        int current ;
         
        /*Statements*/
        for ( current = 0 ; current < last ; current++ )
            exchangeSmallest ( list, current, last ) ;

        return ;

    } /*selectionSort*/


    void exchangeSmallest (int[] list, int current, int last )
    {
        /* Given array of integers, place smallest element into position in array.
           Pre:  list must contain at least one element; current is beginning
                 of array (not necessarily 0); last is last element in array. 
                 Must be >= current
           Post: returns index of smallest element in array.
        */
        
        /*Local Declarations*/
        int walker ;
        int smallest ;
        int tempData ;
         
        /*Statements*/
        smallest = current;
        
        for (walker = current + 1 ; walker <= last ; walker++)
            if ( list[ walker ] < list[ smallest ] )
                smallest = walker ;
        
        /* Smallest selected: exchange with current element */
        tempData = list[ current ] ;
        list[current] = list[ smallest ] ;
        list[smallest] = tempData ;
        return ;
        
    }  /* exchangeSmallest */

Comments