Sorting Networks with HierarQcal

[Gopal-Dahale]

Purpose

Tutorial on using HierarQcal for Sorting Networks.

Details

• Documented and implemented Bubble, Insertion and Bitonic Sorting Network using HierarQcal.
• Added necessary background on the Sorting Network.
• Demonstrated use of nested Qcycle primitive for Bitonic sort.
• Resolves #50 .

  Mentions

  @matt-lourens

[matt-lourens]

Hey @Gopal-Dahale, this is really great.

It's clear and really uses hierarQcal functionality in a very cool way. I made some comments on the notebook, but it's nothing major, after those small changes #50 will be resolved.

I really liked your use of cycle of cycles in the bitonic sort, the tutorial overall gave me some ideas for hierarQcal improvements. I want to make having a sum of the same motif with only one hyperparamater changing easier (a generalization of the current + functionality).

Anyways thanks for the good work.

[Gopal-Dahale]

I made some comments on the notebook.

Are you yet to make the comments as they are not visible to me?

[matt-lourens]

I made some comments on the notebook.

Are you yet to make the comments as they are not visible to me?

I made them with the review functionality, maybe that doesn't work the way I was expecting, I'll copy them here below:

Comments

• at def create_bitonic_sequence on the 4th line should it not be seq+= for the d_comparator cycle? currently the first layer does only +BM[2],+BM[2],..., should it not do +BM[2],-BM[2],+BM[2],-BM[2],....?

Minor stuff:

• change \textbullet to \bullet in first cell
  • In vscode notebook editor there is a katex parserror for \textbullet, it works in jupyter lab though. If we change it to just \bullet it works in both environments
• spelling in first cell: als -> also
• align vertically the printed "Starting array:" and "Sorted Array:" in the code cells its printed
• in the markdown paragraph below Insertion Network: "compares the element at i it with the elements in the sorted part of the array." just remove the hanging "it"
• under bitonic sort markdown paragraph: "Note that $s_1$ and $s_2$ are both bitonic and each element of $s_1$ is less that every element in $s_2$. " "that" -> "than"
• The cell output of the bitonic_array = hierq(), rather print bitonic sequence instead of sorted array since it's not sorted yet

[Gopal-Dahale]

@matt-lourens Can you review the changes?

[matt-lourens]

Hey @Gopal-Dahale, yeah it's perfect thanks!