GSoC/GCI Archive
GSoC/GCI Archive
Google Code-in 2011 Parrot Foundation

Implement Smoothsort algorithm in Winxed for Rosella

completed by: Ayanami Rei

mentors: Andrew Whitworth

Task Description

Rosella would like to provide several sorting algorithms, since different algorithms perform differently on inputs with different characteristics. The default sorting algorithm in Rosella currently is a lightly optimized quicksort, although a combination of quicksort+insertion sort, and a new implementation of Timsort are both being benchmarked and considered. Rosella would like to have other modern sorting algorithms as well, especially Smoothsort.

Provide an implementation of Smoothsort in Winxed for Rosella. The implementation may be basic and does not need to be optimized. Add an implementation of Smoothsort to the file benchmarks/query/sort.winxed, along side quicksort and Timsort implementations (For testing, you can comment out some of the other sorts, or modify parameters).

It is more important for the algorithm to be functionally correct than for it to be particularly fast. Optimization can happen later.

Please make sure to follow existing coding conventions and add comments necessary to tell what is happening at each stage of the algorithm.

Steps To Complete This Task

  1. Create a fork of Rosella.git on github.com
  2. Implement the Smoothsort algorithm in the file benchmarks/query/sort.winxed
  3. Run the benchmark to prove that the code compiles and runs correctly. You may want to add additional debugging output to the file as well.
  4. Create a Github pull request (button on the upper right of your fork) to have your changes incorporated into the master repository

Benefits

  1. Different sort algorithms have different best and worst case runtimes and run characteristics depending on the characteristics of the input. Best case, worst case, average case and other metrics are all important. It is important that Rosella be able to provide a good sorting algorithm for the common case, but also be able to provide additional algorithms if the input is known to have certain properties. A smooth sort algorithm is an interesting, good-performance sort to include.

Requirements

  1. Familiarity with sorting and algorithms in general
  2. Familiarity with Winxed or related languages (C, C++, C#, Java and JavaScript)

Additional Links