In this task, you should define two sorting algorithms that you can use to sort your lexicon of words. In the next task you will write a short program to use one of the sorting algorithms to sort your lexicon. Following sorting, words in your lexicon should be sorted in alphabetical order.It is entirely up to you which two sorting algorithms you include, as long as they are in the subject and different regarding time complexity.You should write one function per-sorting algorithm. Each of these functions should take a single parameter, the lexicon to be sorted. They should sort the lexicon in-place, so they do not need to return anything.
Question
In this task, you should define two sorting algorithms that you can use to sort your lexicon of words. In the next task you will write a short program to use one of the sorting algorithms to sort your lexicon. Following sorting, words in your lexicon should be sorted in alphabetical order.It is entirely up to you which two sorting algorithms you include, as long as they are in the subject and different regarding time complexity.You should write one function per-sorting algorithm. Each of these functions should take a single parameter, the lexicon to be sorted. They should sort the lexicon in-place, so they do not need to return anything.
Solution 1
Sure, I can define two sorting algorithms: Bubble Sort and Quick Sort. Both of these algorithms can be used to sort a lexicon of words.
- Bubble Sort: This is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Here is a Python function for Bubble Sort:
def bubble_sort(lexicon):
n = len(lexicon)
for i in range(n):
for j in range(0, n-i-1):
if lexicon[j] > lexicon[j+1] :
lexicon[j], lexicon[j+1] = lexicon[j+1], lexicon[j]
- Quick Sort: This is a divide and conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.
Here is a Python function for Quick Sort:
def partition(lexicon, low, high):
i = (low-1)
pivot = lexicon[high]
for j in range(low, high):
if lexicon[j] <= pivot:
i = i+1
lexicon[i], lexicon[j] = lexicon[j], lexicon[i]
lexicon[i+1], lexicon[high] = lexicon[high], lexicon[i+1]
return (i+1)
def quick_sort(lexicon, low, high):
if len(lexicon) == 1:
return lexicon
if low < high:
pi = partition(lexicon, low, high)
quick_sort(lexicon, low, pi-1)
quick_sort(lexicon, pi+1, high)
In terms of time complexity, Bubble Sort has a worst-case and average time complexity of O(n^2), where n is the number of items being sorted. Quick Sort, on the other hand, has a worst-case time complexity of O(n^2), but an average time complexity of O(n log n). Therefore, Quick Sort is generally faster and more efficient than Bubble Sort, especially for larger lists.
Solution 2
Sure, here are two sorting algorithms that can be used to sort a lexicon of words: Bubble Sort and Quick Sort.
- Bubble Sort: This is a simple comparison-based algorithm. It works by repeatedly swapping the adjacent elements if they are in the wrong order. Here's a Python function for Bubble Sort:
def bubble_sort(lexicon):
n = len(lexicon)
for i in range(n):
for j in range(0, n-i-1):
if lexicon[j] > lexicon[j+1] :
lexicon[j], lexicon[j+1] = lexicon[j+1], lexicon[j]
Bubble Sort has a worst-case and average time complexity of O(n^2), where n is the number of items being sorted.
- Quick Sort: This is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's a Python function for Quick Sort:
def partition(lexicon, low, high):
i = (low-1)
pivot = lexicon[high]
for j in range(low, high):
if lexicon[j] <= pivot:
i = i+1
lexicon[i], lexicon[j] = lexicon[j], lexicon[i]
lexicon[i+1], lexicon[high] = lexicon[high], lexicon[i+1]
return (i+1)
def quick_sort(lexicon, low, high):
if len(lexicon) == 1:
return lexicon
if low < high:
pi = partition(lexicon, low, high)
quick_sort(lexicon, low, pi-1)
quick_sort(lexicon, pi+1, high)
Quick Sort has a worst-case time complexity of O(n^2), though this scenario is rare, and it has an average time complexity of O(n log n).
Both of these functions sort the lexicon in-place, as required.
Similar Questions
ow you have two sorting algorithms defined, in this task you should create a small program that asks the user which sorting algorithm they would like to use, then sort the lexicon with that sorting algorithm.You should ensure that you test both sorting algorithms to see they give you the same result. When you do this, ensure that you reinitialize your lexicon (Run Task 2 again) to ensure that your lexicon is not already sorted.Example RunsYou should replace the names of the sorting algorithms with the algorithms you have chosen.Note: You can assume the user input will always be either 1 or 2.Note: You can hardcode the names of the sorting algorithms you selected.Run 1:Select your sorting algorithm (1. Bubble Sort, 2. Selection Sort): 1Sorting with Bubble SortRun 2:Select your sorting algorithm (1. Bubble Sort, 2. Selection Sort): 2Sorting with Selection Sort
From the assignment brief, along with the spelling of the word, a word in your lexicon needs to store the following information:The frequency: How many times the word appears in the input files.The list of neighbours: A neighbour of a word w is a word that is of the same length and differs from w by only one letter.The best way this can be implemented is as a Word class, where you can populate your lexicon with Word objects.Your task in this section is to create a class Word that is used to represent a Word in your lexicon.When you do this, you will need to:Think about what instance variables should be defined (and how they should be initialized)Think about what methods you need to implement for this classIn a future task, you will need to sort your lexicon full of Word objects. In the labs you saw a similar example where you needed to sort a collection of Person objects. It may be useful to refer back to this to see what methods were required.You may find that once you attempt the following tasks, you need to come back to this class and add additional methods.
A dictionary contains words that are arranged in an … order.1 poinA. alphabetB. alphabetsC. alphabeticalD. alphabetically
Lexicographical order is often known as alphabetical order when dealing with strings. A string is greater than another string if it comes later in a lexicographically sorted list.Given a word, create a new word by swapping some or all of its characters. This new word must meet two criteria:It must be greater than the original wordIt must be the smallest word that meets the first conditionExampleThe next largest word is .Complete the function biggerIsGreater below to create and return the new string meeting the criteria. If it is not possible, return no answer.Function DescriptionComplete the biggerIsGreater function in the editor below.biggerIsGreater has the following parameter(s):string w: a wordReturns- string: the smallest lexicographically higher string possible or no answerInput FormatThe first line of input contains , the number of test cases.Each of the next lines contains .Constraints will contain only letters in the range ascii[a..z].Sample Input 05abbbhefgdhckdkhcSample Output 0bano answerhegfdhkchcdkExplanation 0Test case 1:ba is the only string which can be made by rearranging ab. It is greater.Test case 2:It is not possible to rearrange bb and get a greater string.Test case 3:hegf is the next string greater than hefg.Test case 4:dhkc is the next string greater than dhck.Test case 5:hcdk is the next string greater than dkhc.Sample Input 16lmnodcbadcbbabdcabcdfedcbabcdSample Output 1lmonno answerno answeracbdabdcfedcbabdc
Arrange the words given below as per order in the dictionary.A. Tout, B. Transfer, C. Torpor, D. Tenet, E. Toy
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.