어떤 상황에서 mergesort가 선택 정렬보다 빠릅니다.

Question

RAM 모델에 따라 계산할 때 선택 정렬을 사용하여보다 효율적으로 정렬 할 수 있고 mergesort를 사용하여 덜 효율적으로 정렬되는 요소의 수는 매우 낮습니다 (n < < 500000). 그러나 이것을 테스트하려고 시도했을 때, 선택 정렬은 3 분 11 초 만에 500000 개의 요소 배열을 정렬하고 mergesort는 6 분 44 초에 정렬을 찾았습니다. 두 알고리즘의 구현이 정확하다고 확신합니다. 무슨 일이야? 설명 해주십시오.

죄송합니다. 정말 죄송합니다. 네트워크 연결이 끊어졌습니다.

public class MergeSort { 

    // temp array 
    public static int temp[]; 

    public static void merge(int a[], int low, int mid, int high) 
    { 
     temp = new int [a.length]; 
     for(int i = low; i <= high; i++) 
      temp[i] = a[i]; 

     int i = low; 
     int j = mid + 1; 
     int k = low; 

     while(i <= mid && j <= high) 
     { 
      if(temp[i] <= temp[j]) 
      { 
       a[k] = temp[i]; 
       i++; 
      } 

      else 
      { 
       a[k] = temp[j]; 
       j++; 
      } 

      k++; 
     } 

     while(i <= mid) 
     { 
      a[k] = temp[i]; 
      k++; 
      i++; 
     } 
    } 

    public static void sort(int a[], int low, int high) 
    { 
     if(low < high) 
     { 
      int middle = (low + high)/2; 

      // sort the left half 
      sort(a, low, middle); 

      // sort the right half 
      sort(a, middle + 1, high); 

      // merge parts 
      merge(a, low, middle, high); 
     } 
    } 
} 

내 선택 정렬 : 선택 정렬에서

public static int[] selSort(int a[]) 
{ 
    int length = a.length; 
    int temp[] = new int [length]; 

    System.arraycopy(a, 0, temp, 0, length); 

    for(int i = 0; i < length - 1; i++) 
    { 
     int smIndex = i; 

     for(int cIndex = i + 1; cIndex < length; ++cIndex) 
      if(temp[cIndex] < temp[smIndex]) 
       smIndex = cIndex; 

     int t = temp[smIndex]; 
     temp[smIndex] = temp[i]; 
     temp[i] = t; 
    } 

    return temp; 
} 

, 나는 이유에 대한 배열을 복제하고

그래서 여기 내 머지 소트입니다.

Answer 1

merge()는 temp = new int [high + 1 - low] 만 할당해야 할 때 a.length를 기준으로 temp []를 할당합니다. 이 수정 후에는 temp [i]에 대한 참조를 temp [i-low]로 변경해야합니다.

현재 코드를 사용하면 Java는 1 개의 짝수 요소와 1 개의 홀수 요소 (높은 +1 - 낮음 == 2) 만 병합하는 경우에도 500,000 개의 요소 배열을 할당해야합니다.

임시 버퍼를 한 번만 할당 한 다소 최적화 된 하향식 병합 정렬의 예입니다. 그런 다음 상호 재귀 적 기능을 사용하여 복사를 방지합니다. 이 예에서 ee는 끝 색인 == a.length입니다. 이렇게하면 1 초당 1/100 초 안에 500,000 개의 정수가 정렬되고 1.5 초 이내에 10,000,000 개의 정수가 정렬됩니다.

static void MergeSort(int a[]) { 
    if (a.length < 2) 
     return; 
    int []b = new int[a.length]; 
    MergeSortAtoA(a, b, 0, a.length); 
} 

static void MergeSortAtoA(int a[], int b[], int ll, int ee) 
{ 
    if (ee - ll > 1) { 
     int rr = (ll + ee)>>1;   // midpoint, start of right half 
     MergeSortAtoB(a, b, ll, rr); 
     MergeSortAtoB(a, b, rr, ee); 
     Merge(b, a, ll, rr, ee);  // merge b to a 
    } 
} 

static void MergeSortAtoB(int a[], int b[], int ll, int ee) 
{ 
    if (ee - ll > 1) { 
     int rr = (ll + ee)>>1;   //midpoint, start of right half 
     MergeSortAtoA(a, b, ll, rr); 
     MergeSortAtoA(a, b, rr, ee); 
     Merge(a, b, ll, rr, ee);  // merge a to b 
    } else if ((ee - ll) == 1) { 
     b[ll] = a[ll]; 
    } 
} 

static void Merge(int []a, int []b, int ll, int rr, int ee) { 
    int o = ll;       // b[]  index 
    int l = ll;       // a[] left index 
    int r = rr;       // a[] right index 
    while(true){      // merge data 
     if(a[l] <= a[r]){    // if a[l] <= a[r] 
      b[o++] = a[l++];   // copy a[l] 
      if(l < rr)     // if not end of left run 
       continue;    //  continue (back to while) 
      while(r < ee){    // else copy rest of right run 
       b[o++] = a[r++]; 
      } 
      break;      //  and return 
     } else {      // else a[l] > a[r] 
      b[o++] = a[r++];   // copy a[r] 
      if(r < ee)     // if not end of right run 
       continue;    //  continue (back to while) 
      while(l < rr){    // else copy rest of left run 
       b[o++] = a[l++]; 
      } 
      break;      //  and return 
     } 
    } 
}