Sekoita lajittelu
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. tammikuuta 2018 tarkistetusta
versiosta . tarkastukset vaativat
28 muokkausta .
Shuffle sort , Shaker sort tai kaksisuuntainen ( eng. Cocktail sort ) on eräänlainen kuplalajittelu . Kuplalajittelumenetelmää analysoimalla voidaan huomata kaksi asiaa.
Ensinnäkin , jos taulukon osan läpi liikkuessa ei tapahdu permutaatioita, tämä taulukon osa on jo lajiteltu ja siksi se voidaan jättää huomiotta.
Toiseksi , siirryttäessä taulukon lopusta alkuun minimielementti "kelluu" ensimmäiseen paikkaan ja maksimielementti siirtyy vain yhden aseman oikealle.
Nämä kaksi ideaa johtavat seuraaviin muokkauksiin kuplalajittelumenetelmään. Matriisin työosan (eli sen osan, jossa liikettä tapahtuu) rajat asetetaan viimeisen vaihdon sijaintiin kussakin iteraatiossa. Matriisi skannataan vuorotellen oikealta vasemmalle ja vasemmalta oikealle.
#include <iostream>
#sisällytä <vektori>
#include <ctime>
void filling ( std :: vektori < int >& arr ) {
for ( koko_t i = 0 ; i < arr . koko (); ++ i ) {
arr [ i ] = static_cast < int > ( rand () % 100 );
std :: cout << arr [ i ] << " " ;
}
std :: cout << std :: endl ;
}
void shakerSort ( std :: vektori < int >& arr ) {
int ohjaus = arr . koko () - 1 ;
int vasen = 0 ;
int oikea = arr . koko () - 1 ;
do {
for ( int i = vasen ; i < oikea ; i ++ ) {
if ( arr [ i ] > arr [ i + 1 ]) {
std :: swap ( arr [ i ], arr [ i + 1 ]);
ohjaus = i ;
}
}
oikea = ohjaus ;
for ( int i = oikea ; i > vasen ; i -- ) {
if ( arr [ i ] < arr [ i - 1 ]) {
std :: swap ( arr [ i ], arr [ i - 1 ]);
ohjaus = i ;
}
}
vasen = ohjaus ;
} while ( vasen < oikea );
}
int main ()
{
const int N = 20 ;
std :: vektori < int > arr ;
arr . reservi ( N );
for ( int i = 0 ; i < N ; i ++ )
arr . työntö ( 0 );
srand ( aika ( 0 ));
täyttö ( arr );
shakerSort ( arr );
for ( int i = 0 ; i < arr . size (); i ++ ) {
std :: cout << arr [ i ] << " " ;
}
arr . selkeä ();
std :: cin . jättää huomiotta ();
}
käyttäen System ;
nimiavaruus SortLab
{
luokka Ohjelma
{
static void Main ()
{
Lajittele ();
}
/*Pääohjelma*/
staattinen void Lajittele ()
{
int [] myint = { 99 , 88 , 77 , 66 , 55 , 44 , 33 , 22 , 11 , 8 , 5 , 3 , 1 };
WriteArray ( myint );
ShakerSort ( myint );
WriteArray ( myint );
konsoli . ReadLine ();
}
/* Shaker sort */
static void ShakerSort ( int [] myint )
{
int vasen = 0 ,
oikea = myint . Pituus - 1 ,
määrä = 0 ;
while ( vasen < oikea )
{
for ( int i = vasen ; i < oikea ; i ++)
{
count ++;
if ( myint [ i ] > myint [ i + 1 ])
Vaihda ( myint , i , i + 1 );
}
oikea --;
for ( int i = oikea ; i > vasen ; i --)
{
count ++;
if ( myint [ i - 1 ] > myint [ i ])
Vaihda ( myint , i - 1 , i );
}
vasen ++;
}
Konsoli . WriteLine ( "\nVertailujen määrä = {0}" , count . ToString ());
}
/* Vaihda elementtejä */
staattinen void Vaihda ( int [] myint , int i , int j )
{
int lasi = myint [ i ];
myint [ i ] = myint [ j ];
myint [ j ] = lasi ;
}
/*Output array*/
static void WriteArray ( int [] a )
{
foreach ( int i in a )
Konsoli . Write ( "{0}|" , i .ToString ( ));
konsoli . WriteLine ( "\n\n\n" );
}
}
}
function shakerSort ( array ) {
anna vasemmalle = 0 ; // taulukon alku
Let right = array . pituus - 1 ; // taulukon loppu
while ( vasen < oikea ) {
for ( i = vasen ; i < oikea ; i ++ ) { if ( array [ i ] > array [ i + 1 ]) { [ array [ i ] , array [ i + 1 ]] = [ taulukko [ i + 1 ], taulukko [ i ]] } } oikea -- ; for ( olkoon i = oikea ; vasen < i ; i -- ) { if ( array [ i ] < array [ i - 1 ]) { [ array [ i ], array [ i - 1 ]] = [ array [ i - 1 ], taulukko [ i ]] } } vasen ++ ; } return array ; }
function cocktail Lajittelu ( & $a ) {
$n = count ( $a );
$vasen = 0 ;
$oikea = $n - 1 ;
do {
for ( $i = $vasen ; $i < $oikea ; $i ++ ) {
if ( $a [ $i ] > $a [ $i + 1 ]) {
list ( $a [ $i ], $a [ $i + 1 ]) = taulukko ( $a [ $i + 1 ], $a [ $i ]);
}
}
$oikea -- ;
for ( $i = $oikea ; $i > $vasen ; $i -- ) {
if ( $a [ $i ] < $a [ $i - 1 ]) {
list ( $a [ $i ], $a [ $i - 1 ]) = taulukko ( $a [ $i - 1 ], $a [ $i ]);
}
}
$vasen ++ ;
} while ( $vasen <= $oikea );
}
TAI
function FunctionCoocktailSort ( & $array )
{
$leftItem = 0 ;
$rightItem = count ( $array ) - 1 ;
for ( $i = $leftItem ; $i < $rightItem ; $i ++ ) {
for ( $j = $leftItem ; $j < $rightItem ; $j ++ ) {
if ( $array [ $j ] > $ taulukko [ $j + 1 ]) {
FunctionSwapVariables ( $taulukko [ $j ], $taulukko [ $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 );
Järjestelmä . ulos . println ( Arrays . toString ( arr ));
}
yksityinen staattinen void fillArray ( int arr [] ) {
for ( int i = 0 ; i < arr . pituus ; i ++ ) {
arr [ i ] = ( int ) ( Math . random () * 10 + 1 );
}
Järjestelmä . ulos . println ( Arrays . toString ( arr ));
}
public static void shakerSort ( int arr [] ) {
int buff ;
int vasen = 0 ;
int oikea = arr . pituus - 1 ;
do {
for ( int i = vasen ; i < oikea ; i ++ ) {
if ( arr [ i ] > arr [ i + 1 ] ) {
buff = arr [ i ] ;
arr [ i ] = arr [ i + 1 ] ;
arr [ i + 1 ] = buff ;
}
}
oikea -- ;
for ( int i = oikea ; i > vasen ; i -- ) {
if ( arr [ i ] < arr [ i - 1 ] ) {
buff = arr [ i ] ;
arr [ i ] = arr [ i - 1 ] ;
arr [ i - 1 ] = buff ;
}
}
vasen ++ ;
} while ( vasen < oikea );
}
näyte = [ 0 , - 1 , 5 , - 2 , 3 ]
vasen = 0
oikea = len ( näyte ) - 1
kun vasen <= oikea :
i alueella ( vasen , oikea , + 1 ) : _
jos näyte [ i ] > näyte [ i + 1 ]:
näyte [ i ], näyte [ i + 1 ] = näyte [ i + 1 ], näyte [ i ]
oikea -= 1
i : lle alueella ( oikea , vasen , -1 ) :
jos näyte [ i - 1 ] > näyte [ i ]:
näyte [ i ], näyte [ i - 1 ] = näyte [ i - 1 ], näyte [ i ]
vasen += 1
tulosta ( näyte )
T-SQL
luo taulukko # temp1
(
id int ensisijaisen avaimen identiteetti , -- rivin tunnus
piste int --arvo
)
julista @ vasen int = 0 ,
@right int = ( valitse määrä ( * ) joukosta # temp1 ) - 1 , _
@i int , _
@swap int _
kun @ vasen <= @ oikea
alkaa
aseta @i = @vasen _ _
kun @ i < @ oikea + 1
alkaa
if ( valitse piste kohdasta # temp1 , jossa id = @ i ) > ( valitse piste kohdasta # temp1 , jossa id = @ i + 1 )
alkaa
set @ swap = ( valitse piste kohdasta # temp1 jossa id = @ i )
päivitys # temp1
asetuspiste = ( valitse piste kohdasta # temp1 jossa id = @ i + 1 ) _
missä id = @i _
päivitys # temp1
asetuspiste = @swap _ _
missä id = @ i + 1
loppu
aseta @i = @i + 1 _ _
loppu
aseta @ oikea = @ oikea - 1
aseta @i = @oikea _ _
kun @i > @vasen - 1 _ _
alkaa
if ( valitse piste kohdasta # temp1 , jossa id = @ i ) < ( valitse piste kohdasta # temp1 , jossa id = @ i - 1 )
alkaa
set @ swap = ( valitse piste kohdasta # temp1 jossa id = @ i )
päivitys # temp1
asetuspiste = ( valitse piste kohdasta # temp1 jossa id = @ i - 1 ) _
missä id = @i _
päivitys # temp1
asetuspiste = @swap _ _
jossa id = @ i - 1
loppu
aseta @i = @i - 1 _ _
loppu
aseta @vasen = @vasen + 1 _ _
loppu
valitse piste
alkaen # temp1
aliohjelma sort_cocktail ( array_size , array )
kokonaisluku i , j
kokonaisluku viimeinen_lajittelematon , firs_lajittelematon , vaihto
looginen tapa
kokonaisluku , tarkoitus ( in ) :: taulukon_koko
kokonaisluku , tarkoitus ( inout ) :: array ( array_size )
viimeinen_lajittelematon = taulukon_koko
kuusi_lajittelematon = 1
tapa = . totta .
do j = 1 , taulukon_koko
jos ( tapa ) sitten
do i = ensimmäinen_lajittelematon , viimeinen_lajittelematon - 1
if ( array ( i ) . gt . array ( i + 1 )) then
vaihto = array ( i )
taulukko ( i ) = taulukko ( i + 1 )
array ( i + 1 ) = vaihto
loppu Jos
lopeta tehdä
viimeinen_lajittelematon = viimeinen_lajittelematon - 1
muu
do i = viimeinen_lajittelematon - 1 , ensimmäinen_lajittelematon , - 1
if ( array ( i ) . gt . array ( i + 1 )) then
vaihto = array ( i )
taulukko ( i ) = taulukko ( i + 1 )
array ( i + 1 ) = vaihto
loppu Jos
lopeta tehdä
kuusi_lajittelematon = kuusi_lajittelematon + 1
loppu Jos
tapa = . ei . tapa
if ( firs_unsorted . ge . last_unsorted ) exit
lopeta tehdä
aliohjelman loppu
Linkit