Help! Weird sorting error...
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;
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
</i>
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
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
The comments for your bubbleSort read:
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.
Method: bubbleSortA sorting algorithm with time complexityO(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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement