Вставка Сортировка по обмену

Question

Я только что начал DSA и задал вопрос о сортировке вставки.

Эта версия из учебников/учебников.

void insertion_sort(int A[], int n) { 
    for (int i = 0; i < n; i++) { 
     int temp = A[i];  
     int j = i; 

     while (temp < A[j - 1] && j > 0) { 
      A[j] = A[j - 1]; 
      j = j - 1; 
     } 
     A[j] = temp;  
    } 
} 

Я думал бы это сделать разницу, если бы мы использовали swapping числа вместо сдвига числа и вставки значения temp в правильном положении отверстия.

void insertionSort(int A[], int n) { 
    for (int i = 0; i < n; i++) { 
     int temp = A[i]; 
     int j = i; 

     while (temp < A[j - 1] && j > 0) { 
      swap(A[j], A[j - 1]); 
      j--; 
     } 
    } 
} 

Своп Код:

void swap(int &a,int &b){ 
    int temp = a; 
    a = b; 
    b = temp; 
} 

О, и это было бы действительно удивительным, если кто-то может объяснить Time Сложности обоих.

Answer 1

Ваша предлагаемая альтернатива неполна, вы не разместили код для swap(). В C swap должен быть макросом, и такой макрос легко загружается, тогда как в C++ он может быть функцией, которая принимает оба аргумента по ссылке.

Кроме того, вы должны проверить j > 0до разыскивается A[j - 1]. Как указано, код вызывает неопределенное поведение.

Что касается ваших вопросов, обе функции одинаково медленно с временной сложностью O (N), но второй потенциально медленнее, потому что подкачка включает в себя больше читает и пишет, чем просто сдвигая значения на одну позицию, но он может быть быстрее на отсортированном массиве, потому что первая версия имеет избыточные магазины.

Обратите внимание, что вы можете еще больше упростить код по цене эффективности таким образом:

void insertionSort(int A[], int n) { 
    for (int i = 1; i < n; i++) { 
     for (int j = i; j > 0 && A[j] < A[j - 1]; j--) { 
      swap(A[j], A[j - 1]); 
     } 
    } 
} 

Answer 2

Временная сложность для обоих подходов O (N^2) в худшем случае. Но число операций во втором подходе больше по сравнению с первым, поскольку второй подход выполняет такое же количество свопов, как и количество сдвигов в первом подходе, но своп требует 3 присвоений по сравнению с одним в на основе сдвига подход. Следовательно, предложенный вами метод будет медленнее по сравнению с просто перемещением элементов.

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <stdint.h> 

void insertion_shift(int* arr, int n){ 
    int i,j,k; 
    for(i=1;i<n;++i){ 
     int temp=arr[i]; 
     for(j=i;j>0 && arr[j-1]>temp;--j) 
      arr[j]=arr[j-1]; 
     arr[j]=temp; 
    } 
} 
void swap(int* a, int* b){ 
    int temp= *a; 
    *a= *b; 
    *b= temp; 
} 

void insertion_swap(int* arr, int n){ 
    int i,j,k; 
    for(i=1;i<n;++i){ 
     int temp=arr[i]; 
     for(j=i;j>0 && arr[j-1]>temp;--j) 
     swap(&arr[j-1],&arr[j]); 
    } 
}  

void print_arr(int* arr, int n){ 
    int i; 
    for(i=0;i<n;++i) 
     printf("%d ",arr[i]); 
    printf("\n"); 
} 

int main(){ 
    int n; 
    scanf("%d",&n); 
    int* arr1= (int*)malloc(sizeof(int)*n); 
    int* arr2= (int*)malloc(sizeof(int)*n); 
    int i; 
    for(i=0;i<n;++i){ 
     scanf("%d",&arr1[i]); 
     arr2[i]=arr1[i]; 
    } 

    struct timespec start, end; 
    clock_gettime(CLOCK_MONOTONIC_RAW,&start); 
    insertion_shift(arr1,n); 
    clock_gettime(CLOCK_MONOTONIC_RAW,&end); 
    uint64_t time_shift= (end.tv_sec - start.tv_sec)*1000000 + 
         (end.tv_nsec - start.tv_nsec)/1000; 
    printf("using shift: %lld microseconds\n",time_shift); 

    clock_gettime(CLOCK_MONOTONIC_RAW,&start); 
    insertion_swap(arr2,n); 
    clock_gettime(CLOCK_MONOTONIC_RAW,&end); 

    uint64_t time_swap= (end.tv_sec - start.tv_sec)*1000000 + 
         (end.tv_nsec - start.tv_nsec)/1000; 
    printf("using swap: %lld microseconds\n",time_swap); 

}

Вот что я получил, когда я назвал обе функции в одном массиве размером 10000. Compilation and execution for 10000 elements array. Если вы все еще не уверены, попробуйте создать случайный массив размером 1000-10000 и запустите вышеуказанный код, чтобы заметить разницу.