Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 6 of 6

Thread: Help with Sort arrays

  1. #1
    Junior Member
    Join Date
    Sep 2009
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Help with Sort arrays

    Hello,

    I have a problem with arrays.

    if i have an array of Integers (EX. Object[] tab = new Object[20];, tab[0] = new Integer(2); )

    is possible to sort array's members with an iterator?

    But i cant use any java defaut structure (school work)

    i need to write a method toArray() that return an array of int in ascending order from an array of integer using an iterator (custom iterator because i cant use the iterator class methods)

    My idea:

    -> sort in ascending order with iterator array's members (tab[])
    -> make a support array of int like int[] arraySup
    -> copy elements to arraySup with intValue() method (i can use this)
    -> return arraySup

    Thanks for the help,

    Best regards.


  2. #2
    Senile Half-Wit Freaky Chris's Avatar
    Join Date
    Mar 2009
    Location
    Wales, Bangor & England, Warwickshire
    Posts
    820
    My Mood
    Cynical
    Thanks
    7
    Thanked 104 Times in 90 Posts

    Default Re: Help with Sort arrays

    Read up on some sorting algorithms, such as Bubble Sort (Easy to implement and understand but slow O(n^2) ) or QuickSort much faster but more complex, there are many

    Sorting algorithm - Wikipedia, the free encyclopedia

    Chris
    chris[at]javaprogrammingforums[dot]com

    Prifysgol Bangor University, North Wales

  3. #3
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Help with Sort arrays

    Bubble sort is NOT easy. Selection sort is err, or maybe insertion sort is. Both are O(n^2) worst case, but insertion sort has a better average case (I don't think it's been proven, but it's best case is O(n)).

    Here's how selection sort works: repeatedly find the min in the un-sorted part and move it to the front.
    ex.:
    4,3,1,5
    min is 1
    1 |^| 4, 3, 5
    min is 3
    1,3 |^| 4, 5
    min is 4
    1,3,4 |^| 5
    min is 5
    1,3,4,5
    done

    Here's an array implementation:
    for (int i = 0; i < needsSorting.length; i++)
    {
         int smallestIndex = i;
         for(int j = i; j < needsSorting.length; j++)
         {
              if(needsSorting[j] < needsSorting[smallestIndex])
              {
                   smallestIndex=j;
              }
         }
         int temp = needsSorting[smallestIndex];
         needsSorting[smallestIndex] = needsSorting[i];
         needsSorting[i] = temp;
    }
    Last edited by helloworld922; September 5th, 2009 at 08:18 PM.

  4. #4
    Junior Member
    Join Date
    Sep 2009
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Help with Sort arrays

    thanks for the help,

    but i need an algorithm for implement the method toArray() of HashSet Class.

    the problem is that my HashSet (custom class, not standard HashSet.java) is implemented with Arrays of int

    Exemple

    Set a = new HashSet();
    a.put(2);

    Can i sort (in ascendig order) HashSet elements with an iterator?

    like this:

    while(hasNext()){
    ...
    ...

    This is an ex of my iter (but i dont know if its ok)

    private class HashSetIter implements Iterator {

    private int pos = 0;

    public boolean hasNext(){

    return pos < nsize; //nsize is a var that contains the number of elements in the HashSet

    public Object next(){
    if(pos < nsize){
    return (int)tabSet[pos++]; //tabSet is the array of int that rapresent my Set
    }else{
    throw new NoSuchElementException();
    }
    }

    public void remove(){
    throw new UnsupportedOperationException();
    }

    }

    But i hate iterators and i dont understand how i can use it.

    Thanks for help,

    best regards (and sorry for my school english )

  5. #5
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Help with Sort arrays

    I wouldn't use hashing to sort elements. Effective data structures for sorting are heaps, and search trees. Arrays aren't too bad either, but hash tables are no good because there is effectively no ordering of elements.

    mmm.. I don't think it's possible for any sorting algorithm to get worst-case of O(n), and that's what your kind of algorithm looks like.

    Do you have to use an iterator? Iterators are useful for linked lists and trees, but aren't too helpful with sorting (usually). I actually can't think of any uses for iterators when it comes to sorting, not to say it isn't possible, but there are much more effective ways to sort.

    In general, I the best running time you'll be able to get without some really advance algorithm is O(nlogn). Algorithms that give this running time are: Quicksort (average speed), MergeSort, Heap sort, and Binary Search Trees (if balanced).

    If you could post the question asked by your teacher, I'd be able to give better advice, but I won't outright give you the answer

  6. The Following User Says Thank You to helloworld922 For This Useful Post:

    drk (September 6th, 2009)

  7. #6
    Junior Member
    Join Date
    Sep 2009
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Help with Sort arrays

    Thank you for the answer.

    There are some advices in my project text:

    -the structure of classes cant be modified
    -the iterators can use support structures
    -the iterators must throw ConcurrentModificationException and NoSuchElementException
    -the method remove() is not implemented
    -Cant use java API structures.

    Implementation of a Set with and array of int with max dimension limited by the free memory.

    This is the interface give to me by teacher

    public interface Set extends Iterable, Cloneable{
    /**
    * Set Empty
    */
    void clear();
    /**
    * is the set empty?
    * @return true if the set is empty, else return false.
    */
    boolean isEmpty();
    /**
    * @return the number of elements inside the Set
    */
    int size();
    /**
    * @return max number of elements inside the set, -1 if the set is empty
    */
    int max();
    /**
    * @param x 
    * @return 
    */
    int nextTrue(int x);
    /**
    * add an int in to the set
    * @param x the int to add.
    * @return true if the int isnt already inside the set, else return falsei
    * @exception IllegalArgumentException if x<0
    */
    boolean put(int x);
    /**
    * 
    * @return true if the int is already inside the set, else return false.
    */
    boolean contains(int x);
    /**
    * remove an int from the set
    * @param x
    * @return true if the int is already inside the set, else return false
    */
    boolean remove(int x);
    /**
    * Convert in String
    * return a string with the elements of Set in ascending order in this form: [ 1 2 3 ]
    * 
    * @return the string
    */
    String toString();
    /**
    * Convert in array
    * return an array of int with the elements of set in ascendig order
    * @return array of int
    */
    int [] toArray();
    /**
    * clone
    * @return a clone of set
    * @throws CloneNotSupportedException
    */
    Object clone() throws CloneNotSupportedException;
    /**
    * return an iterator for iter. the elements in ascending order
    * the method remove isnt implemented
    * @return iterator
    */
    Iterator iterator();
    /**
    * Union
    * add the elements of y in my set
    * @param y the second set
    */
    void union (Insieme y);
    /**
    * Intersection
    * 
    * @param y
    */
    void intersection (Insieme y);
    /**
    * Difference
    *
    * @param y 
    */
    void difference(Insieme y);
    }

    import java.util.*;
     
    public class HashSet implements Set {
     
    final private int address(int x, int l){
    int hash = (new Integer(x)).hashCode();
    return (hash & 0x7FFFFFFF) % l;
     
    public void difference(Set y){
    throw new UnsupportedOperationException();
    }
     
    public void intersection(Set y){
    throw new UnsupportedOperationException();
    }
     
    public int max(){
    throw new UnsupportedOperationException();
    }
     
    public int nextTrue(int x){
    throw new UnsupportedOperationException();
    }
     
    public boolean remove(int x){
    throw new UnsupportedOperationException();
    }
     
    public Object clone(){
    throw new UnsupportedOperationException();
    }
    }

Similar Threads

  1. How to Sort an Array using the java.util.Arrays class
    By JavaPF in forum Java SE API Tutorials
    Replies: 2
    Last Post: May 17th, 2014, 01:16 AM
  2. Replies: 6
    Last Post: October 20th, 2009, 06:33 AM
  3. Insert sort algorithm
    By Alysosh in forum Algorithms & Recursion
    Replies: 1
    Last Post: May 26th, 2009, 09:28 AM
  4. Elegant and short way to implement my program on 2d Array
    By TheForumLord in forum Collections and Generics
    Replies: 1
    Last Post: December 8th, 2008, 03:56 PM
  5. Java error in using Arrays
    By AnithaBabu1 in forum Collections and Generics
    Replies: 4
    Last Post: November 4th, 2008, 06:50 AM