August 04, 2020, 06:13:15 pm

### AuthorTopic: SDD Algorithm Contest (ALCON) | Problem 6: Let's Sort It Out!!!  (Read 1027 times) Tweet Share

0 Members and 1 Guest are viewing this topic.

#### Opengangs

• New South Welsh
• Posts: 696
• $\mathbb{O}_\mathbb{G}$
• Respect: +450
##### SDD Algorithm Contest (ALCON) | Problem 6: Let's Sort It Out!!!
« on: June 25, 2018, 01:27:19 am »
+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.

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

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

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

[2018 $-$ 2022: UNSW]
Degree: Bachelor of Science (Computer Science) / Bachelor of Science (Mathematics)
Specialisation: Artificial Intelligence

#### JTrudeau

• Trendsetter
• Posts: 109
• Master of the Meeses
• Respect: +90
##### 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: 413
• Respect: +448
##### 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

#### 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.

#### 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

• 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