Leksikografsko sortiranje

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Algoritem za leksikografsko sortiranje je sortirni algoritem.

Vsebina

Lastnosti

Njegove pomembne lastnosti so

  • deli atributa (ključa) za urejanje imajo pomen
  • uporabno za sortiranje števil in nizov (znakov)

Postopek

  1. elemente tabele razvrstimo v več razredov glede na vrednost dela atributa (mesto v ključu)
  2. postopek ponavljamo za vse dele (mesta) od najmanj do najbolj pomembnega
  3. vsaka iteracija elemente najprej porazdeli in nato spet prepiše v tabelo a

Prikaz delovanja

sortiranje trimestnih števil

  • števila imajo 3 mesta
  • števila so desetiška - imamo 10 različnih razredov 
a: 257 915 655 315 411 65 721 852 101 477  67 222

najprej gremo po enicah 

razredi:
0: 
1: 411 721 101
2: 852 222
3:
4:
5: 915 655 315 65
6:
7: 257 477 67
8:
9:

združimo (seznam je sedaj urejen po enicah) 

a: 411 721 101 852 222 915 655 315 65 257 477 67

potem sortiramo po deseticah 

razredi:
0: 101
1: 411 915 315
2: 721 222
3:
4:
5: 852 655 257
6: 65 67
7: 477
8:
9:

združimo (sedaj imamo že urejenost po deseticah in hkrati po enicah) 

a: 101 411 915 315 721 222 852 655 257 65 67 477

na koncu sortiramo še po stoticah 

razredi:
0: 65 67
1: 101
2: 222 257
3: 315
4: 411 477
5: 
6: 655
7: 721
8: 852
9: 915

združimo 

a: 65 67 101 222 257 315 411 477 655 721 852 915

Realizacija v Javi

public class LeksiSort
{
 
  // urejanje desetiskih stevil 
  public static void sortiraj(int[] a,int raz,int mest) // raz  = stevilo razredov
  {                                                     // mest = stevilo mest
    for(int m=0; m<mest; m++)
    { 
      razvrsti(a,raz,mest,m);  // razvrsti podatke v razrede glede na mesto m
 
      System.out.println("Tabela a (po razvrscanju za mesto "+m+"): ");
      for(int i=0; i<a.length;++i)
        System.out.println(a[i]);
      System.out.println();
     } 
  }
 
  private static void razvrsti(int[] a,int raz,int mest,int m) 
  {                        //razvrsti in zdruzi glede na mesto m
    int c[]=new int[raz];
 
    for(int i=0;i<a.length;i++)
       ++c[dolociRazred(m,a[i],raz)];  // doloci stevilo elementov v vsakem razredu
 
    // izpis tabele c
    System.out.println("Tabela c (po stetju elementov za mesto "+m+")");
    for(int i=0;i<c.length;i++)
       System.out.print(c[i]+"  ");  
    System.out.println();
    System.out.println();
 
 
    for(int i=1;i<raz;i++)
      c[i]+=c[i-1];         // c[i] vsebuje stevilo elementov, ki so <= i
 
    // izpis tabele c
    System.out.println("Tabela c (stevilo elementov, ki so manjsi od i)");
    for(int i=0;i<c.length;i++)
       System.out.print(c[i]+"  ");  
    System.out.println();
    System.out.println();
 
 
    int tmp[]=new int[a.length];
    for(int i=a.length-1;i>=0;i--)
      tmp[--c[dolociRazred(m,a[i],raz)]]=a[i]; // prepisi a[i] v ustrezen element tmp
 
    for(int i=0;i<a.length;i++)
      a[i]=tmp[i];             // prekopiraj tabelo tmp v a
  }
 
  private static int dolociRazred(int m, int stevilo, int raz)
  {
    return stevilo/(int)Math.pow(10,m)%raz;
  }
 
 
  // urejenje Nizov 
  public static void sortiraj(String[] a,int raz,int mest)
  {
    for(int m=mest-1; m>=0; m--)
     {
      razvrsti(a,raz,mest,m);  // razvrsti podatke v razrede glede na mesto m
/*
      System.out.println("Tabela b (po razvrscanju za mesto "+m+"): ");
      for(int i=0; i<a.length;++i)
        System.out.println(a[i]);
      System.out.println();
*/
     } 
  }
 
  private static void razvrsti(String[] a,int raz,int mest,int m)
  {
    int c[]=new int[raz];
 
    for(int i=0;i<a.length;i++)
       ++c[dolociRazred(m,a[i],raz)];  // doloci stevilo elementov v vsakem razredu
/*
    // izpis tabele c
    System.out.println("Tabela c (po stetju elementov za mesto "+m+"):");
    for(int i=0;i<c.length;i++)
       System.out.print(c[i]+"  ");  
    System.out.println();
    System.out.println();
*/
 
    for(int i=1;i<raz;i++)
      c[i]+=c[i-1];         // c[i] vsebuje stevilo elementov, ki so <= i
/*
    // izpis tabele c
    System.out.println("Tabela c (stevilo elementov, ki so manjsi od i):");
    for(int i=0;i<c.length;i++)
       System.out.print(c[i]+"  ");  
    System.out.println();
    System.out.println();
*/
    String tmp[]=new String[a.length];
    for(int i=a.length-1;i>=0;i--)
      tmp[--c[dolociRazred(m,a[i],raz)]]=a[i]; // prepisi a[i] v ustrezen element tmp
 
    for(int i=0;i<a.length;i++)
      a[i]=tmp[i];             // prekopiraj tabelo tmp v a
  }
 
  private static int dolociRazred(int m, String niz, int raz)
  {
    if (m>niz.length()-1 || niz.charAt(m)==' ')   //ce poz m izven niza ali da je presledek 
                                                  //vrne 0;
      return 0;                         // presledek spada v razred 0
    else
      return Character.toUpperCase(niz.charAt(m))-'A'+1; // A ali a = 1, B ali b = 2...
  }
}

Razred za testiranje algoritma: 

public class TestLeksiSort
{
  static final int ST_RAZ_S=10;
  static final int ST_MEST_S=3;
 
  static final int ST_RAZ_N=27;
  static final int ST_MEST_N=30;
 
  public static void main(String[] args)
  { 
    int[] a={257,915,655,315,411,65,721,852,101,477,67,222};
 
    System.out.println("Urejenje (desetiskih trimestnih) stevil ");
    System.out.println();
    System.out.println("Tabela a (pred sortiranjem): ");
    for(int i=0; i<a.length;++i)
      System.out.println(a[i]);
    System.out.println();
 
    LeksiSort.sortiraj(a,ST_RAZ_S,ST_MEST_S);
 
    System.out.println("Tabela a (po sortiranju): ");
    for(int i=0; i<a.length;++i)
      System.out.println(a[i]);
    System.out.println();
 
 
    String[] b={"Petan Miha","Kolar Peter","Petkovsek Ana","AMBROZ Franc","Zajc Zora",
                "Lah Ljubo","Amon Katja","Lap Lidija","PETEK Peter","Pipan Tone"};
 
    System.out.println("Urejenje nizov ");
    System.out.println();
    System.out.println("Tabela b (pred sortiranjem): ");
    for(int i=0; i<b.length;++i)
      System.out.println(b[i]);
    System.out.println();
 
    LeksiSort.sortiraj(b,ST_RAZ_N,ST_MEST_N);  
 
    System.out.println("Tabela b (po sortiranju): ");
    for(int i=0; i<b.length;++i)
      System.out.println(b[i]);
    System.out.println();
 
  }
}

Izpis programa

Urejenje (desetiskih trimestnih) stevil 

Tabela a (pred sortiranjem): 
257 915 655 315 411 65 721 852 101 477 67 222

Tabela c (po stetju elementov za mesto 0)
0  3  2  0  0  4  0  3  0  0  

Tabela c (stevilo elementov, ki so manjsi od i)
0  3  5  5  5  9  9  12  12  12  

Tabela a (po razvrscanju za mesto 0): 
411 721 101 852 222 915 655 315 65 257 477 67

Tabela c (po stetju elementov za mesto 1)
1  3  2  0  0  3  2  1  0  0  

Tabela c (stevilo elementov, ki so manjsi od i)
1  4  6  6  6  9  11  12  12  12  

Tabela a (po razvrscanju za mesto 1): 
101 411 915 315 721 222 852 655 257 65 67 477

Tabela c (po stetju elementov za mesto 2)
2  1  2  1  2  0  1  1  1  1  

Tabela c (stevilo elementov, ki so manjsi od i)
2  3  5  6  8  8  9  10  11  12  

Tabela a (po razvrscanju za mesto 2): 
65 67 101 222 257 315 411 477 655 721 852 915

Tabela a (po sortiranju): 
65 67 101 222 257 315 411 477 655 721 852 915

Urejenje nizov 

Tabela b (pred sortiranjem): 
Petan Miha
Kolar Peter
Petkovsek Ana
AMBROZ Franc
Zajc Zora
Lah Ljubo
Amon Katja
Lap Lidija
PETEK Peter
Pipan Tone

Tabela b (po sortiranju): 
AMBROZ Franc
Amon Katja
Kolar Peter
Lah Ljubo
Lap Lidija
Petan Miha
PETEK Peter
Petkovsek Ana
Pipan Tone
Zajc Zora

Analiza časovne kompleksnosti

Premiki

n
elementi
m
mesta


  • upoštevamo število premikov, primerjave niso primerljive
  • navidez zelo dobro: O(n)
  • dejansko le redko boljše od quicksorta, ker ne upoštevamo dodatnega dela

Povezave

Vzpostavljeno iz »http://www.e-studij.si/Leksikografsko_sortiranje«
Osebna orodja
Imenski prostori
Različice
Dejanja
navigacija

Tiskanje/izvoz
orodja