Comb sort
From Algorithm wiki
 Related content:
|
Contents |
[edit] Pseudocode
This section needs your Code!
[edit] C Code
void SWAP('''int''' *a,'''int''' *b)
{
'''int''' tmp = *a;
*a = *b;
*b = tmp;
}
void CombSort(int Tab[],size_t NBElem)
{
'''int''' gap;
for(gap = NBelem;;){
'''int''' swap,i;
gap = (gap * 10 ) /13;
if( gap == 9 || gap == 10 ){
gap = 11;
}
if( gap < 1 ){
gap = 1;
}
for( i = 0,swap = 0 ; i < NBelem-gap ; ++i ){
'''int''' j = gap + i;
if( tab[i] > tab[j] ){
'''SWAP'''(tab[i],tab[j]);
swap = 1;
}
}
if( gap <= 1 && !swap ){
/* already sorted */
break;
}
}
[edit] COBOL Code
IDENTIFICATION DIVISION.
PROGRAM-ID. WSSORT.
****************************************************************** 00
* PROGRAM NAME: WSSORT * 00
* DESCRIPTION: THIS IS AN IMPLEMENTATION OF THE COMB SORT * 00
* ALGORITHM THAT IS DESIGNED TO BE INCLUDED INTO A PARENT * 00
* PROGRAM WITH A COPY STATEMENT AND CALLED. IT WILL SORT * 00
* A WORKING STORAGE TABLE SO IT CAN USE 'SEARCH ALL'. IT IS * 00
* A SIMPLE IMPLEMENTATION THAT WILL SORT A SINGLE KEY STRING *
* INTO ASCENDING ORDER. THIS CAN BE APPLIED AGAINST ANY *
* NUMBER OF TABLES IN WORKING STORAGE. *
*
* PARMS:
* S-REC-LEN - LENGTH OF THE RECORDS.
* S-LST-ENT - NUMBER OF RECORDS TO BE SORTED.
* S-KEY-STR - LOCATION OF THE START OF THE KEY.
* S-KEY-LEN - LENGTH OF THE KEY.
* S-TBL - TABLE TO BE SORTED.
*
* WHEN SPECIFYING THE KEY START, THE FIRST BYTE OF THE RECORD
* IS BYTE ONE (1).
*
* THIS PROGRAM MUST BE ADDED TO THE BOTTOM OF THE CALLING
* PROGRAM WITH A 'COPY' STATEMENT AFTER ALL OTHER EXECUTABLE
* STATEMENTS. THE CALLING PROGRAM MUST INCLUDE AN
* 'END PROGRAM XXXXXXXX' AFTER THE COPY OR THE COMPILER WILL
* FLAG AN ERROR.
*
* IMPORTANT NOTE: THE TABLE MUST HAVE AT LEAST ONE MORE ENTRY
* THAN THE NUMBER OF RECORDS TO BE SORTED. THIS IS USED BY THE
* PROGRAM AS A SWAP ENTRY.
*
* EXAMPLE:
*
* PROGRAM-ID. EXAMPLE.
* DATA DIVISION.
* WORKING-STORAGE SECTION.
* 01 MY-TABLE.
* 05 MY-RECORD OCCURS 257 TIMES.
* 10 MY-REC-D1 PIC X(9).
* 10 MY-REC-KEY PIC X(10).
* 10 MY-REC-D2 PIC X(13).
* 01 REC-LEN PIC 9(08) BINARY VALUE ZERO.
* 01 REC-CNT PIC 9(08) BINARY VALUE ZERO.
* 01 KEY-ST PIC 9(08) BINARY VALUE ZERO.
* 01 KEY-LEN PIC 9(08) BINARY VALUE ZERO.
*
* PROCEDURE DIVISION.
* MOVE 32 TO REC-LEN
* MOVE 257 TO REC-CNT
* MOVE 10 TO KEY-ST
* MOVE 10 TO KEY-LEN
*
* CALL 'WSSORT' USING REC-LEN, REC-CNT, KEY-ST,
* KEY-LEN, MY-TABLE.
*
* COPY WSSORT.
* END PROGRAM EXAMPLE.
****************************************************************** 00
DATA DIVISION.
WORKING-STORAGE SECTION.
01 L PIC 9(08) BINARY
VALUE ZERO.
01 L-OFF PIC 9(08) BINARY
VALUE ZERO.
01 L-KEY PIC 9(08) BINARY
VALUE ZERO.
01 H PIC 9(08) BINARY
VALUE ZERO.
01 H-OFF PIC 9(08) BINARY
VALUE ZERO.
01 H-KEY PIC 9(08) BINARY
VALUE ZERO.
01 SWAP-OFF PIC 9(08) BINARY
VALUE ZERO.
01 GAP PIC 9(08) BINARY
VALUE ZERO.
01 FILLER PIC X(01) VALUE SPACES.
88 NOT-SWAPPED VALUE 'N'.
88 SWAPPED VALUE 'S'.
LINKAGE SECTION.
01 S-REC-LEN PIC 9(08) BINARY.
01 S-LST-ENT PIC 9(08) BINARY.
01 S-KEY-STR PIC 9(08) BINARY.
01 S-KEY-LEN PIC 9(08) BINARY.
01 S-TBL PIC X(16777215) .
PROCEDURE DIVISION
USING S-REC-LEN
S-LST-ENT
S-KEY-STR
S-KEY-LEN
S-TBL.
COMPUTE SWAP-OFF = (S-LST-ENT * S-REC-LEN) + 1
COMPUTE GAP = S-LST-ENT
PERFORM UNTIL NOT SWAPPED AND GAP = 1
SET NOT-SWAPPED TO TRUE
COMPUTE GAP = GAP / 1.3
EVALUATE GAP
WHEN 0
MOVE 1 TO GAP
WHEN 9
WHEN 10
MOVE 11 TO GAP
END-EVALUATE
* FIGURE MY STARTING OFFSETS OUTSIDE THE WORK LOOP.
COMPUTE L-KEY = S-KEY-STR
COMPUTE H-KEY = (GAP * S-REC-LEN) + S-KEY-STR
PERFORM VARYING L FROM 1 BY 1
UNTIL L > (S-LST-ENT - GAP)
IF S-TBL(H-KEY:S-KEY-LEN) < S-TBL(L-KEY:S-KEY-LEN)
SET SWAPPED TO TRUE
COMPUTE L-OFF = (L-KEY - S-KEY-STR) + 1
COMPUTE H-OFF = (H-KEY - S-KEY-STR) + 1
MOVE S-TBL(H-OFF:S-REC-LEN)
TO S-TBL(SWAP-OFF:S-REC-LEN)
MOVE S-TBL(L-OFF:S-REC-LEN)
TO S-TBL(H-OFF:S-REC-LEN)
MOVE S-TBL(SWAP-OFF:S-REC-LEN)
TO S-TBL(L-OFF:S-REC-LEN)
END-IF
ADD S-REC-LEN TO H-KEY
ADD S-REC-LEN TO L-KEY
END-PERFORM
END-PERFORM
* CLEAN UP THE SWAP AREA.
MOVE ALL HIGH-VALUES TO S-TBL(SWAP-OFF:S-REC-LEN)
.
END PROGRAM WSSORT.
[edit] C++ Code
template <typename Type>
void Comb(Type *pF, Type *pL)
{
const float fSHRINK_FACTOR = 1.3f;
bool bSwapped = 1;
for (int h = pL-pF; bSwapped || h > 1;) {
h = (int)( (float)h / fSHRINK_FACTOR );
if (h==9 || h==10) { h=11; }
if (h<1) { h=1; }
bSwapped = 0;
for (Type *pI=pF-1; ++pI + h < pL;) {
if (*(pI+h) < *pI) {
iter_swap(pI+h, pI);
bSwapped = 1;
}
}
}
}
[edit] PHP Code
do{
$bSwapped = 0;
if($gap > 1){
$gap = intval($gap / 1.3);
}
for($j=0; $j < ((Count($array)) - $gap);++$j){
if($array[$j] > $array[$j + $gap]){
$temp = $array[$j];
$array[$j] = $array[$j + $gap];
$array[$j + $gap] = $temp;
$bSwapped = 1;
}
}
}while($gap > 1 and $bSwapped = 1);
[edit] C# Code
This section needs your Code!
[edit] Java Code
public class CombSort <T extends Comparable <? super T>> {
public void Comb(T *pF, Type *pL) {
final float fSHRINK_FACTOR = 1,3;
boolean bSwapped = 1;
for (int h = pL-pF; bSwapped || h > 1;) {
h = (int)( (float)h / fSHRINK_FACTOR );
if (h==9 || h==10)
h=11;
if (h<1)
h=1;
bSwapped = 0;
for (T pI = pF-1; ++pI + h < pL;) {
if ((pI+h) < pI) {
iter_swap(pI+h, pI);
bSwapped = 1;
}
}
}
}
}
[edit] VB Code
Dim S1(L To R) As String
Dim P1(L To R) As Long
Dim L1(L To R) As Long
For I = L To R
S1(I) = GetRandomString()
P1(I) = I
L1(I) = GetRandomLong()
Next I
pCombSortS L, R, S1, P1
CombSortL L, R, L1
' CODE:
Sub CombSortS(L As Long, R As Long, A() As String, P() As Long)
Dim GAP As Long
Dim SWAPPED As Boolean
Dim I As Long
Dim J As Long
Dim TMP As Long
'Initialize GAP to length of list.
GAP = CLng(1 + R - L)
Do
'For each pass, divide GAP by 1.3.
GAP = (10 * GAP) \ 13
'The most efficient series of final GAP values starts with 11.
If GAP = 0 Then
GAP = 1
ElseIf GAP = 9 Or GAP = 10 Then
GAP = 11
End If
'Use SWAPPED to tell whether we made a pass without any exchanges.
SWAPPED = False
'Compare and possibly swap values/pointers separated by GAP.
For I = L To R - GAP
J = I + GAP
If A(P(I)) > A(P(J)) Then
TMP = P(I)
P(I) = P(J)
P(J) = TMP
SWAPPED = True
End If
Next I
'If GAP = 1 and we didn't move anything, we're done.
Loop While SWAPPED Or GAP > 1
End Sub
Sub CombSortL(L As Long, R As Long, A() As Long)
Dim GAP As Long
Dim SWAPPED As Boolean
Dim I As Long
Dim J As Long
Dim TMP As Long
GAP = CLng(1 + R - L)
Do
GAP = (10 * GAP) \ 13
If GAP = 0 Then
GAP = 1
ElseIf GAP = 9 Or GAP = 10 Then
GAP = 11
End If
SWAPPED = False
For I = L To R - GAP
J = I + GAP
If A(I) > A(J) Then
TMP = A(I)
A(I) = A(J)
A(J) = TMP
SWAPPED = True
End If
Next I
Loop While SWAPPED Or GAP > 1
End Sub
[edit] Perl Code
This section needs your Code!
[edit] Prolog Code
This section needs your Code!
[edit] Python Code
This section needs your Code!
[edit] Ruby Code
def comb_sort!(ary)
# comb sort 11
sf = 1.3
gap = (ary.size / sf).to_i
loop do
swaps = 0
for i in 0...(ary.size-gap)
if ary[i] > ary[i+gap]
ary[i], ary[i+gap] = ary[i+gap], ary[i]
swaps += 1
end
end
if gap == 1
break if swaps == 0
else
gap = (gap / sf).to_i
gap = 11 if gap == 9 or gap == 10
end
end
ary
end
[edit] Basic Code
By Dave Stratford
DEF PROC_CombSort11(Size%)
gap%=Size%
REPEAT
IF gap% > 1 THEN
gap%=gap% / 1.3
IF gap%=9 OR gap%=10 gap%=11
ENDIF
I% = 1
Finished%=TRUE
REPEAT
IF data%(I%) > data%(I%+gap%) THEN
SWAP data%(I%),data%(I%+gap%)
Finished% = FALSE
ENDIF
I%+=1
UNTIL I%+gap% > Size%
UNTIL gap%=1 AND Finished%
ENDPROC
