# anybody have a generic algorith to quicksort a linked list?

Discussion in 'OT Technology' started by BaZ, Jul 9, 2003.

1. ### BaZ2004 ACC Champions

Joined:
Jun 12, 2001
Messages:
2,005
0
Location:
Hokieville, USA

2. ### SLEDcustom title

Joined:
Sep 20, 2001
Messages:
28,122
8
i don't have the code handy, but my favorite sorting method was the Shell Sort

3. ### SLEDcustom title

Joined:
Sep 20, 2001
Messages:
28,122
8
here it is in java, should be easy to convert:

Code:
```class ShellSortAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception {
int h = 1;
/*
* find the largest h value possible
*/
while ((h * 3 + 1) < a.length) {
h = 3 * h + 1;
}

/*
* while h remains larger than 0
*/
while( h > 0 ) {
/*
* for each set of elements (there are h sets)
*/
for (int i = h - 1; i < a.length; i++) {
/*
* pick the last element in the set
*/
int B = a[i];
int j = i;
/*
* compare the element at B to the one before it in the set
* if they are out of order continue this loop, moving
* elements "back" to make room for B to be inserted.
*/
for( j = i; (j >= h) && (a[j-h] > B); j -= h) {
if (stopRequested) {
return;
}
a[j] = a[j-h];
pause(i,j);
}
/*
*  insert B into the correct place
*/
a[j] = B;
pause(j);
}
/*
* all sets h-sorted, now decrease set size
*/
h = h / 3;
}
}
}
```

4. ### SLEDcustom title

Joined:
Sep 20, 2001
Messages:
28,122
8
there is always the good 'ole quick sort too:

Code:
```class QSortAlgorithm extends SortAlgorithm {
void sort(int a[], int lo0, int hi0) throws Exception {
int lo = lo0;
int hi = hi0;
pause(lo, hi);
if (lo >= hi) {
return;
}
else if( lo == hi - 1 ) {
/*
*  sort a two element list by swapping if necessary
*/
if (a[lo] > a[hi]) {
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
}
return;
}

/*
*  Pick a pivot and move it out of the way
*/
int pivot = a[(lo + hi) / 2];
a[(lo + hi) / 2] = a[hi];
a[hi] = pivot;

while( lo < hi ) {
/*
*  Search forward from a[lo] until an element is found that
*  is greater than the pivot or lo >= hi
*/
while (a[lo] <= pivot && lo < hi) {
lo++;
}

/*
*  Search backward from a[hi] until element is found that
*  is less than the pivot, or lo >= hi
*/
while (pivot <= a[hi] && lo < hi ) {
hi--;
}

/*
*  Swap elements a[lo] and a[hi]
*/
if( lo < hi ) {
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
pause();
}

if (stopRequested) {
return;
}
}

/*
*  Put the median in the "center" of the list
*/
a[hi0] = a[hi];
a[hi] = pivot;

/*
*  Recursive calls, elements a[lo0] to a[lo-1] are less than or
*  equal to pivot, elements a[hi+1] to a[hi0] are greater than
*  pivot.
*/
sort(a, lo0, lo-1);
sort(a, hi+1, hi0);
}

void sort(int a[]) throws Exception {
sort(a, 0, a.length-1);
}
}

```

5. ### BaZ2004 ACC Champions

Joined:
Jun 12, 2001
Messages:
2,005
0
Location:
Hokieville, USA
i know the algorithm for quick sort, i was just wondering if anybody had altered it for quick sort. i tried overloading the bracket operators but that didnt work and was the only way i could think to do it

Joined:
Jun 12, 2001
Messages:
2,005