5 Replies - 12335 Views - Last Post: 15 November 2006 - 11:41 PM Rate Topic: -----

#1 yaeli_17  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 09-October 06

inserting a new element into a sorted array

Posted 15 November 2006 - 01:14 PM

I am having difficulty with a question in an assignment.

in the class, we are managing booklists objects. which are essentially arrays that hold book objects (book class is given to us).

we are supposed to write an insert() class where i need to insert a book into the array, and i already have a method which compares the book to the others and gives me a positive, 0, or negative number if the book is after, in the position, or before the book it is being compared to respectively.
(and the list is already sorted alphabetically so i don't need to do sort it).

the problem i have is actually inserting the book in the required position and "pushing" all the other books forward one space in the array.
the other problem is that once the array is full i need to transfer everything to a bigger array - twice it's size..

and of course - we're ment to do this without using arrayList, but normal arrays.

any help with this will be GREATLY apreciated.

i wrote a single line and don't know where to go from there.
i'm completely new in programming

 public void insert(Book book) {
		
		for (int i = 0; i < book.compareTo(bookList[i]); i++) 


Is This A Good Question/Topic? 0
  • +

Replies To: inserting a new element into a sorted array

#2 horace  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 291
  • View blog
  • Posts: 1,900
  • Joined: 25-October 06

Re: inserting a new element into a sorted array

Posted 15 November 2006 - 02:22 PM

(1) to insert a book at element bookList[i] and you have number books in the array you need a loop from number downto i moving the elements one place up the array, i.e. bookList[number] to bookList[number+1] until you move bookList[i] to bookList[i+1]. You then insert the new book at bookList[i]

(2) to extend the size of the array you create a temporyarray twice the size,e.g.
book temp[] = new Book[size*2];
copy the contents of booklist[] to temp[]
assign bookList to temp, e.g.
bookList=temp;

remember bookList stores a reference (a pointer inC/C++) to an array so bookList now references the new Book[size*2] array - the old Book array would be garbage collected if nothing else references it
Was This Post Helpful? 0
  • +
  • -

#3 yaeli_17  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 09-October 06

Re: inserting a new element into a sorted array

Post icon  Posted 15 November 2006 - 02:30 PM

thanks for your reply.

i still am not sure how to do the inserting part :(
but i think i have an idea of how to create a larger array, store the old one in it, and point to it.

would this work?
(count is the number of book objects in the array)

if (count == bookList.length)
			{
				Book[] temp = new Book[bookList.length * 2];
				
				for (int book = 0; book < bookList.length; book++)
					temp[book] = bookList[book];
				
				bookList = temp;
			} 

Was This Post Helpful? 0
  • +
  • -

#4 horace  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 291
  • View blog
  • Posts: 1,900
  • Joined: 25-October 06

Re: inserting a new element into a sorted array

Posted 15 November 2006 - 02:46 PM

looks OK - test it by printing bookList.length and the array contents to make sure the copy is OK
Was This Post Helpful? 0
  • +
  • -

#5 yaeli_17  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 09-October 06

Re: inserting a new element into a sorted array

Posted 15 November 2006 - 03:15 PM

for the insertion part, i need to have an int to keep track of the index. but how do i get the index where i'm ment to insert the element, if i'm not allowed to use binary search.

i know i need to use the fact that they're already sorted but...
:huh:
i'm completely stuck :(

	public void insert(Book book) {
		
		if (bookList.isEmpty() == true)
			bookList[0] = book;
		else
		{
		
		for (int i = 0; i < count; i++)
		{
			if (i < book.compareTo(bookList[i]) 

Was This Post Helpful? 0
  • +
  • -

#6 horace  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 291
  • View blog
  • Posts: 1,900
  • Joined: 25-October 06

Re: inserting a new element into a sorted array

Posted 15 November 2006 - 11:41 PM

the array bookList must have been sorted acording to some criteria (book title, author, ISBN number) - you would go thru the bookList array until you find the index where the new book is to be inserted, call it i

if you have count books in the array the algorithm would be something like
loop j from count downto i 
  bookList[j+1] = bookList[j] 
bookList[i]= new Book


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1