Cocktail sort
From Algorithm wiki
 Related content:
|
Contents |
[edit] Pseudocode
This section needs your Code!
[edit] C Code
[edit] char *
void shaker(char *items, int count) {
register int i;
int exchange;
char t;
do {
exchange = 0;
for(i = count - 1; i > 0; --i) {
if(items[i - 1] > items[ i ]) {
t = items[i - 1];
items[i - 1] = items[ i ];
items[ i ] = t;
exchange = 1;
}
}
for(i = 1; i < count; ++i) {
if(items[i - 1] > items[ i ]) {
t = items[i-1];
items[i - 1] = items[ i ];
items[ i ] = t;
exchange = 1;
}
}
} while(exchange); /* sort until no exchanges */
}
[edit] C++ Code
template <typename Type> inline
void CocktailShaker(Type *pF, Type *pL)
{
Type *pShift = pF;
Type *pI;
while (pF < pL) {
for (pI=pF; ++pI<pL;) { // [pShift, pL)
if (*pI < *(pI-1)) {
iter_swap(pI, pI-1);
pShift = pI;
}
}
pL = pShift;
for (pI=pL; --pI>pF;) { // (pShift, pF]
if (*pI < *(pI-1)) {
iter_swap(pI, pI-1);
pShift = pI;
}
}
pF = pShift;
}
}
[edit] PHP Code
function shaker(&$items) {
$t='';
$count = count($items);
$exchange = 0;
do {
$exchange = 0;
for($i = $count - 1; $i > 0; --$i) {
if($items[$i - 1] > $items[$i]) {
$t = $items[$i - 1];
$items[$i - 1] = $items[$i];
$items[$i] = $t;
$exchange = 1;
}
}
for($i = 1; $i < $count; ++$i) {
if($items[$i - 1] > $items[$i]) {
$t = $items[$i-1];
$items[$i - 1] = $items[$i];
$items[$i] = $t;
$exchange = 1;
}
}
} while($exchange);
}
[edit] C# Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CocktailSort
{
class Cocktail
{
/// <summary>
/// o(n^2) not better then max sort
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
int[] array = new int[5] {5,2,18,4,1 };
int temp = 0;
int index = 1;
int swap = 0;
int search = 0;
for (int i = 0; i < array.Length-1; i++)
{
if (array[i] > array[index])
{
int big = array[i];
array[i] = array[index];
array[index] = big;
swap++;
}
search++;
index++;
for (int j = array.Length-1; j > 0; j--)
{
if (array[j] > array[j-1])
{
int big = array[j];
array[j] = array[j - 1];
array[j - 1] = big;
swap++;
}
search++;
}
}
for (int i = 0; i < array.Length; i++)
{
Console.WriteLine(array[i]);
}
Console.WriteLine("number of swaps: " + swap);
Console.WriteLine("number of search: " + search);
}
}
}
[edit] Java Code
class CocktailSort
{
private Integer[] list;
private void cocktail_sort()
{
/*Performs a bi-directional bubble sort on "list", also known as a cocktail
sort. After making bubbling from left to right, the algorithm then bubbles
from right to left.*/
int beg = 0; //Beginning index for the left-to-right pass
int end = list.length - 1;//End index for the left-to-right pass
Integer tmp = null;//Temporary variable for swapping
boolean hasSwapped = false;//Denotes whether a swap was made during a pass
do
{
hasSwapped = false;
//Bubble sort from left-to-right starting at beg and ending at end
for (int i = beg;i < end;++i)
{
if (list[i] > list[i + 1])
{
tmp = list[i];
list[i] = list[i + 1];
list[i + 1] = tmp;
hasSwapped = true;
}
}
--end; //Decrease end by one
//Bubble sort from right-to-left starting at end and ending at beg
for (int i = end;i > beg;--i)
{
if (list[i] < list[i - 1])
{
tmp = list[i];
list[i] = list[i - 1];
list[i - 1] = tmp;
hasSwapped = true;
}
}
++beg; //Increment beg by one
} while ((hasSwapped == true) && (beg != end)); //While no swaps have been made
}
public Integer[] Sort(Integer[] unsorted)
{
/*Initializes list to the passed unsorted list, and then invokes
the cocktail sort algorithm on that list. The resulting sorted
list will then be returned*/
list = unsorted;
cocktail_sort();
return list;
}
public CocktailSort()
{
/*Default constructor*/
list = null;
}
}
[edit] VB Code
This section needs your Code!
[edit] Perl Code
This section needs your Code!
[edit] Prolog Code
This section needs your Code!
[edit] Python Code
def CocktailSort( Array_List ):
swapped = True
begin = -1
end = len(Array_List)
while (swapped):
swapped = False
begin += 1
for i in range(begin, end - 1):
if(Array_List[i] > Array_List[i + 1]):
swapped = True
Array_List[i] += Array_List[i + 1]
Array_List[i + 1] = Array_List[i] - Array_List[i + 1]
Array_List[i] = Array_List[i] - Array_List[i + 1]
if (not swapped):
break;
end -= 1
swapped = False
for i in range(end - 1, begin - 1, -1):
if(Array_List[i] > Array_List[i + 1]):
swapped = True
Array_List[i] += Array_List[i + 1]
Array_List[i + 1] = Array_List[i] - Array_List[i + 1]
Array_List[i] = Array_List[i] - Array_List[i + 1]
[edit] Ruby Code
def cocktail_sort(ary)
left, right = 0, ary.size-1
while left < right
last_swap = right
(right-1).downto(left) do |i|
if ary[i]>ary[i+1]
ary[i], ary[i+1] = ary[i+1], ary[i]
last_swap = i
end
end
left = last_swap + 1
left.upto(right-1) do |i|
if ary[i]>ary[i+1]
ary[i], ary[i+1] = ary[i+1], ary[i]
last_swap = i
end
end
right = last_swap
end
end
[edit] Pascal/Delphi Code
procedure CocktailSort(var A:array of double);
Var
i: Integer;
z: Double;
swapped: boolean;
begin
repeat
swapped := false;
for i:=low(A) to high(A)-1 do
begin
if(A[i] > A[i+1])then
begin
z := A[i];
A[i] := A[i+1];
A[i+1] := z;
swapped := true;
end;
end;
for i:=high(A)-1 downto low(A) do
begin
if(A[i] > A[i+1])then
begin
z := A[i];
A[i] := A[i+1];
A[i+1] := z;
swapped := true;
end;
end;
until swapped = false;
end;
[edit] Basic Code
By Dave Stratford
DEF PROC_ShakerSort(Size%)
Start%=2
End%=Size%
Direction%=1
LastChange%=1
REPEAT
FOR J% = Start% TO End% STEP Direction%
IF data%(J%-1) > data%(J%) THEN
SWAP data%(J%-1),data%(J%)
LastChange% = J%
ENDIF
NEXT J%
End% = Start%
Start% = LastChange% - Direction%
Direction% = Direction% * -1
UNTIL ( ( End% * Direction% ) < ( Start% * Direction% ) )
ENDPROC
