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.

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

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:

Code :

---

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

---

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 :P )

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

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

Code :

---

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

---

Code :

---

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

---