Sortare aleatorie
Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de
versiunea revizuită la 11 ianuarie 2018; verificările necesită
28 de modificări .
Sortare aleatorie , sau sortare Shaker sau bidirecțională ( ing . Sortare cocktail ) este un fel de sortare cu bule . Analizând metoda de sortare cu bule, se pot observa două lucruri.
În primul rând , dacă nu apar permutări la deplasarea printr-o parte a matricei, atunci această parte a matricei este deja sortată și, prin urmare, poate fi exclusă din considerare.
În al doilea rând , când se deplasează de la sfârșitul matricei la început, elementul minim „plutește” în prima poziție, iar elementul maxim este deplasat doar cu o poziție la dreapta.
Aceste două idei duc la următoarele modificări ale metodei de sortare cu bule. Limitele părții de lucru a matricei (adică a părții matricei în care are loc mișcarea) sunt stabilite în locația ultimului schimb la fiecare iterație. Matricea este scanată alternativ de la dreapta la stânga și de la stânga la dreapta.
#include <iostream>
#include <vector>
#include <ctime>
umplere gol ( std :: vector < int >& arr ) {
pentru ( size_t i = 0 ; i < arr . size (); ++ i ) {
arr [ i ] = static_cast < int > ( rand () % 100 );
std :: cout << arr [ i ] << " " ;
}
std :: cout << std :: endl ;
}
void shakerSort ( std :: vector < int >& arr ) {
int control = arr . dimensiunea () - 1 ;
int stânga = 0 ;
int dreapta = arr . dimensiunea () - 1 ;
face {
pentru ( int i = stânga ; i < dreapta ; i ++ ) {
dacă ( arr [ i ] > arr [ i + 1 ]) {
std :: swap ( arr [ i ], arr [ i + 1 ]);
control = i ;
}
}
dreapta = control ;
pentru ( int i = dreapta ; i > stânga ; i -- ) {
dacă ( arr [ i ] < arr [ i - 1 ]) {
std :: swap ( arr [ i ], arr [ i - 1 ]);
control = i ;
}
}
stânga = control ;
} în timp ce ( stânga < dreapta );
}
int main ()
{
const int N = 20 ;
std :: vector < int > arr ;
arr . rezerva ( N );
pentru ( int i = 0 ; i < N ; i ++ )
arr . pushback ( 0 );
srand ( timp ( 0 ));
umplere ( arr );
shakerSort ( arr );
pentru ( int i = 0 ; i < arr . dimensiune (); i ++ ) {
std :: cout << arr [ i ] << " " ;
}
arr . clar ();
std :: cin . ignora ();
}
folosind System ;
namespace SortLab
{
class Program
{
static void Main ()
{
Sort ();
}
/*Program principal*/
static void Sort ()
{
int [] myint = { 99 , 88 , 77 , 66 , 55 , 44 , 33 , 22 , 11 , 8 , 5 , 3 , 1 };
WriteArray ( myint );
ShakerSort ( myint );
WriteArray ( myint );
Consola . ReadLine ();
}
/* Shaker sort */
static void ShakerSort ( int [] myint )
{
int stânga = 0 ,
dreapta = myint . Lungime - 1 ,
număr = 0 ;
while ( stânga < dreapta )
{
for ( int i = stânga ; i < dreapta ; i ++)
{
count ++;
if ( myint [ i ] > myint [ i + 1 ])
Schimb ( myint , i , i + 1 );
}
dreapta --;
pentru ( int i = dreapta ; i > stânga ; i --)
{
count ++;
if ( myint [ i - 1 ] > myint [ i ])
Schimb ( myint , i - 1 , i );
}
stânga ++;
}
Consolă . WriteLine ( "\nNumăr de comparații = {0}" , număr . ToString ());
}
/* Schimbați elemente */
static void Schimbați ( int [] myint , int i , int j )
{
int glass = myint [ i ];
myint [ i ] = myint [ j ];
myint [ j ] = sticla ;
}
/*Matrice de ieșire*/
static void WriteArray ( int [] a )
{
foreach ( int i în a )
Consolă . Scrie ( "{0}|" , i .ToString ( ));
Consola . WriteLine ( "\n\n\n" );
}
}
}
function shakerSort ( array ) {
let left = 0 ; // începutul matricei
let right = array . lungime - 1 ; // sfârşitul matricei
while ( stânga < dreapta ) {
for ( lasă i = stânga ; i < dreapta ; i ++ ) {
if ( matrice [ i ] > matrice [ i + 1 ]) {
[ matrice [ i ], matrice [ i + 1 ]] = [ matrice [ i + 1 ], matrice [ i ]]
}
}
dreapta -- ;
pentru ( lasă i = dreapta ; stânga < i ; i -- ) {
dacă ( matrice [ i ] < matrice [ i - 1 ]) {
[ matrice [ i ], matrice [ i - 1 ]] = [ matrice [ i - 1 ], matrice [ i ]]
}
}
stânga ++ ;
}
matrice de returnare ; }
function cocktailSorting ( & $a ) {
$n = count ( $a );
$stânga = 0 ;
$dreapta = $n - 1 ;
do {
for ( $i = $stânga ; $i < $dreapta ; $i ++ ) {
if ( $a [ $i ] > $a [ $i + 1 ]) {
lista ( $a [ $i ], $a [ $i + 1 ]) = tablou ( $a [ $i + 1 ], $a [ $i ]);
}
}
$dreapta -- ;
pentru ( $i = $dreapta ; $i > $stânga ; $i -- ) {
if ( $a [ $i ] < $a [ $i - 1 ]) {
lista ( $a [ $i ], $a [ $i - 1 ]) = tablou ( $a [ $i - 1 ], $a [ $i ]);
}
}
$stânga ++ ;
} while ( $stânga <= $dreapta );
}
SAU
function FunctionCoocktailSort ( & $array )
{
$leftItem = 0 ;
$rightItem = număr ( $array ) - 1 ;
for ( $i = $leftItem ; $i < $rightItem ; $i ++ ) {
for ( $j = $leftItem ; $j < $rightItem ; $j ++ ) {
if ( $array [ $j ] > $ matrice [ $j + 1 ]) {
FunctionSwapVariables ( $matrice [ $j ], $matrice [ $j + 1 ]);
}
}
$rightItem -- ;
pentru ( $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 );
Sistem . afară . println ( Arrays . toString ( arr ));
}
private static void fillArray ( int arr [] ) {
pentru ( int i = 0 ; i < arr . lungime ; i ++ ) {
arr [ i ] = ( int ) ( Math . aleatoriu () * 10 + 1 );
}
Sistem . afară . println ( Arrays . toString ( arr ));
}
public static void shakerSort ( int arr [] ) {
int buff ;
int stânga = 0 ;
int dreapta = arr . lungime - 1 ;
face {
pentru ( int i = stânga ; i < dreapta ; i ++ ) {
dacă ( arr [ i ] > arr [ i + 1 ] ) {
buff = arr [ i ] ;
arr [ i ] = arr [ i + 1 ] ;
arr [ i + 1 ] = buff ;
}
}
dreapta -- ;
pentru ( int i = dreapta ; i > stânga ; i -- ) {
dacă ( arr [ i ] < arr [ i - 1 ] ) {
buff = arr [ i ] ;
arr [ i ] = arr [ i - 1 ] ;
arr [ i - 1 ] = buff ;
}
}
stânga ++ ;
} în timp ce ( stânga < dreapta );
}
eșantion = [ 0 , - 1 , 5 , - 2 , 3 ]
stânga = 0
dreapta = len ( eșantion ) - 1
în timp ce stânga <= dreapta :
pentru i în interval ( stânga , dreapta , + 1 ):
dacă eșantion [ i ] > eșantion [ i + 1 ]:
proba [ i ], proba [ i + 1 ] = proba [ i + 1 ], proba [ i ]
dreapta -= 1
pentru i în interval ( dreapta , stânga , - 1 ):
dacă eșantion [ i - 1 ] > eșantion [ i ]:
eșantion [ i ], eșantion [ i - 1 ] = eșantion [ i - 1 ], eșantion [ i ]
stânga += 1
imprimare ( probă )
creați tabelul # temp1
(
id int identitatea cheii primare , -- ID de rând
punct int --valoare
)
declara @ left int = 0 ,
@right int = ( selectați numărul ( * ) din # temp1 ) - 1 , _
@i int , _
@swap int _
în timp ce @ stânga <= @ dreapta
ÎNCEPE
set @i = @left _ _
în timp ce @ i < @ dreapta + 1
ÎNCEPE
if ( selectați punctul din # temp1 unde id = @ i ) > ( selectați punctul din # temp1 unde id = @ i + 1 )
ÎNCEPE
set @ swap = ( selectează punctul din # temp1 unde id = @ i )
actualizare # temp1
punct de referință = ( selectați punctul din # temp1 unde id = @ i + 1 )
unde id = @i _
actualizare # temp1
punct de referință = @swap _ _
unde id = @ i + 1
Sfârşit
set @i = @i + 1 _ _
Sfârşit
setați @ dreapta = @ dreapta - 1
set @i = @dreapta _ _
în timp ce @i > @left - 1 _ _
ÎNCEPE
if ( selectați punctul din # temp1 unde id = @ i ) < ( selectați punctul din # temp1 unde id = @ i - 1 )
ÎNCEPE
set @ swap = ( selectează punctul din # temp1 unde id = @ i )
actualizare # temp1
set point = ( selectează punctul din # temp1 unde id = @ i - 1 )
unde id = @i _
actualizare # temp1
punct de referință = @swap _ _
unde id = @ i - 1
Sfârşit
set @i = @i - 1 _ _
Sfârşit
set @left = @left + 1 _ _
Sfârşit
selectați punctul
de la # temp1
subrutina sort_cocktail ( array_size , array )
întreg i , j
întreg last_unsorted , firs_unsorted , schimb
mod logic
integer , intent ( în ) :: array_size
întreg , intenție ( inout ) :: matrice ( array_size )
last_unsorted = dimensiune_matrice
firs_nesorted = 1
cale = . adevărat .
do j = 1 , array_size
dacă ( mod ) atunci
do i = firs_unsorted , last_unsorted - 1
dacă ( array ( i ) . gt . array ( i + 1 )) atunci
schimb = matrice ( i )
matrice ( i ) = matrice ( i + 1 )
matrice ( i + 1 ) = schimb
sfârşitul dacă
sfârşitul face
ultimul_nesortat = ultimul_nesortat - 1
altfel
do i = ultimul_nesortat - 1 , primul_nesortat , - 1
dacă ( array ( i ) . gt . array ( i + 1 )) atunci
schimb = matrice ( i )
matrice ( i ) = matrice ( i + 1 )
matrice ( i + 1 ) = schimb
sfârşitul dacă
sfârşitul face
brazi_nesortați = brazi_nesortați + 1
sfârşitul dacă
cale = . nu . cale
if ( firs_unsorted . ge . last_unsorted ) exit
sfârşitul face
sfârşitul subrutinei
Link -uri