Bland sortering
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den
version , der blev gennemgået den 11. januar 2018; checks kræver
28 redigeringer .
Shuffle sort , eller Shaker sort, eller tovejs ( eng. Cocktail sort ) er en slags boble sortering . Ved at analysere boblesorteringsmetoden kan to ting bemærkes.
For det første , hvis der ikke forekommer nogen permutationer, når du bevæger dig gennem en del af arrayet, så er denne del af arrayet allerede sorteret, og derfor kan det udelukkes fra overvejelse.
For det andet , når du flytter fra slutningen af arrayet til begyndelsen, "flyder" minimumselementet til den første position, og maksimumelementet flyttes kun en position til højre.
Disse to ideer fører til følgende ændringer af boblesorteringsmetoden. Grænserne for den arbejdende del af arrayet (det vil sige den del af arrayet, hvor bevægelsen finder sted) er sat på stedet for den sidste udveksling ved hver iteration. Arrayet scannes skiftevis fra højre mod venstre og fra venstre mod højre.
#include <iostream>
#inkluder <vektor>
#include <ctime>
tomrumsudfyldning ( std :: vektor < int > & arr ) {
for ( størrelse_t i = 0 ; i < arr . størrelse (); ++ i ) {
arr [ i ] = static_cast < int > ( rand () % 100 );
std :: cout << arr [ i ] << " " ;
}
std :: cout << std :: endl ;
}
void shakerSort ( std :: vektor < int >& arr ) {
int kontrol = arr . størrelse () - 1 ;
int venstre = 0 ;
int højre = arr . størrelse () - 1 ;
gør {
for ( int i = venstre ; i < højre ; i ++ ) {
if ( arr [ i ] > arr [ i + 1 ]) {
std :: swap ( arr [ i ], arr [ i + 1 ]);
kontrol = i ;
}
}
højre = kontrol ;
for ( int i = højre ; i > venstre ; i -- ) {
if ( arr [ i ] < arr [ i - 1 ]) {
std :: swap ( arr [ i ], arr [ i - 1 ]);
kontrol = i ;
}
}
venstre = kontrol ;
} while ( venstre < højre );
}
int main ()
{
const int N = 20 ;
std :: vektor < int > arr ;
arr . reserve ( N );
for ( int i = 0 ; i < N ; i ++ )
arr . pushback ( 0 );
srand ( tid ( 0 ));
fyldning ( arr );
shakerSort ( arr );
for ( int i = 0 ; i < arr . størrelse (); i ++ ) {
std :: cout << arr [ i ] << " " ;
}
arr . klar ();
std :: cin . ignorere ();
}
bruger System ;
navneområde SortLab
{
class Program
{
static void Main ()
{
Sort ();
}
/*Hovedprogram*/
static void Sort ()
{
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ængde - 1 ,
antal = 0 ;
while ( venstre < højre )
{
for ( int i = venstre ; i < højre ; i ++)
{
tælle ++;
if ( myint [ i ] > myint [ i + 1 ])
Swap ( myint , i , i + 1 );
}
højre --;
for ( int i = højre ; i > venstre ; i --)
{
tælle ++;
if ( myint [ i - 1 ] > myint [ i ])
Swap ( myint , i - 1 , i );
}
venstre ++;
}
Konsol . WriteLine ( "\nAntal sammenligninger = {0}" , tæl . ToString ());
}
/* Swap elementer */
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" );
}
}
}
funktion shakerSort ( array ) {
lad venstre = 0 ; // start af array
lad højre = array . længde - 1 ; // ende af matrix
while ( venstre < højre ) {
for ( lad i = venstre ; i < højre ; i ++ ) {
if ( matrix [ i ] > matrix [ i + 1 ]) {
[ matrix [ i ], matrix [ i + 1 ]] = [ array [ i + 1 ], array [ i ]]
}
}
højre -- ;
for ( lad i = højre ; venstre < i ; i -- ) {
if ( array [ i ] < array [ i - 1 ]) {
[ array [ i ], array [ i - 1 ]] = [ array [ i - 1 ], array [ i ]]
}
}
venstre ++ ;
}
returner matrix ;
}
funktion cocktailSortering ( & $a ) {
$n = count ( $a );
$venstre = 0 ;
$højre = $n - 1 ;
gør {
for ( $i = $venstre ; $i < $højre ; $i ++ ) {
if ( $a [ $i ] > $a [ $i + 1 ]) {
list ( $a [ $i ], $a [ $i + 1 ]) = matrix ( $a [ $i + 1 ], $a [ $i ]);
}
}
$right -- ;
for ( $i = $højre ; $i > $venstre ; $i -- ) {
if ( $a [ $i ] < $a [ $i - 1 ]) {
liste ( $a [ $i ], $a [ $i - 1 ]) = matrix ( $a [ $i - 1 ], $a [ $i ]);
}
}
$venstre ++ ;
} while ( $venstre <= $højre );
}
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 -- ;
for ( $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 . ud . println ( Arrays . toString ( arr ));
}
private static void fillArray ( int arr [] ) {
for ( int i = 0 ; i < arr . længde ; i ++ ) {
arr [ i ] = ( int ) ( Matematik . tilfældig () * 10 + 1 );
}
System . ud . println ( Arrays . toString ( arr ));
}
public static void shakerSort ( int arr [] ) {
int buff ;
int venstre = 0 ;
int højre = arr . længde - 1 ;
gør {
for ( int i = venstre ; i < højre ; i ++ ) {
if ( arr [ i ] > arr [ i + 1 ] ) {
buff = arr [ i ] ;
arr [ i ] = arr [ i + 1 ] ;
arr [ i + 1 ] = buff ;
}
}
højre -- ;
for ( int i = højre ; i > venstre ; i -- ) {
if ( arr [ i ] < arr [ i - 1 ] ) {
buff = arr [ i ] ;
arr [ i ] = arr [ i - 1 ] ;
arr [ i - 1 ] = buff ;
}
}
venstre ++ ;
} while ( venstre < højre );
}
prøve = [ 0 , - 1 , 5 , - 2 , 3 ]
venstre = 0
højre = len ( eksempel ) - 1
mens venstre <= højre :
for i inden for rækkevidde ( venstre , højre , +1 ) :
hvis prøve [ i ] > prøve [ i + 1 ]:
prøve [ i ], prøve [ i + 1 ] = prøve [ i + 1 ], prøve [ i ]
højre -= 1
for i inden for rækkevidde ( højre , venstre , -1 ) :
hvis prøve [ i - 1 ] > prøve [ i ]:
prøve [ i ], prøve [ i - 1 ] = prøve [ i - 1 ], prøve [ i ]
venstre += 1
print ( eksempel )
opret tabel # temp1
(
id int primær nøgleidentitet , -- række- id
point int --værdi
)
erklære @ venstre int = 0 ,
@right int = ( vælg antal ( * ) fra # temp1 ) - 1 , _
@i int , _
@swap int _
mens @ venstre <= @ højre
begynde
sæt @i = @venstre _ _
mens @ i < @ højre + 1
begynde
if ( vælg punkt fra # temp1 hvor id = @ i ) > ( vælg punkt fra # temp1 hvor id = @ i + 1 )
begynde
sæt @ swap = ( vælg punkt fra # temp1 hvor id = @ i )
opdater # temp1
sætpunkt = ( vælg punkt fra # temp1 hvor id = @ i + 1 ) _
hvor id = @i _
opdater # temp1
sætpunkt = @swap _ _
hvor id = @ i + 1
ende
sæt @i = @i + 1 _ _
ende
sæt @ højre = @ højre - 1
sæt @i = @højre _ _
mens @i > @venstre - 1 _ _
begynde
if ( vælg punkt fra # temp1 hvor id = @ i ) < ( vælg punkt fra # temp1 hvor id = @ i - 1 )
begynde
sæt @ swap = ( vælg punkt fra # temp1 hvor id = @ i )
opdater # temp1
sætpunkt = ( vælg punkt fra # temp1 hvor id = @ i - 1 ) _
hvor id = @i _
opdater # temp1
sætpunkt = @swap _ _
hvor id = @ i - 1
ende
sæt @i = @i - 1 _ _
ende
sæt @venstre = @venstre + 1 _ _
ende
vælg punkt
fra # temp1
subrutine sort_cocktail ( array_size , array )
heltal i , j
heltal last_unsorted , firs_usorted , exchange
logisk måde
heltal , hensigt ( i ) :: array_size
heltal , hensigt ( inout ) :: array ( array_size )
sidste_usorteret = matrixstørrelse
først_usorteret = 1
måde = . sandt .
do j = 1 , array_size
hvis ( måde ) så
do i = først_usorteret , sidste_usorteret - 1
if ( matrix ( i ) . gt . matrix ( i + 1 )) derefter
udveksling = matrix ( i )
matrix ( i ) = matrix ( i + 1 )
array ( i + 1 ) = udveksling
Afslut Hvis
ende gøre
sidste_usorteret = sidste_usorteret - 1
andet
do i = sidste_usorteret - 1 , først_usorteret , - 1
if ( matrix ( i ) . gt . matrix ( i + 1 )) derefter
udveksling = matrix ( i )
matrix ( i ) = matrix ( i + 1 )
array ( i + 1 ) = udveksling
Afslut Hvis
ende gøre
firs_usorteret = firs_usorteret + 1
Afslut Hvis
måde = . ikke . vej
if ( firs_unsorted . ge . last_unsorted ) exit
ende gøre
afslutte subrutine
Links