# Need help identifying and explaining an algorithm

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.
Quote by blake1221

This is not my hometask, this is something I want to understand
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?
Quote by denizenz
I'll logic you right in the thyroid.

Art & Lutherie
Quote by darkstar2466
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?

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,
doesnt say much for my intelligence that i heard "algorithm" and i thought of Prof Farnsworth...
Roses are red
Voilets are blue
The only bulge in my pocket is my wallet
No i'm not happy to see you
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.
Quote by denizenz
I'll logic you right in the thyroid.

Art & Lutherie
Quote by darkstar2466
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,
Quote by gonzaw
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,
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
Quote by denizenz
I'll logic you right in the thyroid.

Art & Lutherie
Quote by darkstar2466
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.
Then please do explain the mystery. I am curious.
Quote by denizenz
I'll logic you right in the thyroid.

Art & Lutherie
Quote by darkstar2466
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.
Quote by Orryn
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
Quote by gonzaw
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,

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
People don't really go to heaven when they die. They're taken to a special place and burned - Sherlock Holmes

Your authority is not recognized in Fort Kickass!

It's not like bullshit, more like poetry.
Quote by Orryn
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.
Quote by denizenz
I'll logic you right in the thyroid.

Art & Lutherie
Last edited by Orryn at Feb 2, 2012,
Quote by Orryn
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,
Quote by gonzaw
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.
This thread might as well be in a different language.
Quote by Orryn
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.
Quote by QPC_Sam
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.
Quote by Orryn
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?
Quote by gonzaw
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?
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.
Quote by denizenz
I'll logic you right in the thyroid.

Art & Lutherie
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 >_>