algorytm.org

Implementacja w Java



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sortowanie przez scalanie (mergesort) - Implementacja w Java
Ocena użytkownikóww: *****  / 11
SłabyŚwietny
Nadesłany przez gchlebus, 28 lutego 2011 02:18
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

merge_1_j.java:
// Sortowanie przez scalanie (mergesort)
// www.algorytm.org

package mergesort;

public class merge_sort {
    public static void mergeSort(int tab[], int l, int r){

        int DividePoint = dividePoint(l,r);

        if (r!=l){
            mergeSort(tab, l, DividePoint);
            mergeSort(tab, DividePoint+1, r);

            //pointers used to refer to content of arrays
            int ptrA = l;
            int ptrB = DividePoint+1;

            int i = 0;
            int[] temptab = new int[r-l+1];

            //join two arrays into one sorted array
            while(ptrA<=DividePoint && ptrB<=r){
                if (compare(tab[ptrA], tab[ptrB])){
                    temptab[i++] = tab[ptrA++];
                }else{
                    temptab[i++] = tab[ptrB++];
                }
            }
            if (ptrA>dividePoint(l,r)){         //if all elements of first array
                                                //were used add rest of second
                                                //array to the end of temporary
                                                //array
                for (int j = ptrB; j<=r; j++){
                    temptab[i++] = tab[j];
                }
            }else{                              //opposite case
                for (int j = ptrA; j<=dividePoint(l,r); j++){
                    temptab[i++] = tab[j];
                }
            }
            //copy results
            copy(tab, temptab, l,r);
        }

    }
  
  private static int dividePoint(int l, int r){
      //calculates divide point of array
      int tabLength = r-l+1;
      if (tabLength%2 == 0){
          return l-1+(tabLength)/2;
      }else{
          return l+tabLength/2;
      }
  }

  private static boolean compare(int num1, int num2){
      if (num1 > num2) return false;
      if (num1 < num2) return true;
      else
          return true;
  }

  private static void copy(int tab[], int temptab[], int l, int r){
      //copies result from temporary array to original array
      int j=0;
      for (int i=l; i<=r; i++){
          tab[i] = temptab[j++];
      }

  }
}
Dodaj komentarz