/prog/ - InsertionSort on sorted arrays

Name: Anonymous 2011-09-11 20:47

can anyone say at which point it is preferable to use InsertionSort instead of MergeSort.
I don't mean at array size but at how much of the array is already sorted

so anyone has any idea, 95%, 97%, 99% sorted?

Name: Anonymous 2011-09-11 21:03

Why, if you can use a Fibonacci Butt Sort at all times?

Name: Anonymous 2011-09-11 21:06

not stable

Name: n3n7i 2011-09-11 21:57

No idea really...

Are you building like a hybrid sort? Or does it sort, then add some data and sort again?

>>If in the latter case, are there possible lower val's ? or will all the new data be higher than the last sorted Value? (assuming it must make some difference..?)

Name: n3n7i 2011-09-11 22:25

Ooh, what about a Burst-blank-insert// for all values less than the highest last sorted value?

...might Require n- extra memory / array items? (where n = No of values < H. L. S)

Name: Anonymous 2011-09-11 22:30

it is a hybrid, a mergesort that uses insertionsort in less than 16 elements or 98% sorted (this info is either given or got by monte carlo)

Name: Anonymous 2011-09-11 22:35

i'd use some variant of strandsort in the bigger picture didn't need arrays, it's a pretty sweet disjoint sets implementation with 3n cost on linearly distributed data, this sorting just fucks me over

Name: n3n7i 2011-09-11 22:56

Eg



1, 2, 4, 5, 7, 8, 10, 11, 12,(<<Sorted // new >>) 15, 13, 9, 14, 6, 



Sort new data? (15, 13, 9, 14, 6 >> 6, 9, 13, 14, 15)



1, 2, 4, 5, 7, 8, 10, 11, 12,  6, 9, 13, 14, 15



n=2 (6, 9 < 12 // 13, 14, 15 > 12)



Add two entries? 



1, 2, 4, 5, 7, 8, 10, 11, 12, 6, 9, 13, 14, 15, _, _,



Switch-out?



1, 2, 4, 5, 7, 8, [10, 11, 12,] _, _, 13, 14, 15, 6, 9



step 2 (12> x >9)



1, 2, 4, 5, (7, 8,) _, _, [10, 11, 12,] 13, 14, 15, 6, 9



step 1 (9> x >6)



1, 2, 4, 5, _, (7, 8,) _, 10, 11, 12, 13, 14, 15, 6, 9

Name: Anonymous 2011-09-11 23:02

>>8 cretin

Name: Anonymous 2011-09-12 0:28

>>9
He's on his way to become a Lisper!

Name: n3n7i 2011-09-12 2:26

That should be faster than inserting one byte at a time?

The already-sorted bytes that do need to be moved are only moved once, step n [Compared with moved n times, step 1]

//Gets faster with larger n-values? (minus initial sort?)

Name: n3n7i 2011-09-12 2:58

Quicksort does/uses swaps... But if you have Blanks you only need to do half a swap?

Use quicksort or whichever just to sort the new entries ?

B-b-i ?

fill in the blanks?

Name: n3n7i 2011-09-12 3:23

the pleasure of increasing the mean ``quality of post'' where name="n3n7i"

Name: n3n7i 2011-09-12 3:25

wow.

you guys are even more retarded than on /b/

even they were more help.

lol STFU and GTFO

(PS : I have a PhD in computer science - does not mean that I know everything you do, but sure means I know fuckloads more than that.)

Name: Anonymous 2011-09-12 3:29

STFU and GTFO

Name: n3n7i 2011-09-12 4:35

=) i Never went to uni....

Name: Anonymous 2011-09-12 5:54

>>16
It shows

Name: Anonymous 2011-09-12 12:04

OP here, I went with a 98% ratio

>>12
QuickSort doesn't help at all, it doesn't take already sorted data into consideration and is not stable and efficient at the same time

Name: Anonymous 2011-09-12 12:26

>>16
Who would have guessed?

Name: n3n7i 2011-09-12 15:09

i phuq g0atz

Name: Anonymous 2011-09-12 15:26

if you have a sorter array, why don't you simple use binary search to find place of new elements and insert them?

Name: Anonymous 2011-09-12 16:20

>>12
Quicksort does/uses swaps... But if you have Blanks you only need to do half a swap?

Not all swaps are created equals. Some languages can do it more efficiently than others.

Name: Anonymous 2011-09-12 16:22

>>14
Wow, you hold a Ph.D. in computer science, and yet, you made what has to be freshmen levelish mistake regarding swap? Wow. Wtf? Did you get your Ph.D at some loser school like San Diego State?

Name: Anonymous 2011-09-12 19:27

http://www.facebook.com/n3n7i

Name: Anonymous 2011-09-12 19:32

>>24

is this real life?

Name: n3n7i 2011-09-12 22:13

>>24
Hey! That's private... =)

Name: Anonymous 2011-09-12 22:22

>>26 cretin

Name: tdavis 2011-09-12 22:42

>>23
My first exposure to paging was at Ticketmaster. The idea was, to give users enough memory. I got the term "virtual memory" in my head and used it (wrongly) even when not swapping to disk. That's just "paging". In general, personally, I'm not good with standard terminology and sloppily use the first word that pops in my head instead of doing research to find what everybody else calls it.

God says...
Line: 12768

6:22 And the LORD spake unto Moses, saying, 6:23 Speak unto Aaron and
unto his sons, saying, On this wise ye shall bless the children of
Israel, saying unto them, 6:24 The LORD bless thee, and keep thee:
6:25 The LORD make his face shine upon thee, and be gracious unto
thee: 6:26 The LORD lift up his countenance upon thee, and give thee
peace.

6:27 And they shall put my name upon the children of Israel, and I
will bless them.

Name: n3n7i 2011-09-12 22:46

You can all make ID's now... if you like?
Everyone seems to be preoccupied with my five alphanumerics anyway...

Did that sort not work// Or you just didn't follow it (Didn't exactly explain very well eh)?

Question, did you actually need to resort data or nope?
Might be good for a variant of your problem>?

Name: tdavis 2011-09-12 22:50

>>28

The rule of thumb for guessing how long asm code would take was to count memory referrences. That's no longer practical. When I made LoseThos not use paging, I thought, "If I get rid of 3 levels of indirection, it should be much faster!" CPU's do a good job of eliminating the penalty for all the indirection present in paging. Long mode (64-bit mode) requires paging. I identity map. The founding principle was all-ring-0 and no paging or at least identity-mapping. Both those boost performance (marginally).

Name: n3n7i 2011-09-12 23:04

http://www.youtube.com/watch?v=__PU5CVSegg

Name: Anonymous 2011-09-12 23:11

>>31

Google "64-bit Operating system"

I'm the winner.

I beat all these guys.

http://wiki.osdev.org/Projects

Name: !hKD42dyBMw 2011-09-12 23:12

sss

Name: !eSlu3.6Gdk 2011-09-12 23:13

#29nfks#29nfks#29nfks#29nfks#29nfks#29nfks#29nfks#29nfks

Name: tdavis 2011-09-12 23:18

>>31
LoseThos is an operating system. Linux is just a kernel. GNU/Linux is an operating system.

These guys do not make compilers
http://wiki.osdev.org/Projects

They make pointless Linux wannabes. The ONLY ISSUE in OSDEV for PCs is compatibility. You're delusional if you think people will write drivers for you.

Name: Anonymous 2011-09-12 23:27

Too bad LoseThos will never be popular enough to justify its shitty existence.

Name: Anonymous 2011-09-12 23:28

>>35
You're delusional if you think people will write drivers for you.
Fuck you faggot.

Name: tdavis 2011-09-12 23:33

>>37
amateur

Name: Anonymous 2011-09-12 23:38

>>38
Faggot.

Name: n3n7i 2011-09-12 23:42

>>"You're delusional if you think people will write drivers for you."

That would probably depend on the perceived Merit/Benefit of doing so?> ...you might be lucky? =)

Name: n3n7i 2011-09-12 23:53

http://www.youtube.com/watch?v=99LqZ66-jZo

Name: n3n7i 2011-09-13 0:03

>>17 >>19 so what's your excuse? =)

Name: Sussex Dev Team 2011-09-13 0:27

>>40,42

Please stop decreasing the average quality of posts where the name field is equal to the string "n3n7i".



Thank you.

Name: Anonymous 2011-09-13 0:30

>>41
http://www.youtube.com/watch?v=v01MIdWPnKk

Name: Anonymous 2011-09-13 0:43

>YouTube Reactions
>YouTube tests a new feature that allows users to express their reactions without posting silly comments. They can just click one of the six buttons (LOL, OMG, EPIC, CUTE, WTF, FAIL) and instantly tag the video.
One step closer to Idiocracy.

Name: n3n7i 2011-09-13 1:42

i am a faggot please rape my face

Name: n3n7i 2011-09-13 6:10

>>46
=)

Name: Anonymous 2011-09-13 8:10

ehh, what do you guys mean by 98% sorted? The only metric I can think of would be the number of inversions. But yeah, you could probably figure out from the number of inversions how many array assignment operations would be performed by a simple implementation of insertion sort, merge sort, quick sort, and such, although it would be difficult. The actual performance on a CPU with a cache can depend on a lot more it might be better to test implementations empirically by timing their execution on different types of arrays, and see how they do. Also, quick sort is the bestest.

Name: Anonymous 2011-09-13 10:42

I like how the LoseThos guy calls people ``delusional''.

InsertionSort on sorted arrays

1 Name: Anonymous 2011-09-11 20:47

2 Name: Anonymous 2011-09-11 21:03

3 Name: Anonymous 2011-09-11 21:06

4 Name: n3n7i 2011-09-11 21:57

5 Name: n3n7i 2011-09-11 22:25

6 Name: Anonymous 2011-09-11 22:30

7 Name: Anonymous 2011-09-11 22:35

8 Name: n3n7i 2011-09-11 22:56

9 Name: Anonymous 2011-09-11 23:02

10 Name: Anonymous 2011-09-12 0:28

11 Name: n3n7i 2011-09-12 2:26

12 Name: n3n7i 2011-09-12 2:58

13 Name: n3n7i 2011-09-12 3:23

14 Name: n3n7i 2011-09-12 3:25

15 Name: Anonymous 2011-09-12 3:29

16 Name: n3n7i 2011-09-12 4:35

17 Name: Anonymous 2011-09-12 5:54

18 Name: Anonymous 2011-09-12 12:04

19 Name: Anonymous 2011-09-12 12:26

20 Name: n3n7i 2011-09-12 15:09

21 Name: Anonymous 2011-09-12 15:26

22 Name: Anonymous 2011-09-12 16:20

23 Name: Anonymous 2011-09-12 16:22

24 Name: Anonymous 2011-09-12 19:27

25 Name: Anonymous 2011-09-12 19:32

26 Name: n3n7i 2011-09-12 22:13

27 Name: Anonymous 2011-09-12 22:22

28 Name: tdavis 2011-09-12 22:42

29 Name: n3n7i 2011-09-12 22:46

30 Name: tdavis 2011-09-12 22:50

31 Name: n3n7i 2011-09-12 23:04

32 Name: Anonymous 2011-09-12 23:11

33 Name: !hKD42dyBMw 2011-09-12 23:12

34 Name: !eSlu3.6Gdk 2011-09-12 23:13

35 Name: tdavis 2011-09-12 23:18

36 Name: Anonymous 2011-09-12 23:27

37 Name: Anonymous 2011-09-12 23:28

38 Name: tdavis 2011-09-12 23:33

39 Name: Anonymous 2011-09-12 23:38

40 Name: n3n7i 2011-09-12 23:42

41 Name: n3n7i 2011-09-12 23:53

42 Name: n3n7i 2011-09-13 0:03

43 Name: Sussex Dev Team 2011-09-13 0:27

44 Name: Anonymous 2011-09-13 0:30

45 Name: Anonymous 2011-09-13 0:43

46 Name: n3n7i 2011-09-13 1:42

47 Name: n3n7i 2011-09-13 6:10

48 Name: Anonymous 2011-09-13 8:10

49 Name: Anonymous 2011-09-13 10:42