• Post Reply Bookmark Topic Watch Topic
  • New Topic

Sorting Arrays and Keeping Count of the Swaps  RSS feed

 
Aundra Thompson
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I need to modify modules used in the book that run a bubble sort, selection sort, and insertion sort on an integer array such that each module keeps a count of the number of swaps it makes.

How do I code for this?


Then we have to design an application that uses 3 identical arrays of at least 20 integers. That calls each module on a different array, and display the number swaps made by each algorithm.



Beginner course, Using Programming Logic and Design by Tony Gaddis (3rd Ed.) - Chapter 9
 
Paweł Baczyński
Bartender
Posts: 2077
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It is simple. Declare a variable of type int. Whenever a swap occurs increment this variable.
 
Aundra Thompson
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you I must have just been having a mental block last night after too many hours studying. Most appreciated!
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pawel Pawlowicz wrote:It is simple. Declare a variable of type int. Whenever a swap occurs increment this variable.
Agree, but for a large array you will suffer an overflow, so use a long instead.
 
Paweł Baczyński
Bartender
Posts: 2077
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I agree. AFAIK bubble sort has n^2 worst case complexity. So it might overflow on an array larger than 46340 elements (sqrt(2^31-1)).
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Last time I tried counting bubble sort, I found it used (n² - n) ÷ 2 comparisons.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!