Archived

This topic is now archived and is closed to further replies.

Pfhorseti

Help! Weird sorting error...

Recommended Posts

Hi, I''m doing my homework for school, and I''m stuck with this strange error it gives me... although data.length is 2000, the algorithm makes insane number of comparisons and swaps. The code is written in java... if anyone can see what''s wrong with it, please post! I''ve been stuck with this for a few hours now. Here''s the code: import java.util.*; import java.util.Random; public class Sort { static int NUM_ELEM = 2000; public static void main (String args[]) { Random randGen = new Random(); int[] numbers = new int[NUM_ELEM]; for(int i = 0; i < NUM_ELEM; i++) numbers = Math.abs(randGen.nextInt() % NUM_ELEM + 1); SortClass sort = new SortClass(numbers, NUM_ELEM); sort.bubbleSort(); System.out.println("bubbleSort - " + "compCounter: " + sort.getCompCounter() + " swapCounter: " + sort.getSwapCounter()); sort.selectionSort(); System.out.println("selectionSort - " + "compCounter: " + sort.getCompCounter() + " swapCounter: " + sort.getSwapCounter()); sort.insertionSort(); System.out.println("insertionSort - " + "compCounter: " + sort.getCompCounter() + " swapCounter: " + sort.getSwapCounter()); } } public class SortClass { private int[] data; private int size; // Actual size of array. private int swapCounter; private int compCounter; static boolean COUNT = true; public SortClass(int[] newData, int newSize) { data = newData; size = newSize; } /*-----------------------------------------------------------------------------* Method: bubbleSort A sorting algorithm with time complexity O(N^2). *-----------------------------------------------------------------------------*/ public void bubbleSort() { int i, j; swapCounter = 0; // Counts the number of swaps. compCounter = 0; // Counts the number of comparisons. for(i = 0; i < size - 1; i++) for(j = size - 1; j > i; j--) { if(COUNT) compCounter++; if(data[j - 1] > data[j]) { swap(j, j - 1); // Data doesn''t have to be passed because of PIV. if(COUNT) swapCounter++; } } } /*-----------------------------------------------------------------------------* Method: selectionSort A sorting algorithm with time complexity O(N^2). *-----------------------------------------------------------------------------*/ public void selectionSort() { int i, j; int minSub; swapCounter = 0; // Counts the number of swaps. compCounter = 0; // Counts the number of comparisons. for(i = 0; i < size - 1; i++) { minSub = i; for(j = i + 1; j < size; j++) { if(COUNT) compCounter++; if(data[j] < data[minSub]) minSub = j; } swap(i, minSub); if(COUNT) swapCounter++; } } /*-----------------------------------------------------------------------------* Method: insertionSort A sorting algorithm with time complexity O(N^2). *-----------------------------------------------------------------------------*/ public void insertionSort() { int i, j; int value; swapCounter = 0; // Counts the number of swaps. compCounter = 0; // Counts the number of comparisons. for( i = 1; i < size; i++) { value = data[i]; j = i; if(COUNT) compCounter++; while( j <= 1 && data[j - 1] > value) { data[j] = data[j - 1]; j--; } } } /*-----------------------------------------------------------------------------* Method: swap Swaps the two elements in data. *-----------------------------------------------------------------------------*/ public void swap(int firstSub, int secondSub) { int temp; temp = data[firstSub]; data[firstSub] = data[secondSub]; data[secondSub] = temp; } public void setData(int[] newData) { data = newData; } public int[] getData() { return data; } public void setSize(int newSize) { size = newSize; } public int getSize() { return size; } public int getSwapCounter() { return swapCounter; } public int getCompCounter() { return compCounter; } } And here''s the output (run on Project Builder, OS X) bubbleSort - compCounter: 1999000 swapCounter: 1003013 selectionSort - compCounter: 1999000 swapCounter: 1999 insertionSort - compCounter: 1999 swapCounter: 0 java has exited with status 0. Since data[] contains random numbers, the output here can vary. Nonetheless it still returns insane number of comparisons and swaps. -Pfhor

Share this post


Link to post
Share on other sites
Its a long while since I learnt sorts, but the bubble sort comparision is correct as far as I can see.

Its the most inefficant sort there is, it move the lowest number to the bottom from (0-2000) then moves the lowest number to the bottom from (1-2000) and so on.... until (1999-2000) when it finishes.

Getting a huge number of comparisions is normal.

,Jay


Share this post


Link to post
Share on other sites
The comments for your bubbleSort read:
Method: bubbleSort

A sorting algorithm with time complexity
O(N^2).


In this case, N is 2000 (N generally refers to how many objects you have to sort/perform the algorithm on). N^2 is 4,000,000, so you''re still fine if you''re under that.

Share this post


Link to post
Share on other sites