#1

Basically, here's the picture:

12 random numbers need to be sorted in ascending order, we use 4 files in order to do this

97 20 53 04 32 15 50 89 48 95 04 37 n = 12

F1 97, 04 32 48 95

F2 20 53, 15 50 89, 04 37

F3 20 53 97, 04 37

F4 04 15 32 48 50 89 95

F1 04 15 20 32 48 50 53 89 95 97

F2 04 37

F3 04 04 15 20 32 37 48 50 53 89 95 97

I understand the FIRST 2 steps with F1 and F2 and lose any idea after that.

12 random numbers need to be sorted in ascending order, we use 4 files in order to do this

97 20 53 04 32 15 50 89 48 95 04 37 n = 12

F1 97, 04 32 48 95

F2 20 53, 15 50 89, 04 37

F3 20 53 97, 04 37

F4 04 15 32 48 50 89 95

F1 04 15 20 32 48 50 53 89 95 97

F2 04 37

F3 04 04 15 20 32 37 48 50 53 89 95 97

I understand the FIRST 2 steps with F1 and F2 and lose any idea after that.

#2

#3

This is not my hometask, this is something I want to understand

#4

Some sort of weird mergesort. You'll notice that the first F3 and F4 are merged variations of F1 and F2. Subsequently, the next F1 and F2 are merged steps from the last F3 and F4, with the final F3 being the sorted list.

Really. Weird. Algorithm. Wtf is this shit?

Really. Weird. Algorithm. Wtf is this shit?

#5

Some sort of weird mergesort. You'll notice that the first F3 and F4 are merged variations of F1 and F2. Subsequently, the next F1 and F2 are merged steps from the last F3 and F4, with the final F3 being the sorted list.

Really. Weird. Algorithm. Wtf is this shit?

Let me upload a picture

Here,

Also, our teacher said something about

http://en.wikipedia.org/wiki/Shellsort

But I don't see any "connection" between the two

*Last edited by Orryn at Feb 2, 2012,*

#6

doesnt say much for my intelligence that i heard "algorithm" and i thought of Prof Farnsworth...

#7

Ahhh, I should've known it was shellsort. This is the one where Sedgewick brought down the running time to O(N^(4/3)).

Shellsort relies on gaps and swapping things through runs in place. Just read the 'Description' section of the wiki page - very self evident.

Shellsort relies on gaps and swapping things through runs in place. Just read the 'Description' section of the wiki page - very self evident.

#8

Ahhh, I should've known it was shellsort. This is the one where Sedgewick brought down the running time to O(N^(4/3)).

Shellsort relies on gaps and swapping things through runs in place. Just read the 'Description' section of the wiki page - very self evident.

Didn't help.

Can you SHOW and EXPLAIN the F3 and F4?

Edit:

I understand the shells sorting, but THIS doesn't look like it

*Last edited by Orryn at Feb 2, 2012,*

#9

Didn't help.

Can you SHOW and EXPLAIN the F3 and F4?

Edit:

I understand the shells sorting, but THIS doesn't look like it

Isn't F3 just a middle step of the insertion sort?

As in, it's not finished?

But wait, that isn't shellsort, why isn't it sorted through gaps?

Wtf? lol

#11

Isn't F3 just a middle step of the insertion sort?

As in, it's not finished?

But wait, that isn't shellsort, why isn't it sorted through gaps?

Wtf? lol

That's the point, it ain't shell sorting, it's some... random... shit...

edit:

I got the algorithm, I know how it works, thanks guys.

*Last edited by Orryn at Feb 2, 2012,*

#12

I'm gonna go ahead and say this sort makes no fu

d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 d11

97 20 53 04 32 15 50 89 48 95 04 37

F1:

97 04 32 48 95

d0 d3 d4 d8 d9

F2:

20 53 15 50 89 04 37

d1 d2 d5 d6 d7 d10 d11

**cking sense. The indices in F1 and F2 don't make any sense at all..**d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 d11

97 20 53 04 32 15 50 89 48 95 04 37

F1:

97 04 32 48 95

d0 d3 d4 d8 d9

F2:

20 53 15 50 89 04 37

d1 d2 d5 d6 d7 d10 d11

#13

I'm gonna go ahead and say this sort makes no fucking sense. The indices in F1 and F2 don't make any sense at all..

d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 d11

97 20 53 04 32 15 50 89 48 95 04 37

F1:

97 04 32 48 95

d0 d3 d4 d8 d9

F2:

20 53 15 50 89 04 37

d1 d2 d5 d6 d7 d10 d11

It does, I got it figured out!

This ain't shell sorting for sure, though.

#14

Then please do explain the mystery. I am curious.

#15

Then please do explain the mystery. I am curious.

Okay!

97 20 53 04 32 15 50 89 48 95 04 37

Okay, so this is our array, we take the first number,

(97)>20 so we put in into F1,

(20<53)>04 we put into F2,

(04<32)>15 we put into F1,

(15<50<89)>48 we put into F2,

(48<95)> 04 we put into F1,

(04<37) we put into F2

So now we have 2 arrays, F1 and F2

F1 (97), (04 32 48 95)

F2 (20 53), (15 50 89), (04 37)

^ important to keep the groups separated

Now we take the 1st group of F1 and F2 and unite them

(97)+(20 53)= (97 20 53) and now we sort it (20 53 97) and put it into F3

Now we take the 2ond group of F1 and F2 and unite them

(04 32 48 95)+(15 50 89)= (15 50 89 04 32 48 95) and sort it (04 15 32 48 50 89 95), put it into F4

Now we take the 3rd group of F1 and F2 and unite them

( )+(04 37)= (04 37) and sort if (04 37) and put it into F3

Now we have

F3 (20 53 97), (04 37)

F4 (04 15 32 48 50 89 95)

Now we're doing the same thing as the previous step with F1 and F2, except, we are over-writing F1 and F2, because it's related to programming and we want to use as less memory as possible

1st group of F3 and F4, (20 53 97 04 15 32 48 50 89 95) and sort it, put into F1

2ond group of F3 and F4, (04 37) and sort it, put into F2

Now we have

F1 (04 15 20 32 48 50 53 89 95 97)

F2 (04 37)

And now we just unite them, sort them, and re-write it into F3, done.

#16

Okay!

97 20 53 04 32 15 50 89 48 95 04 37

Okay, so this is our array, we take the first number,

(97)>20 so we put in into F1,

(20<53)>04 we put into F2,

(04<32)>15 we put into F1,

(15<50<89)>48 we put into F2,

(48<95)> 04 we put into F1,

(04<37) we put into F2

So now we have 2 arrays, F1 and F2

F1 (97), (04 32 48 95)

F2 (20 53), (15 50 89), (04 37)

^ important to keep the groups separated

Now we take the 1st group of F1 and F2 and unite them

(97)+(20 53)= (97 20 53) and now we sort it (20 53 97) and put it into F3

Now we take the 2ond group of F1 and F2 and unite them

(04 32 48 95)+(15 50 89)= (15 50 89 04 32 48 95) and sort it (04 15 32 48 50 89 95), put it into F4

Now we take the 3rd group of F1 and F2 and unite them

( )+(04 37)= (04 37) and sort if (04 37) and put it into F3

Now we have

F3 (20 53 97), (04 37)

F4 (04 15 32 48 50 89 95)

Now we're doing the same thing as the previous step with F1 and F2, except, we are over-writing F1 and F2, because it's related to programming and we want to use as less memory as possible

1st group of F3 and F4, (20 53 97 04 15 32 48 50 89 95) and sort it, put into F1

2ond group of F3 and F4, (04 37) and sort it, put into F2

Now we have

F1 (04 15 20 32 48 50 53 89 95 97)

F2 (04 37)

And now we just unite them, sort them, and re-write it into F3, done.

How do you "sort" F1, F4 and stuff?

What are the advantages of that? You are sorting the same numbers like 3 times in different groups

#17

How do you "sort" F1, F4 and stuff?

What are the advantages of that? You are sorting the same numbers like 3 times in different groups

What do you mean by how do I sort F1 and F4?

The advantage is that we can take up some of physical memory on the computer instead of ram to store some information(file1, file2, file3, file4) which will drastically improve speed since ram is significantly smaller than hard drive.

It's group sorting, the groups become bigger and more "sorted" along the way, most of the time it's must faster to sort it by parts and groups than just sorting the original array in 1 action.

*Last edited by Orryn at Feb 2, 2012,*

#18

for i = 1:n,

k = i

for j = i+1:n, if a[j] < a[k], k = j

→ invariant: a[k] smallest of a[i,k]

→ invariant: a[1..i] in final position

end

#19

What do you mean by how do I sort F1 and F4?

The advantage is that we can take up some of physical memory on the computer instead of ram to store some information(file1, file2, file3, file4) which will drastically improve speed since ram is significantly smaller than hard drive.

The memory hierarchy goes, largest to smallest, in order of access, and latency:

Hard drive --> Main memory --> L3 cache --> L2 cache --> L1 cache --> Registers

Hard drive accesses are the slowest - you want to avoid them. Main memory is where you want to run your entire program from. Using files is very slow compared to in-memory processing.

#20

*Last edited by Orryn at Feb 2, 2012,*

#21

What do you mean by how do I sort F1 and F4?

There are parts where you say "Then we just sort the group".

I mean, your initial problem was sorting a group of n=12 elements, so how do you "sort" these "auxiliary" groups?

Do you use another algorithm or do you make it recursive?

Either way, the order of this algorithm is massive I think. Must be n³ or something.

The advantage is that we can take up some of physical memory on the computer instead of ram to store some information(file1, file2, file3, file4) which will drastically improve speed since ram is significantly smaller than hard drive.

It's group sorting, the groups become bigger and more "sorted" along the way, most of the time it's must faster to sort it by parts and groups than just sorting the original array in 1 action.

Besides cache and registers, RAM has the fastest access time out there, so that's completely backwards

Also, to "store" the "groups" you need a lot of memory, with structures and shit.

That takes up space, and also time (when trying to access each group, search each element, etc).

EDIT:

*Last edited by gonzaw at Feb 2, 2012,*

#22

There are parts where you say "Then we just sort the group".

I mean, your initial problem was sorting a group of n=12 elements, so how do you "sort" these "auxiliary" groups?

Do you use another algorithm or do you make it recursive?

Either way, the order of this algorithm is massive I think. Must be n³ or something.

Besides cache and registers, RAM has the fastest access time out there, so that's completely backwards

Also, to "store" the "groups" you need a lot of memory, with structures and shit.

That takes up space, and also time (when trying to access each group, search each element, etc).

EDIT:

Selection sort?

That's a possibility.

I prefer Mergesort though (**** Quicksort )

We use the bubble method to sort the joined group of 2, for example (12 85 49 05) into (05 12 49 85), basically we are using more than one algorithm, one to sort groups, one to sort the group itself.

#23

This thread might as well be in a different language.

#24

Now we take the 1st group of F1 and F2 and unite them

(97)+(20 53)= (97 20 53) and now we sort it (20 53 97) and put it into F3

Now we take the 2ond group of F1 and F2 and unite them

(04 32 48 95)+(15 50 89)= (15 50 89 04 32 48 95) and sort it (04 15 32 48 50 89 95), put it into F4

Now we take the 3rd group of F1 and F2 and unite them

( )+(04 37)= (04 37) and sort if (04 37) and put it into F3

I mostly agree with you, but why unite the two sets and then sort them? They are ordered lists due the manner in which they were formed, so they just need merging.

eg:

(04 32 48 95);(15 50 89)

4 is the smallest of the starting numbers so it becomes the first of the new list and delete it:

(04) --- (32 48 95);(15 50 89)

Now 15 is the smallest starting number so it becomes the second of the new list and delete it, etc. You end up with (04 32 48 95);(15 50 89) merged into one ordered list.

#25

I mostly agree with you, but why unite the two sets and then sort them? They are ordered lists due the manner in which they were formed, so they just need merging.

eg:

(04 32 48 95);(15 50 89)

4 is the smallest of the starting numbers so it becomes the first of the new list and delete it:

(04) --- (32 48 95);(15 50 89)

Now 15 is the smallest starting number so it becomes the second of the new list and delete it, etc. You end up with (04 32 48 95);(15 50 89) merged into one ordered list.

In terms of programming, what I described seems to be much simpler I believe.

#26

We use the bubble method to sort the joined group of 2, for example (12 85 49 05) into (05 12 49 85), basically we are using more than one algorithm, one to sort groups, one to sort the group itself.

Okay, but what are the advantages of this algorithm?

Does it have a good order? For worst case scenario? Average scenario?

Is it stable at least? Or does it use less memory (which I doubt)?

In which case would it be better to use this algorithm than to use Quicksort/Mergesort/others?

#27

Okay, but what are the advantages of this algorithm?

Does it have a good order? For worst case scenario? Average scenario?

Is it stable at least? Or does it use less memory (which I doubt)?

In which case would it be better to use this algorithm than to use Quicksort/Mergesort/others?

This.

The fact that it uses the bubble sort several times within the sorting algorithm, which uses 2 separate arrays, looks highly inefficient. What is

*n*?

#28

By and large, this appears to be a useless algorithm for practice lol. Considering that you use four files to arrange the intermediary sort results, you end up using 4N space in four files for N = 12.

#29

Also, if you take the worst case scenario (I think it's an array ordered in a descendant fashion), you do get like O(n³ or worse I think.

But thinking of a worst case scenario here is kind of difficult since you have to sort like a million auxiliary groups, and those come "pre-sorted" from before >_>

But thinking of a worst case scenario here is kind of difficult since you have to sort like a million auxiliary groups, and those come "pre-sorted" from before >_>