Loading:


Metoda sortowania - Zoptymalizowane szybkie sortowanie - Optimized Quick Sort [JAVA]

Skrypt ukazuje jak wygląda oraz jak działa metoda sortowania typu Optimized Quick Sort (Zoptymalizowane Szybkie sortowanie). Kod ten można wykorzystać do sortowania liczb.



Napisz Artyku³

Listing


package sorting;

/**
 * last generated: 2009-03-07
 * @author Funkcje.net
 */

public class ZoptymalizowaneSzybkieSortowanie {
  //wielkość można dowolnie modyfikować w instrukcji warunkowej  
  private int WIELKOSC;

  public void sortowanie( Comparable [ ] items ) {
        szybkieSortowanie( items, 0, items.length - 1 );
    }
   

    private void szybkieSortowanie( Comparable [ ] items, int start, int stop ) {
        if (items.length >= 100000){
            WIELKOSC = 15;
        }else if (items.length >= 10000) {
            WIELKOSC = 10;
        }else{
            WIELKOSC = 5;
        }
       
        if( start + WIELKOSC > stop )
            sortowanie( items, start, stop );
        else {
            int mediana = ( start + stop ) / 2;
            if( items[ stop ].compareTo( items[ start ] ) < 0 )
                swap_function( items, start, stop );
            if( items[ stop ].compareTo( items[ mediana ] ) < 0 )
                swap_function( items, mediana, stop );
            if( items[ mediana ].compareTo( items[ start ] ) < 0 )
                swap_function( items, start, mediana );
           
            swap_function( items, mediana, stop - 1 );
            Comparable piwot = items[ stop - 1 ];
           
            int i, j;
            for( i = start, j = stop - 1; ; ) {
                while( items[ ++i ].compareTo( piwot ) < 0 );
                while( piwot.compareTo( items[ --j ] ) < 0 );
                if( i >= j )
                    break;
                swap_function( items, i, j );
            }
           
            swap_function( items, i, stop - 1 );
           
            szybkieSortowanie( items, start, i - 1 );    // Sortowanie małych elementów
            szybkieSortowanie( items, i + 1, stop );   // Sortowanie dużych elementów
        }
    }
   

    public static final void swap_function( Object [ ] items, int index1, int index2 ) {
        Object temp = items[ index1 ];
        items[ index1 ] = items[ index2 ];
        items[ index2 ] = temp;
    }
   
   
    private static void sortowanie( Comparable [ ] items, int start, int stop ) {
        for( int p = start + 1; p <= stop; p++ ) {
            Comparable temp = items[ p ];
            int j;
           
            for( j = p; j > start && temp.compareTo( items[ j - 1 ] ) < 0; j-- )
                items[ j ] = items[ j - 1 ];
            items[ j ] = temp;
        }
    }

}
 




Dodano przez: divix
Ranga: Administrator serwisu Punktów: 38423
Komentarze użytkowników
    • Tre¶æ komentarza
      Kod do komentarza (opcjonalnie)
      PHP JavaScript MySQL Smarty SQL HTML CSS ActionScript
      Autor
      Token
      token

       

       








funkcje.net
Wszelkie prawa zastrzeżone©. | Funkcje.net 2008-2020 v.1.5 | design: diviXdesign & rainbowcolors