Skip to content

Designing a sorting algorithm

Bubble sort

function main()

  var myArray = Array<Int32>(5);
  myArray[0] = 41;
  myArray[1] = 40;
  myArray[2] = 43;
  myArray[3] = 44;
  myArray[4] = 42;


  print("Unsorted:");
  for (i in 0:myArray.count())
    print(toString(myArray[i]) + " ");
  endfor
  printLn("");

  bubble_sort(myArray);

  print("Sorted:");
  for (i in 0:myArray.count())
    print(toString(myArray[i]) + " ");
  endfor
  printLn("");

endfunction


function bubble_sort(an_array :Array<Int32>)

    var more_swaps : Bool = true;

    while(more_swaps == true)

      more_swaps = false;

      for (i in 0:an_array.count()-1) 

          if (an_array[i] > an_array[i + 1])

              more_swaps = true;

              var temp = an_array[i];
              an_array[i] = an_array[i + 1];
              an_array[i + 1] = temp;

          endif
      endfor

    endwhile

endfunction

Insertion sort

function main()

  var myArray = Array<Int32>(5);
  myArray[0] = 41;
  myArray[1] = 40;
  myArray[2] = 43;
  myArray[3] = 44;
  myArray[4] = 42;


  print("Unsorted:");
  for (i in 0:myArray.count())
    print(toString(myArray[i]) + " ");
  endfor
  printLn("");

  insertion_sort(myArray);

  print("Sorted:");
  for (i in 0:myArray.count())
    print(toString(myArray[i]) + " ");
  endfor
  printLn("");

endfunction


function insertion_sort(an_array :Array<Int32>)


    for(index in 1:an_array.count()) 

      var currentvalue = an_array[index];
      var position = index;

      while ((position >= 1) && (an_array[position - 1] > currentvalue))

          an_array[position] = an_array[position - 1];
          position = position - 1;

      endwhile

      an_array[position] = currentvalue;

    endfor


endfunction

Merge sort

function main()

  // needs to be an even number length
    var a_list = Array<UInt32>(15);

    for (i in 0:a_list.count())
        a_list[i] = rand(0u32, 1000u32);
    endfor

    printLn(a_list);
    merge(a_list);
    printLn(a_list);

endfunction


function merge(a_list : Array<UInt32>)

    // print("Splitting "); printLn(a_list);

    if (a_list.count() > 1)

        var mid = a_list.count() / 2;

        var left_half = Array<UInt32>(mid);
        var right_half = Array<UInt32>(mid);

        if (a_list.count() % 2 != 0)
          right_half = Array<UInt32>(mid+1);
        endif

        for (x in 0:mid)
            left_half[x] = a_list[x];
        endfor

        var count = 0;
        for (y in mid:a_list.count())
            right_half[count] = a_list[y];
            count += 1;
        endfor

        // print("Left half "); printLn(left_half);
        // print("Right half "); printLn(right_half);

        merge(left_half);
        merge(right_half);


        var i = 0;
        var j = 0;
        var k = 0;


        while (i < left_half.count() && j < right_half.count())
            if (left_half[i] < right_half[j])
                a_list[k] = left_half[i];
                i += 1;
            else
                a_list[k] = right_half[j];
                j += 1;
            endif

            k=k+1;
        endwhile


        while (i < left_half.count())
            a_list[k] = left_half[i];
            i += 1;
            k += 1;
        endwhile


        while (j < right_half.count())
            a_list[k] = right_half[j];
            j += 1;
            k += 1;
        endwhile      

    endif 

    //print("Merging "); printLn(a_list);

endfunction 

Quick sort

function main()

    var a_list = Array<Int32>(15);

    for (i in 0:a_list.count())
      a_list[i] = rand(0, 1000);
    endfor

    var n = a_list.count(); 

    printLn(a_list); 
    quick_sort(a_list, 0, n-1);
    printLn(a_list);

endfunction


function quick_sort(a_list : Array<Int32>, low : Int32, high : Int32) 

    var pi = 0;

    if (low < high)

        // get the partition index
        pi = partition(a_list, low, high);

        quick_sort(a_list, low, pi-1);
        quick_sort(a_list, pi+1, high);

    endif

endfunction


function partition (a_list : Array<Int32>, low : Int32, high : Int32) : Int32

    var pivot = rand(low, high);

    // swap random pivot with high
    var temp = a_list[high];
    a_list[high] = a_list[pivot];
    a_list[pivot] = temp;

    // track next pivot index
    var new_pivot_index = low - 1;

    for (index in low:high)

        if (a_list[index] < a_list[high])

            new_pivot_index = new_pivot_index + 1;
            temp = a_list[new_pivot_index];
            a_list[new_pivot_index] = a_list[index];
            a_list[index] = temp;

        endif

    endfor

    // swap pivot to new spot
    temp = a_list[new_pivot_index + 1];
    a_list[new_pivot_index + 1] = a_list[high];
    a_list[high] = temp;

    return new_pivot_index + 1;


endfunction