Welcome, Guest. Please login or register.

November 18, 2019, 05:13:59 pm

Author Topic: SDD Algorithm Contest (ALCON) | Problem 6: Let's Sort It Out!!!  (Read 781 times)  Share 

0 Members and 1 Guest are viewing this topic.

Opengangs

  • MOTM: AUG 17
  • New South Welsh
  • Forum Leader
  • ****
  • Posts: 683
  • Respect: +436
+6
<< Prev
Next >>

ALCON PROBLEM 6:
LET'S SORT IT OUT!!!

Week 5 asked you to write a program that allows deals with string manipulation. If you missed this problem, you can always do them in your spare time and get feedback in your code.

You can find the sample answer to Week 5's problem, as well as everything Week 5 related here.

Please make sure you've read the rules here.

Week 6 question:

Part of the HSC syllabus tasks you with your fluency in the different sorting methods, including bubble, insertion and selection sort. Unlike the previous problems, this fortnight will consist of writing three different programs.

Your first program is a simple ascending bubble sort. Worth 2 marks, write a program that takes in an unsorted array and sorts them using bubble sort. This sorting method takes two adjacent elements in an array and compares them to each other. If the second element is smaller than the first, then moves onto the next two. This process repeats until no more elements can be found. An animated diagram illustrates this process.

Courtesy of: Wikimedia

Your second program is a simple ascending insertion sort. Worth 2 marks, write a program that takes in an unsorted array and sorts them using insertion sort. This sorting method takes two adjacent elements in an array and compares them to each other. The only difference between insertion and bubble is that insertion finds the location of each respective element, while bubble iterates over time. An animated diagram illustrates this process.

Courtesy of: Wikimedia

Finally, write an ascending selection sort method. Selection sort takes the first unsorted element in the array and finds the minimum element in the unsorted array, and swaps the two elements so that the minimum element is placed in its correct location. This continues until no more swaps can be made, in which case, we can assume that the entire array is finally sorted. An animated diagram illustrates this process.

Courtesy of: Wikimedia

Optional challenge add-on (+2 marks)
There is another sorting method; this sorting method is highly inefficient, but we tend to use it for educational purposes. This is called the bogosort. Bogosort takes an unsorted array and attempts to sort the array by arranging the elements in random order. If itís unsorted, then the program will start again, randomly arranging the elements with no predetermined pattern. This process continues until it finds a sorted array, in which case, the process terminates. Your goal here is to write a bogosort.

You may assume that a random function has been created. This function returns a random number from 0 to the (length of the array - 1). This may return the same number multiple times, so you may have to take this into account.

Youíll be marked on correctness, efficiency, and defensive programming.

Learning objectives for the week:

-> Introduction to sorting methods.
-> Writing the logic behind sorting methods.
-> Fluency in bubble sort, insertion sort, and selection sort.

-> Debugging and logic writing: if youíre unsure whether or not your logic is accurate, itís recommended that you use a small number of elements and test them out with the logic of your program.

Marking guidelines

Don't forget to login or register an account to submit your answer!

Good luck, and as always, happy algorithming!
« Last Edit: July 08, 2018, 08:40:50 pm by Opengangs »
2017: English (Advanced): 86 | Mathematics: 94 | Mathematics (Extension 1): 45 | Biology: 84 | Business Studies: 87 | Software Design and Development: 88

2018: Computer Science @ UNSW

JTrudeau

  • MOTM: APR 18
  • Trendsetter
  • **
  • Posts: 109
  • Master of the Meeses
  • Respect: +89
Re: SDD Algorithm Contest (ALCON) | Problem 6: Let's Sort It Out!!!
« Reply #1 on: July 08, 2018, 09:27:29 am »
+5
Hey y'all! With less than 24 hours and no entries so far, OG and I have decided to extend the deadline by another week. . This week's question is a great revision on sorting methods (which you'll find a lot of algorithms use!), so give it a spin :) Hope to see a couple entries more pop up!
Data Science, Finance || University of Sydney
== First in State for Software Design and Development 2017 ==
Advanced English | Maths Extension 1 | Maths Extension 2 | Economics | Software Design & Development | Chemistry

cthulu

  • Trailblazer
  • *
  • Posts: 35
  • Respect: +1
Re: SDD Algorithm Contest (ALCON) | Problem 6: Let's Sort It Out!!!
« Reply #2 on: July 08, 2018, 03:49:53 pm »
+1
Hi,

I was going to do this question but I thought there was no point because I would be just sending the algorithms I had pre-written. I just want to thank you guys for these questions, it has really helped me improve my pseudocode.

Thanks!

MisterNeo

  • MOTM: MAY 2017
  • Forum Obsessive
  • ***
  • Posts: 479
  • Hello, it is iÖ√-1
  • Respect: +447
Re: SDD Algorithm Contest (ALCON) | Problem 6: Let's Sort It Out!!!
« Reply #3 on: July 08, 2018, 05:38:48 pm »
+4
Hey guys, another sorting algorithm I found very interesting and worth checking out is gravity/bead sort.
(pic from Wikipedia)
It works by having beads suspended over each other and letting them drop, and it naturally sorts itself into increasing order. One of the disadvantages is that it only works for positive numbers.
If you're looking for a project to do over the holidays, definitely try creating your own :)
HSC 2017 | ATAR: 95.60
______________
Bachelor of Commerce with Bachelor of Science (Computer Science) at UNSW

cthulu

  • Trailblazer
  • *
  • Posts: 35
  • Respect: +1
Re: SDD Algorithm Contest (ALCON) | Problem 6: Let's Sort It Out!!!
« Reply #4 on: July 11, 2018, 04:23:43 pm »
0
Was bored so I decided to try this. Wasn't really sure about the BogoSort thing so I came up with an algorithm that would first check if the array is sorted, then randomise the array and then recursively call the function again to check if its sorted and if not then randomise the array again.

https://docs.google.com/document/d/11gQbzxEKEjjURYtcM98WV0BagD6zqnExld6o7spMCCA/edit?usp=sharing

jasn9776

  • Forum Regular
  • **
  • Posts: 57
  • Respect: +4
Re: SDD Algorithm Contest (ALCON) | Problem 6: Let's Sort It Out!!!
« Reply #5 on: July 15, 2018, 10:28:53 pm »
0
Bubble Sort
Assume Array is a zero-indexed array of length i+1
While j <=last  and SWAPPED=TRUE
   SWAPPED=FALSE
   Last=lastIndex -1 'because we +1 in code
   J = 0
   FOR i =0 to last-J
      IF Array>Array[i+1]
         SWAP(Animals,Animals[i+1])
         SWAPPED=TRUE
      ENDIF
   Next I
j=j+1
EndWhile

Selection Sort
Assume 1 indexed array
Pass = 0
WHILE Pass < LengthofArray.Numbers
   FOR i=1 + Pass to LengthofArray.Numbers
      Marked cell=Numbers
      Max = Marked cell
      IF Numbers > Max THEN
         MaxPos = I
         Max = Numbers
      ENDIF
   NEXT
   IF max>Numbers
      SWAP(Numbers[1+Pass], Numbers[MaxPos])
   ENDIF
Pass = Pass + 1
ENDWHILE

Insertion Sort (NA-I still don't get it after watching a few videos of it. The code is just really confusing.)

BogoSort
BogoSort
Assume all arrays are 1-indexed
Array-Check is an Boolean array of length L(default = F)
Array-Numbers is a Integer array of length L
Array-Potentially sorted is of length L
WHILE ORDERED = FALSE
 i =1
WHILE i <= max index of Array-Numbers i.e. L
    Random Number=Rndfunction(number from 0 to L)
    IF Array-Check(Random Number) = FALSE THEN
        Array-Numbers(i)=Array-PotentiallySorted(random no.)
        Array-Check(Random Number) = TRUE
        i = i + 1
    ELSE 'Do nothing'
    ENDIF
ENDWHILE

  ORDERED = TRUE
   i = 1
  WHILE i < L - 1 and ORDERED = true 'L -1 since we are comparing to i+1'
      IF Array-Potentially sorted(i)>Array-potentially sorted(i+1) THEN
           ORDERED =FALSE
     ENDIF
     i = i + 1
ENDWHILE
IF ORDERED = TRUE THEN
   DISPLAY ARRAY-Potentially sorted
ELSE
   Reset Array-Numbers
   Reset Array-Check
ENDWHILE
   
     
« Last Edit: July 22, 2018, 10:04:32 pm by jasn9776 »
HSC 2018: English Adv(88) | Bio (90) | Phys(85) | Software Design (87) | 3U Math (41)

wewanttacos

  • Adventurer
  • *
  • Posts: 5
  • Respect: 0
Re: SDD Algorithm Contest (ALCON) | Problem 6: Let's Sort It Out!!!
« Reply #6 on: July 17, 2018, 06:11:58 pm »
0
BEGIN BubbleSort
    swap = True
    WHILE swap = True
        swap = False
        index = 1
        WHILE index < length of array
            IF array[index] < array[index+1] THEN
                temp = array[index]
                array[index] = array[index+1]
                array[index+1] = temp
                swap = True
            ENDIF
            index = index + 1
        ENDWHILE
    ENDWHILE
END BubbleSort