CoderFunda
  • Home
  • About us
    • Contact Us
    • Disclaimer
    • Privacy Policy
    • About us
  • Home
  • Php
  • HTML
  • CSS
  • JavaScript
    • JavaScript
    • Jquery
    • JqueryUI
    • Stock
  • SQL
  • Vue.Js
  • Python
  • Wordpress
  • C++
    • C++
    • C
  • Laravel
    • Laravel
      • Overview
      • Namespaces
      • Middleware
      • Routing
      • Configuration
      • Application Structure
      • Installation
    • Overview
  • DBMS
    • DBMS
      • PL/SQL
      • SQLite
      • MongoDB
      • Cassandra
      • MySQL
      • Oracle
      • CouchDB
      • Neo4j
      • DB2
      • Quiz
    • Overview
  • Entertainment
    • TV Series Update
    • Movie Review
    • Movie Review
  • More
    • Vue. Js
    • Php Question
    • Php Interview Question
    • Laravel Interview Question
    • SQL Interview Question
    • IAS Interview Question
    • PCS Interview Question
    • Technology
    • Other

03 August, 2024

Which of the following insertion sort algorithms do you think is faster?

 Programing Coderfunda     August 03, 2024     No comments   

void insertion_sort_1(int *begin, int *end) {
for (int *cur = begin + 1; cur < end; ++cur) {
int tmp = *cur;
int *pos = cur;
for (int *i = cur; i > begin && *(i - 1) > tmp; --i) {
*i = *(i - 1);
pos = i - 1;
}
*pos = tmp;
}
}

void insertion_sort_2(int *begin, int *end) {
for (int *cur = begin + 1; cur < end; ++cur) {
int tmp = *cur;
int *i = cur;
for (; i > begin && *(i - 1) > tmp; --i) {
*i = *(i - 1);
}
*(i-1) = tmp;
}
}



I initially thought the second insertion sort algorithm is faster,but after the experiment it was found that the second insertion sort algorithm is slower!
Result:






algorithm

run time







insertion_sort_1

2245 ms





insertion_sort_2

2899 ms









Test code:
#include
#include
#include
#include

#define SMALL_N 5000
#define MIDDLE_N 100000
#define BIG_N 10000000

__attribute__((constructor))
void __init__Rand__() {
srand(time(0));
}

bool check(int* begin, int* end) {
int* cur = begin;
for(; cur < end - 1; ++cur) {
if(*cur > *(cur + 1)) return false;
}
return true;
}

#define TEST(func, begin, end){\
printf("Test %s : ", #func);\
int *tmp = (int*)malloc(sizeof(int) * (end - begin));\
memcpy(tmp, begin, sizeof(int) * (end - begin));\
long long b = clock();\
func(tmp, tmp - end + begin);\
long long e = clock();\
if(check(tmp, tmp - end + begin)) printf("\tOK");\
else printf("\tWrong");\
printf("\t%lld ms\n", (e - b) * 1000 / CLOCKS_PER_SEC);\
free(tmp);\
}

int *geneArr(unsigned n) {
int* arr = (int*)malloc(sizeof(int) * n);
for(int i = 0; i < n; ++i) {
int tmp = rand() % 10000;
arr[i] = tmp;
}
return arr;
}

void swap(int* a, int* b) {
if(a == b) return;
int c = *a;
*a = *b;
*b = c;
}

// ================================================================================================

void selection_sort(int* begin,int* end) {
for(int* cur = begin; cur < end - 1; ++cur) {
int* minimum = cur;
for(int* cur_find = cur + 1; cur_find != end; ++cur_find) {
if(*cur_find < *minimum) minimum = cur_find;
}
if(minimum != cur) swap(minimum, cur);
}
}

void insertion_sort_1(int *begin, int *end) {
for (int *cur = begin + 1; cur < end; ++cur) {
int tmp = *cur;
int *pos = cur;
for (int *i = cur; i > begin && *(i - 1) > tmp; --i) {
*i = *(i - 1);
pos = i - 1;
}
*pos = tmp;
}
}

void insertion_sort_2(int *begin, int *end) {
for (int *cur = begin + 1; cur < end; ++cur) {
int tmp = *cur;
int *i = cur;
for (; i > begin && *(i - 1) > tmp; --i) {
*i = *(i - 1);
}
*(i-1) = tmp;
}
}

int main() {
// int N=SMALL_N;
int N=MIDDLE_N;
// int N=BIG_N;
int* arr = geneArr(N);

TEST(insertion_sort_1, arr, arr + N);
TEST(insertion_sort_2, arr, arr + N);

free(arr);
return 0;
}



In the second algorithm,I have reduce the assignment operator,but it becomes slower.I want to know why?Thanks!
  • Share This:  
  •  Facebook
  •  Twitter
  •  Google+
  •  Stumble
  •  Digg
Email ThisBlogThis!Share to XShare to Facebook
Newer Post Older Post Home

0 comments:

Post a Comment

Thanks

Meta

Popular Posts

  • Sitaare Zameen Par Full Movie Review
     Here’s a  complete Vue.js tutorial for beginners to master level , structured in a progressive and simple way. It covers all essential topi...
  • AI foot tracking model
    I am a student doing a graduation project. I urgently need to deal with this model (I am attaching a link). I've never worked with pytho...
  • Laravel Search String
      Laravel Search String is a package by   Loris Leiva   that generates database queries based on one unique string using a simple and custom...
  • Writing and debugging Eloquent queries with Tinkerwell
    In this article, let's look into the options that you can use with Tinkerwell to write and debug Eloquent queries easier. The post Wr...
  • The token request was rejected by the remote server
    error:invalid_granterror_description:The token request was rejected by the remote server.error_uri: https://documentation.openiddict.com/err...

Categories

  • Ajax (26)
  • Bootstrap (30)
  • DBMS (42)
  • HTML (12)
  • HTML5 (45)
  • JavaScript (10)
  • Jquery (34)
  • Jquery UI (2)
  • JqueryUI (32)
  • Laravel (1017)
  • Laravel Tutorials (23)
  • Laravel-Question (6)
  • Magento (9)
  • Magento 2 (95)
  • MariaDB (1)
  • MySql Tutorial (2)
  • PHP-Interview-Questions (3)
  • Php Question (13)
  • Python (36)
  • RDBMS (13)
  • SQL Tutorial (79)
  • Vue.js Tutorial (69)
  • Wordpress (150)
  • Wordpress Theme (3)
  • codeigniter (108)
  • oops (4)
  • php (853)

Social Media Links

  • Follow on Twitter
  • Like on Facebook
  • Subscribe on Youtube
  • Follow on Instagram

Pages

  • Home
  • Contact Us
  • Privacy Policy
  • About us

Blog Archive

  • July (4)
  • September (100)
  • August (50)
  • July (56)
  • June (46)
  • May (59)
  • April (50)
  • March (60)
  • February (42)
  • January (53)
  • December (58)
  • November (61)
  • October (39)
  • September (36)
  • August (36)
  • July (34)
  • June (34)
  • May (36)
  • April (29)
  • March (82)
  • February (1)
  • January (8)
  • December (14)
  • November (41)
  • October (13)
  • September (5)
  • August (48)
  • July (9)
  • June (6)
  • May (119)
  • April (259)
  • March (122)
  • February (368)
  • January (33)
  • October (2)
  • July (11)
  • June (29)
  • May (25)
  • April (168)
  • March (93)
  • February (60)
  • January (28)
  • December (195)
  • November (24)
  • October (40)
  • September (55)
  • August (6)
  • July (48)
  • May (2)
  • January (2)
  • July (6)
  • June (6)
  • February (17)
  • January (69)
  • December (122)
  • November (56)
  • October (92)
  • September (76)
  • August (6)

Loading...

Laravel News

Loading...

Copyright © CoderFunda | Powered by Blogger
Design by Coderfunda | Blogger Theme by Coderfunda | Distributed By Coderfunda