Тим сортирует ошибку по количеству элементов, которые не являются степенью 2 - PullRequest
Новая
       33

Тим сортирует ошибку по количеству элементов, которые не являются степенью 2

0 голосов
/ 02 ноября 2019

Я пытаюсь реализовать алгоритм Тимсорта для сортировки случайных целых чисел со знаком в неубывающем порядке. Этот алгоритм хорошо сортирует целые числа со знаком, когда число целых чисел относительно мало, однако, когда число становится больше, сортировка кажется неэффективной, когда число целых чисел со знаком не равно 2.

Например, он хорошо сортирует256 случайных целых чисел со знаком, но он не может отсортировать 257, 258, 259, 260 или 261 целое число со знаком. Но тогда он хорошо сортирует 512, 511, 510 целых чисел со знаком. Я не могу найти причину этого противоречивого результата, когда для некоторого числа элементов, которые не являются степенью двойки, он работает, а для некоторых других чисел элементов, которые не являются степенью двойки, он терпит неудачу. 

#include <stdio.h>
#include <stdlib.h>
#include <time.h> 
#include <string.h>
#include <limits.h>
#include <bits/stdc++.h>
#include <stdint.h>

const int RUN = 32;

void insertionSort(int* list, int left, int right){
    for(int i = left+1; i <= right; i++){
    int temp = list[i];
    int j = i - 1;
    while(list[j] > temp && j >= left){
        list[j+1] = list[j];
        j--;
    }
    list[j+1] = temp;
    }
}

void merge(int* list, int l, int m, int r){
    if( l == r) return; //
    int len1 = m - l + 1, len2 = r - m;
    int* left = (int*)malloc(sizeof(int)*len1);
    int* right = (int*)malloc(sizeof(int)*len2);

    for(int i = len1; i--;) left[i] = list[l + i];

    for(int i = len2; i--;) right[i] = list[m + 1 + i];
    int i = 0, j = 0, k = l;
    //merging into larger sub array
    while(i < len1 && j < len2){
    if( left[i] <= right[j]){
            list[k] = left[i];
        i++;
    }
    else{
        list[k] = right[j];
        j++;
        }
    k++;
    }
    //copy remaining part
    while(i < len1){
    list[k] = left[i];
    k++; i++;
    }
    while(j < len2){
    list[k] = right[j];
    k++; j++;
    }
}

void algorithm_4(int* list, int input_size) { //tim sort
   int* list2 = (int*)malloc(sizeof(int)*input_size);
   for(int i = 0; i < input_size; i++){
       list2[i] = list[i+1];
   }
   //for(int i = 1; i <= input_size; i+=RUN){
   for(int i = 0 ; i < input_size; i+=RUN){
     insertionSort(list2, i,std::min((i+31), (input_size-1)));
   }
   for(int size = RUN; size < input_size; size = size * 2){
     for(int left = 0; left < input_size; left += size * 2){
    int right;
    if(input_size - 1 < 2*(2*size - 1)){
           right = input_size -1;
    }
    else right = std::min((left+2*size-1), (input_size-1));
    int mid = (left + right) / 2;
    merge(list2, left, mid, right);
          }
   }
   for(int i = 0; i<input_size; i++){
       list[i+1] = list2[i];
   }
}
...