Bubble Sort In Julia Lang
Julia is that "new new", the programming language that developers are swooning over. Even my one professor, Doug Williams, who may as well be Dr. Racket himself is jumping shit and boarding the SS Julia.
As I work though my graduate degree in Computer Science, I've committed to getting some Julia experience under my belt - especially in my Algorithms course. One thing I've noticed in my foray into Julia is that there is pretty limited documentation compared to the other languages I've worked with extensively - namely Python and C++. Of course, the first full version of Julia was released about a month ago, so the community is small, but quickly growing. Often, I don't feel that I'm able to contribute to those communities in a meaningful way because of their size, and so I'm taking advantage of this opportunity to contribute to the Julia community and post some of the code I'm writing and lessons I'm learning.
Without further adieu...
Bubble sort is a naive sorting algorithm, which means that it will check and compare every element in the list to be sorted. In terms of code this means one for loop to iterate through the list, and a second nested for loop to compare each element from the first loop against all the others in the list. This nested for loop structure is what results in a time complexity of O(n^2).
If you've used MATLAB and/or Python and/or C++ before, this syntax will probably feel fairly intuitive. The most important things to remember when in Julia are:
1) Arrays index from 1, not 0
2) You don't need semicolons everywhere
3) No curly brackets - but you do need end statements
Below is the basic Bubble Sort algorithm for sorting an array.
Full code can be found at:
# Written by Katrina Siegfried # 2018-09-15 # CSCI3412_Algorithms # BubbleSort algorithm written from notes from DataStructures function bubbleSort(list) numberOfSwaps = 0 numberOfComparisons = 0 len = length(list) for i = 1:len-1 for j = 2:len numberOfComparisons += 1 if list[j-1] > list[j] tmp = list[j-1] list[j-1] = list[j] list[j] = tmp numberOfSwaps += 1 end end end println("Number of swaps: ", numberOfSwaps) println("Number of comparisons: ", numberOfComparisons) end # UNCOMMENT CODE BELOW TO PRINT UNSORTED LIST for i = 1:length(listToSort) # println(listToSort[i]) end # CALL BUBBLE SORT AND BENCHMARK IT println("Bubble Sort") @time bubbleSort(listToSort) writedlm("sortResults.txt", listToSort) # UNCOMMENT CODE BELOW TO PRINT SORTED LIST for i = 1:length(listToSort) println(listToSort[i]) end