Elementary Sorts

[tabchas]

Hey Guys,

I was just going through a book that is teaching elementary sorts so I created a program called OrderedArray in order to test them. However, I am not getting the results I want. When I time the 3 types of sorts: bubble, selection, and insertion, Bubble Sort seems dominant. This should not be true as the bubble sort is SUPPOSED to be the simplest and longest algorithm.

Can one of you guys please look at my code and make sure that I am sorting them out correctly? I just need to know whether the sort code is following the algorithm properly and not doing extra steps.

This is the OrderedArray Class:

public class OrderedArray {
    
    int [] array;
    int num_elements = 0;
    int size = 0;
        
    public OrderedArray (int size)
    {
        this.size = size;
        array = new int [size];        
    }
    
    public int search (int key)
    {
        int lowerBound = 0;
        int higherBound = num_elements - 1;
        int binary = 0;
        int count = 0;
        
        while (true)
        {
            binary = (higherBound + lowerBound) / 2;
            
            if (count > num_elements)
                return -1;
            else if (higherBound == lowerBound && array[higherBound] == key)
                return higherBound;
            else if (array[binary] == key)
                return binary;                
            else if (array[binary] < key)
                lowerBound = binary + 1;
            else if (array[binary] > key)
                higherBound = binary - 1;
            
            count += 1;
        }     
    }
    
    public void bubblesort ()
    {
        for (int i = 0; i < num_elements - 1; i++)
        {
            if (array[i] > array[i + 1])
            {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
    }
    
    public void selectionsort ()
    {
        int temp;
        
        for (int i = 0; i < num_elements - 1; i++)
        {
            temp = i;
            for (int j = i + 1; j < num_elements; j++)
                if (array[j] < array[temp])
                    temp = j;
            
            int temp2 = array[i];
            array[i] = array[temp];
            array[temp] = temp2;
        }
    }
    
    
    public void insertionsort ()
    {
       for (int i = 1; i < num_elements; i++)
       {
           int temp = array[i];
                
           for (int j = i; j > 0; j--)
           {
               if (temp < array[j - 1])
                   array[j] = array[j - 1];
               else
               {
                   array[j] = temp;
                   break;
               }
           }              
       }
    }      
    
    public void insert (int x)
    {
        if (num_elements < size)
        {
            array[num_elements] = x;
            
            num_elements += 1;
            
        }
        else 
            System.out.println("Too many items!");     
    }
    
    public void delete (int x)
    {
        int target_element = search(x);
        
        if (target_element == -1)
            System.out.println("Number cannot be found!");
        else
        {
            array[target_element] = 0;
            
            for (int i = target_element; i < num_elements - 1; i++)
                array[i] = array[i + 1];                
            
            array[num_elements - 1] = 0;
            num_elements -= 1;
        }            
    }   
    
    public void print (String s)
    {   
        long startTime; 
        
        if (s.equals("bubblesort"))
        {        
            startTime = System.nanoTime();
            bubblesort();
            System.out.println("Bubble Sort Time: " + (System.nanoTime() - startTime));
        } 
        else if (s.equals("selectionsort"))
        {
            startTime = System.nanoTime();
            selectionsort();
            System.out.println("Selection Sort Time: " + (System.nanoTime() - startTime));
        }
        else if (s.equals("insertionsort"))
        {
            startTime = System.nanoTime();
            insertionsort();
            System.out.println("Insertion Sort Time: " + (System.nanoTime() - startTime));
        }
        
        if (num_elements != 0)
        {
            System.out.print("[");
        
            for(int i = 0; i < num_elements - 1; i++)
                System.out.printf("%d, ", array[i]);     
        
            System.out.printf("%d]\n", array[num_elements - 1]);     
            
        }
        else 
        {
            System.out.print("[");
        
            for(int i = 0; i < array.length - 1; i++)
                System.out.printf("%d, ", array[i]);     
        
            System.out.printf("%d]\n", array[array.length - 1]);
        }
    }
    
    public void clear ()
    {
        for (int i = 0; i < num_elements; i++)
        {
            array[i] = 0;
        }
        num_elements = 0;
    }
}

Here is the program that uses the OrderedArray Class:

public class OrderedArrayApp {

    public static void main(String[] args) {
        OrderedArrayApp main = new OrderedArrayApp();
        main.initialize();
    }

    private void initialize() {
        
        OrderedArray array = new OrderedArray(20);        
           
    }
}

Thanks!

[Norm]

Your code has no comments describing what it is trying to do and how it is going to do it. Where do you document how you are implementing each sort?

Where is your testing program? How do you test the code you posted?

[JosAH]

Your bubble sort implementation is incorrect (and it doesn't sort your data). It needs two nested loops, not a single loop. Check your text book(s).

kind regards,

Jos

[tabchas]

Norm: Sorry about that... I didn't realize how important comments were. I will add the comments describing the process and post it again here later.
JosAH: How does it not sort the data? I tested it out and it works perfectly... And when I step through it, it is using the bubble sort algorithm. Is it necessary to use two loops? Aren't there different ways to approach the problem?

Thanks!

[JosAH]

JosAH: How does it not sort the data? I tested it out and it works perfectly... And when I step through it, it is using the bubble sort algorithm. Is it necessary to use two loops? Aren't there different ways to approach the problem?

Try to make it sort the data 5, 4, 3, 2, 1; it comes out as 4, 3, 2, 1, 5. One pass of 'bubbling' isn't enough, it only bubbles one element to its final place, i.o.w. you need n of those passes which means another (nested) loop. Your implemenation isn't correct.

kind regards,

Jos

[Norm]

It doesn't sort for me either.
You need to provide code that shows how you've tested it.

[tabchas]

Sorry about that. I now realize the importance of the two nested loops.

Thanks!

Here is the updated Bubble Sort Method:

public void bubblesort ()
    {
        for (int i = 0; i < num_elements - 1; i++)
        {
            for (int j = 0; j < num_elements - 1; j++)
            {
                if (array[j] > array[j + 1])
                {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

[JosAH]

Sorry about that. I now realize the importance of the two nested loops.

Thanks!

You're welcome of course; I bet the three sort methods run a slow as the other now, right? All three run in O(n^2) (which is not that good)

kind regards,

Jos

[tabchas]

Yea and it is weird that the selection and insertion sorts run slower than the bubble sort. What is the reason for it?