Results 1 to 9 of 9
  1. #1
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default Elementary Sorts

    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:

    Java Code:
    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:

    Java Code:
    public class OrderedArrayApp {
    
        public static void main(String[] args) {
            OrderedArrayApp main = new OrderedArrayApp();
            main.initialize();
        }
    
        private void initialize() {
            
            OrderedArray array = new OrderedArray(20);        
               
        }
    }
    Thanks!
    Tabish Chasmawala

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,899
    Rep Power
    25

    Default

    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?
    Last edited by Norm; 06-13-2011 at 06:45 PM.

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,778
    Blog Entries
    7
    Rep Power
    21

    Default

    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
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

    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!
    Last edited by tabchas; 06-13-2011 at 07:13 PM.
    Tabish Chasmawala

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,778
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by tabchas View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,899
    Rep Power
    25

    Default

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

  7. #7
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

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

    Thanks!

    Here is the updated Bubble Sort Method:

    Java Code:
    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;
                    }
                }
            }
        }
    Tabish Chasmawala

  8. #8
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,778
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by tabchas View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

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

Similar Threads

  1. Tnsping of some sorts
    By mac in forum New To Java
    Replies: 1
    Last Post: 01-23-2010, 04:47 PM
  2. Elementary problems
    By mgm2010 in forum New To Java
    Replies: 6
    Last Post: 02-01-2009, 09:33 PM
  3. Elementary Quesions
    By hitmen in forum New To Java
    Replies: 6
    Last Post: 10-21-2008, 01:23 AM
  4. Topological Sorts
    By Emily in forum Advanced Java
    Replies: 1
    Last Post: 04-03-2008, 05:39 PM
  5. Topological Sorts
    By Emily in forum New To Java
    Replies: 0
    Last Post: 03-27-2008, 01:11 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •