Thread: Sorting Arrays and Counting the Number of Swaps

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

Hi!

This exercise supposes that it is you who should write the solution, not anyone else. So you'd better try.

Have you already written BubbleSort yourself? I think after you do this, the rest will be obvious to you.

You can see the short explanation of the simplified BubbleSort version here:
Bubble Sort - CodeAbbey
And by the way here is the task exactly about counting swaps, so you can check your answers online.

If you think it is hard to catch the whole bubblesort algorithm at once in the mind, see the following page:
Bubble in Array - CodeAbbey
Here is the description of "one step" of the bubble sort. You only need to repeat such steps until you find that last step gives no swaps at all.

I have the code for a bubble sort but I don't know how to code for it to count the number of swaps?

If I can see an example of a program even similar to the 2nd question I would understand more. Our book is more like a short print out and there isn't a whole lot of explanation. I'm feeling lost.

I have the code for a bubble sort but I don't know how to code for it to count the number of swaps?

Just close this code and try to rewrite it yourself, using your hands and your head.

If I can see an example of a program even similar to the 2nd question I would understand more.

You can not master programming by begging for code. You could not learn just looking at the code. You really need to write the code yourself.

And believe, this task is not hard.

I think by "module" you mean "method" in Java. If not, please clarify. It's important to use the correct terms so that we understand the task and can help you appropriately.

For counting the number of swaps, since swapping is an important part of most sort algorithms, you may have a separate method for swapping two elements in an array, something like the following signature that will swap the elements at index1 and index2 in the int[] array, 'myArray':

public void swapElements( int[] myArray, int index1, int index2 )

If that's the case, simply add a counter, say numberOfSwaps, to the swap method that increments each time a swap is made. Remember to check and then reset the swap counter between each sort algorithm.

Thank you for the links they are definitely helpful. Trying to learn on my own and it's pretty hard to piece things together. I'm not a college student I'm an adult trying to teach myself. With absolutely no programming background. So what seems 'easy' for other programmers to just figure out is quite a challenge for me as this is an entirely new topic. Note taking an intro course.

I get all kinds of attitude I'm surprised by on forums when I do ask a question as if people are too good to work with a beginner. People have up to 75 different learning styles and I am definitely visual and hands-on equally. I try to find some examples to lead me working through the book first then try the hands on.

When it doesn't make sense to me I ask, it's the only way I'll learn. Because staring at it won't make me 'get it' as osmosis hasn't worked for me yet and at 35 I know what I need to learn something.

--- Update ---

I do mean method. The programming logic book is a broad generalization on all programs I am trying to apply this to learning Java.

--- Update ---

I'm not sure why you're being an ass. But I'm not begging for anything. I'm glad you don't think this is hard this is probably what you do for a living where I have zero background or experience in this and trying to learn something new.

You win the prize for trying to make people feel like shit.


public class SortingComp{

public static void main(String Args[]){
int num1[] = { 26,45,56,12,78,74,39,22,5,90,87,32,28,11,93,62,79, 53,22,51 };
int num2[] = { 26,45,56,12,78,74,39,22,5,90,87,32,28,11,93,62,79, 53,22,51 };
int num3[] = { 26,45,56,12,78,74,39,22,5,90,87,32,28,11,93,62,79, 53,22,51 };
int bubsortcomp = bubble_srt(num1,num1.length);
int selcomp = selection_srt(num2,num2.length);
int inscomp = insertion_srt(num3,num3.length);
System.out.println("Number of comparison in Bubble Sort " + bubsortcomp);
System.out.println("Number of comparison in Selection Sort " + selcomp );
System.out.println("Number of comparison in Insertion Sort " + inscomp );
}



public static int bubble_srt( int a[], int n ){
int i, j,t=0;
int numswaps =0;
for(i = 0; i < n; i++){
for(j = 1; j < (n-i); j++){
if(a[j-1] > a[j]){
numswaps++;
t = a[j-1];
a[j-1]=a[j];
a[j]=t;
}
}
}
return numswaps;
}
public static int selection_srt(int array[], int n){
int numswaps = 0;
for(int x=0; x<n; x++){
int index_of_min = x;
for(int y=x; y<n; y++){
if(array[index_of_min]<array[y])
index_of_min = y;
}
int temp = array[x];
array[x] = array[index_of_min];
array[index_of_min] = temp;
numswaps ++;
}
return numswaps;
}

public static int insertion_srt(int array[], int n){
// no swaps in insertion sort shifting based on comparison
int comp = 0;
for (int i = 1; i < n; i++){
int j = i;
int B = array[i];
while ((j > 0) && (array[j-1] > B)){
comp++;
array[j] = array[j-1];
j--;
}
array[j] = B;
}
return comp;
}
}

And if you are going to hurl abuse at people, you should be sure to indicate at whom the abuse is thrown. I'll assume you were complaining at rodiongork, so I won't cross you off my Christmas list, but you move to the bottom. A better way to handle posts you don't find helpful is to ignore them. Assaults and abuse directed at any will alienate you with all. A bad reputation on social/professional forums like this one is hard to recover from, unfruitful (unless you count negative effects), and unnecessary.

Good luck!

These are frustrated students you're interacting with. Give 'em a break. You're a professional who spends ALL DAY thinking about this after years of practicing it. Imagine working full-time and going to school full-time in pursuit of a Comp Sci degree purely online with ZERO understanding of programming until 2-months ago. That's me! I don't say this for pity, but just to seek some empathy from the pros.

Sometimes we get stuck and have NO frame of reference to trouble-shoot from. We're looking for hints, for tips, for understanding, for an explanation I hadn't heard, an EXAMPLE (not the answer, an example), for a new brain to bounce ideas off of. We are not looking for links. We don't want to spend 3-more hours READING about a subject that we've already spent three hours reading about and another three hours coding a solution for that is still failing and finally we give up and ask for help from the inter-webs.

I use these forums as a last resort. Perhaps you all are just sick of first-resort homework seekers. But try to imagine yourself alone, confused, pulling your hair out with no classroom to help you when you imagine the posters on these forums. Because most of us are not just seeking answers, we're seeking understanding.

Sorry for the rant. It just bugs me to see how condescending the "professionals" are toward the students. I can't wait to work side-by-side with such nasty and inconsiderate people! I'll be promoted over them within weeks

Thread strayed off topic and should have died a quiet death.

Thread closed.