Blanda sortering
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från
versionen som granskades den 11 januari 2018; kontroller kräver
28 redigeringar .
Blanda sortering , eller Shaker sort , eller dubbelriktad ( eng. Cocktail sort ) är en sorts bubbelsortering . När man analyserar bubblesorteringsmetoden kan två saker noteras.
För det första , om inga permutationer inträffar när man rör sig genom en del av arrayen, är denna del av arrayen redan sorterad och därför kan den uteslutas från övervägande.
För det andra , när man flyttar från slutet av arrayen till början, "flyter" minimielementet till den första positionen, och det maximala elementet flyttas endast en position åt höger.
Dessa två idéer leder till följande modifieringar av bubblesorteringsmetoden. Gränserna för den arbetande delen av arrayen (det vill säga den del av arrayen där rörelse sker) sätts vid platsen för den sista växlingen vid varje iteration. Arrayen skannas växelvis från höger till vänster och från vänster till höger.
#include <iostream>
#inkludera <vektor>
#inkludera <ctime>
tomrumsfyllning ( std :: vektor < int > & arr ) {
för ( storlek_t i = 0 ; i < arr . storlek (); ++ i ) {
arr [ i ] = static_cast < int > ( rand () % 100 );
std :: cout << arr [ i ] << " " ;
}
std :: cout << std :: endl ;
}
void shakerSort ( std :: vektor < int >& arr ) {
int kontroll = arr . storlek () - 1 ;
int vänster = 0 ;
int höger = arr . storlek () - 1 ;
gör {
for ( int i = vänster ; i < höger ; i ++ ) {
if ( arr [ i ] > arr [ i + 1 ]) {
std :: swap ( arr [ i ], arr [ i + 1 ]);
kontroll = i ;
}
}
höger = kontroll ;
for ( int i = höger ; i > vänster ; i -- ) {
if ( arr [ i ] < arr [ i - 1 ]) {
std :: swap ( arr [ i ], arr [ i - 1 ]);
kontroll = i ;
}
}
vänster = kontroll ;
} while ( vänster < höger );
}
int main ()
{
const int N = 20 ;
std :: vektor < int > arr ;
arr . reserv ( N );
för ( int i = 0 ; i < N ; i ++ )
arr . pushback ( 0 );
srand ( tid ( 0 ));
fyllning ( arr );
shakerSort ( arr );
for ( int i = 0 ; i < arr . storlek (); i ++ ) {
std :: cout << arr [ i ] << " " ;
}
arr . rensa ();
std :: cin . ignorera ();
}
använder System ;
namnutrymme SortLab
{
class Program
{
static void Main ()
{
Sort ();
}
/*Huvudprogram*/
static void Sortera ()
{
int [] myint = { 99 , 88 , 77 , 66 , 55 , 44 , 33 , 22 , 11 , 8 , 5 , 3 , 1 };
WriteArray ( myint );
ShakerSort ( myint );
WriteArray ( myint );
Konsol . ReadLine ();
}
/* Shaker sort */
static void ShakerSort ( int [] myint )
{
int left = 0 ,
right = myint . Längd - 1 ,
antal = 0 ;
while ( vänster < höger )
{
for ( int i = vänster ; i < höger ; i ++)
{
räkna ++;
if ( myint [ i ] > myint [ i + 1 ])
Swap ( myint , i , i + 1 );
}
höger --;
for ( int i = höger ; i > vänster ; i --)
{
räkna ++;
if ( myint [ i - 1 ] > myint [ i ])
Swap ( myint , i - 1 , i );
}
vänster ++;
}
Konsol . WriteLine ( "\nAntal jämförelser = {0}" , count . ToString ());
}
/* Swap element */
static void Swap ( int [] myint , int i , int j )
{
int glass = myint [ i ];
myint [ i ] = myint [ j ];
myint [ j ] = glas ;
}
/*Output array*/
static void WriteArray ( int [] a )
{
foreach ( int i in a )
Console . Skriv ( "{0}|" , i .ToString ( ));
Konsol . WriteLine ( "\n\n\n" );
}
}
}
function shakerSort ( array ) {
låt vänster = 0 ; // start av array
låt höger = array . längd - 1 ; // slutet av array
while ( vänster < höger ) {
for ( låt i = vänster ; i < höger ; i ++ ) {
if ( array [ i ] > array [ i + 1 ]) {
[ array [ i ], array [ i + 1 ]] = [ array [ i + 1 ], array [ i ]]
}
}
höger -- ;
for ( låt i = höger ; vänster < i ; i -- ) {
if ( array [ i ] < array [ i - 1 ]) {
[ array [ i ], array [ i - 1 ]] = [ array [ i - 1 ], array [ i ]]
}
}
vänster ++ ;
}
returnera array ;
}
function cocktailSorting ( & $a ) {
$n = count ( $a );
$left = 0 ;
$höger = $n - 1 ;
gör {
for ( $i = $left ; $i < $right ; $i ++ ) {
if ( $a [ $i ] > $a [ $i + 1 ]) {
list ( $a [ $i ], $a [ $i + 1 ]) = array ( $a [ $i + 1 ], $a [ $i ]);
}
}
$right -- ;
för ( $i = $höger ; $i > $vänster ; $i -- ) {
if ( $a [ $i ] < $a [ $i - 1 ]) {
list ( $a [ $i ], $a [ $i - 1 ]) = array ( $a [ $i - 1 ], $a [ $i ]);
}
}
$vänster ++ ;
} while ( $left <= $right );
}
ELLER
function FunctionCoocktailSort ( & $array )
{
$leftItem = 0 ;
$rightItem = count ( $array ) - 1 ;
for ( $i = $leftItem ; $i < $rightItem ; $i ++ ) {
for ( $j = $leftItem ; $j < $rightItem ; $j ++ ) {
if ( $array [ $j ] > $ array [ $j + 1 ]) {
FunctionSwapVariables ( $array [ $j ], $array [ $j + 1 ]);
}
}
$rightItem -- ;
för ( $j = $rightItem ; $j > $leftItem ; $j -- ) {
if ( $array [ $j ] < $array [ $j - 1 ]) {
FunctionSwapVariables ( $array [ $j ], $array [ $j - 1 ]);
}
}
}
}
public static void main ( String [] args ) {
fillArray ( arr );
shakerSort ( arr );
System . ut . println ( Arrays . toString ( arr ));
}
private static void fillArray ( int arr [] ) {
for ( int i = 0 ; i < arr . längd ; i ++ ) {
arr [ i ] = ( int ) ( Matte . slumpmässig () * 10 + 1 );
}
System . ut . println ( Arrays . toString ( arr ));
}
public static void shakerSort ( int arr [] ) {
int buff ;
int vänster = 0 ;
int höger = arr . längd - 1 ;
gör {
for ( int i = vänster ; i < höger ; i ++ ) {
if ( arr [ i ] > arr [ i + 1 ] ) {
buff = arr [ i ] ;
arr [ i ] = arr [ i + 1 ] ;
arr [ i + 1 ] = buff ;
}
}
höger -- ;
for ( int i = höger ; i > vänster ; i -- ) {
if ( arr [ i ] < arr [ i - 1 ] ) {
buff = arr [ i ] ;
arr [ i ] = arr [ i - 1 ] ;
arr [ i - 1 ] = buff ;
}
}
vänster ++ ;
} while ( vänster < höger );
}
prov = [ 0 , - 1 , 5 , - 2 , 3 ]
vänster = 0
höger = len ( exempel ) - 1
medan vänster <= höger :
för i inom intervallet ( vänster , höger , +1 ) :
om prov [ i ] > prov [ i + 1 ]:
prov [ i ], prov [ i + 1 ] = prov [ i + 1 ], prov [ i ]
höger -= 1
för i inom intervallet ( höger , vänster , -1 ) :
om prov [ i - 1 ] > prov [ i ]:
prov [ i ], prov [ i - 1 ] = prov [ i - 1 ], prov [ i ]
vänster += 1
print ( exempel )
skapa tabell # temp1
(
id int primärnyckelidentitet , -- rad- ID
point int --värde
)
deklarera @ vänster int = 0 ,
@right int = ( välj antal ( * ) från # temp1 ) - 1 , _
@jag inte , _
@swap int _
medan @ vänster <= @ höger
Börja
ställ in @i = @vänster _ _
medan @ i < @ höger + 1
Börja
if ( välj punkt från # temp1 där id = @ i ) > ( välj punkt från # temp1 där id = @ i + 1 )
Börja
ställ in @ swap = ( välj punkt från # temp1 där id = @ i )
uppdatera # temp1
börvärde = ( välj punkt från # temp1 där id = @ i + 1 ) _
där id = @i _
uppdatera # temp1
börvärde = @swap _ _
där id = @ i + 1
slutet
ställ in @i = @i + 1 _ _
slutet
ställ in @ höger = @ höger - 1
ställ in @i = @höger _ _
medan @i > @vänster - 1 _ _
Börja
if ( välj punkt från # temp1 där id = @ i ) < ( välj punkt från # temp1 där id = @ i - 1 )
Börja
ställ in @ swap = ( välj punkt från # temp1 där id = @ i )
uppdatera # temp1
börvärde = ( välj punkt från # temp1 där id = @ i - 1 ) _
där id = @i _
uppdatera # temp1
börvärde = @swap _ _
där id = @ i - 1
slutet
ställ in @i = @i - 1 _ _
slutet
ställ in @vänster = @vänster + 1 _ _
slutet
välj punkt
från # temp1
subrutin sort_cocktail ( array_size , array )
heltal i , j
heltal sist_osorterat , först_osorterat , utbyte
logiskt sätt
heltal , avsikt ( i ) :: array_size
heltal , avsikt ( inout ) :: array ( array_size )
last_unsorted = array_size
först_osorterat = 1
sätt = . sant .
gör j = 1 , array_size
om ( sätt ) då
gör jag = först_osorterat , sist_osorterat - 1
if ( matris ( i ) . gt . matris ( i + 1 )) då
utbyte = array ( i )
array ( i ) = array ( i + 1 )
array ( i + 1 ) = utbyte
sluta om
slut göra
last_unsorted = last_unsorted - 1
annan
gör i = sist_osorterat - 1 , först_osorterat , - 1
if ( matris ( i ) . gt . matris ( i + 1 )) då
utbyte = array ( i )
array ( i ) = array ( i + 1 )
array ( i + 1 ) = utbyte
sluta om
slut göra
firs_osorterat = firs_osorterat + 1
sluta om
sätt = . inte . sätt
om ( firs_unsorted . ge . last_unsorted ) avsluta
slut göra
avsluta subrutinen