Sorting Algorithms

 DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Nov 2005
Posts
1

## Sorting Algorithms

Hi, im trying to compare the runtime of 2 algorithms (an insertion sort algorithm and a quicksort algorithm), i've done the code for them correct i think but im having some problems..

The code for the Insertion Sort:

Code:
```public class InsertionSortAlgorithm
{

public static void insertionSort(int[] arrayData, int numberItems)
{
for(int i=0;i<numberItems - 1;i++)
{
int j = i - 1;
int item = arrayData[i];

while (j >= 0 && arrayData[j] > item)
{
arrayData[j + 1] = arrayData[j];
j = j - 1;
}
arrayData[j + 1] = item;

}
}
}```
Code for Quick Sort:

Code:
```public class QuickSortAlgorithm
{

public static int[] quickSort(int[] list, int lower, int upper)
{
if (upper > lower)
{
int j = partition(list,lower,upper);
quickSort(list,lower,j-1);
quickSort(list,j+1,upper);

}
return list;
}
public static int partition(int[] list, int lower, int upper)
{
int i = lower;
int j = upper + 1;
int v = list[lower];
int t, t2;

do{
do{
i = i + 1;
}
while (list[i] < v);

do {
j = j - 1;
}
while (list[j] > v);

if (i < j){

t = list[i];
t2 = list[j];
list[j] = t;
list[i] = t2;
}
}

while (i<j);

t = list[lower];
t2 = list[j];
list[i] = t;
list[lower] = t2;

return j;
}
}```
Code to run each algorithm:

Code:
```public class ArrayData
{

private int[] data;
private int numberItems = 10000;

public static void main(String args[])
{
ArrayData myData = new ArrayData();

}

public ArrayData()
{

data = new int[numberItems];

long start1 = System.currentTimeMillis();

for (int i=0;i<numberItems;i++)
{
data[i] = (int) (Math.random() * 1000);

}

for( int j =0; j < 10; j++){

long start = System.currentTimeMillis();

int[] a =  QuickSortAlgorithm.quickSort(data, 0, numberItems - 1);

long end = System.currentTimeMillis();

long time = end - start;

System.out.println(time + "ms");

}

long start2 = System.currentTimeMillis();
System.out.println("Total time: " + (start2 - start1) + " ms");

}
}
/* public void output()
{
for (int i=0;i<numberItems;i++)
{

System.out.println(data[i]);

}

} */

/*public void algorithmTimer()
{
long start = System.currentTimeMillis();

QuickSortAlgorithm.quickSort(data, 0, numberItems - 1);

long end = System.currentTimeMillis();

long time = end - start;

System.out.println(time + "ms");

}
}

/*	public void algorithmTimer()
{
long start = System.currentTimeMillis();

InsertionSortAlgorithm.insertionSort(data, numberItems);

long end = System.currentTimeMillis();

long time = end - start;

System.out.println(time + "ms");

}
} */```
Basically those 2 algorithms are in their own seperate classes and using the 3rd class ArrayData im calling them and timing the results of arrays of random integers. The insertion sort algorithm works fine i think.. but the quick sort im having problems with.. something about stack overflows.. it all compiles fine so im not sure whats wrong.. if anybody could help me out here would be appreciated.

Thanks,

Sandy

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
Walk your way through the execution of your code, watching how i and j walk toward each other. You should see that the place you want to put your "partition value" is actually one index past where j ended up - j and i have walked PAST each other and j needs to backtrack one to be at the index where the partition value should be inserted.

So, swap your list[lower] with the value at list[j+1]; and then return j+1. You should stop having your stack overflows then.

[In earlier versions of this post I got lost with the formatting and I'm just not used to the do - while structure. I didn't clear up my confusion until I reconstructed the code with the formatting I'm used to ...]
Last edited by nspils; 11-14-2005 at 09:54 AM.

3. Registered User
Join Date
Sep 2005
Location
istanbul / Turkey
Posts
133
i tried to correct it , do-while loops were wrong.
Code:
```class QuickSortAlgorithm {
public static int[] quickSort(int[] list, int lower, int upper) {
if (upper > lower) {
int j = partition(list, lower, upper);
quickSort(list, lower, j);
quickSort(list, j == lower ? (j + 1) : j , upper);
}
return list;
}

public static int partition(int[] list, int lower, int upper) {
int i = lower;
int j = upper;
int v = list[lower];
int t, t2;
do {
while ( (i < j) && (list[i] < v)) {
i = i + 1;
}

while ( (j > i) && (list[j] >= v)) {
j = j - 1;
}

if (i < j) {
t = list[i];
t2 = list[j];
list[j] = t;
list[i] = t2;
}
}
while (i < j);
return j;
}
}```

4. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
You left out swapping your original (for each call to the sort procedure) list[lower] ( which you've stored as v) with the value at list[j+1]; and then return j+1, rather than j.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise