<< PrevNext >>
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.
Don't forget to
login or
register an account to submit your answer!
Good luck, and as always, happy algorithming!