Explore BrainMass

Explore BrainMass

    Sorting

    University of Chicago students lined up in height order

     

    As it's name suggesting, sorting algorithms rearrange the items in a collection in a given order. Often this order is numerical, either ascending or descending, or lexicographical, but there are many options beyond that, depending on the use the sorted collection will be put to. Items to be sorted can be any kind of object with at least one rankable attribute - database records, people, colors, house numbers, etc. The item being sorted may have more than one value in it, e.g. it could be a tuple, but the value that is used to sort in these cases is known as the key. Some tasks may even require more than one sort, such as ordering a deck of cards first by number and then by suit. In this case, those two attributes are the primary and secondary keys, depending on which is tended to first.

    The same values may be ranked differently by different sorting algorithms, e.g. colors could be ranked alphabetically, or by preference, but the order of the separate values should not change if the same sorting algorithm is applied multiple times. Otherwise it would be a shuffle rather than a sort. However, values with equal rank may or may not remain in the same order upon consecutive sorts. This is knows as the stability of the algorithm. An stable sort will preserve the original order of equal-rank items each time it is run so their order will not change, while they are considered interchangeable in a non-stable sort.

    Due to the prevalence of sorting in programs everywhere, much research has gone into finding the most efficient sorting algorithms for different cases. Many consider the sorting problem solved by mergesort, quicksort and heapsort which run on average in O(n log n) time, but in reality these are often slower than they need to be for partially-sorted data and so many hybrids have risen to plug these gaps, such as Timsort (the standard sort routine for Python and Java) and introsort. Some of these hybrids can sort partially-sorted data in as little as O(n) time, and new shades of sorting algorithms are being developed all the time.
     

    Many basic sorting algorithms, such as the first 3 mentioned above and bubblesort, see widespread use as introductory material in classes teaching computer programming due to their universality and easily demonstrable nature. Sorting in general is of huge use to programmers as it allows not only a more efficient traversal of data for applications, but is much easier for humans to understand should they need to examine or analyse the data by hand as well.

    © BrainMass Inc. brainmass.com March 19, 2024, 4:09 am ad1c9bdddf

    BrainMass Categories within Sorting

    Quicksort

    Solutions: 1

    A divide and conquer algorithm that sorts subsections as it partitions them off of the original list based on a pivot value.

    Mergesort

    Solutions: 0

    A divide and conquer algorithm that breaks the original list down into subsections and sorts them as it rejoins the parts in order.

    Bubblesort

    Solutions: 0

    An algorithm that sorts the list in place by comparing each element with its next neighbor.

    BrainMass Solutions Available for Instant Download

    Simulating Neurons

    1. Kozma et al. present a contemporary mathematical model of human behavior under some environmental constraints. How well does their model fit the human performance data? Is their solution algorithm blind overall to error reduction between input and associated output states or is it based on propagation or another Hebbian learn

    Irish Football League: Working with Excel

    CGS1030 Practice 1 Insert the following table into Sheet1 of an Excel spreadsheet, keeping the cell references consistent. ( The Sheet is already created in the second file) A B C D E F G H I J 1 2 Irish Football League Round 3 (Soccer) 3 4 Home Team Goals P

    MySQL SELECT Statements

    Write SELECT statements for the following questions. Make sure to include the statement execution, including the resulting data. Display all columns and all rows from the Employees table. 9 rows returned Display the regionid, regiondescription for all rows in the Regions table. 4 rows returned Modify query 2 so that the

    A concise summary of different types of physical tamper-resistant devices.

    Write a concise summary (ideally one to two pages) of what you have learned about physical tamper-resistant devices. a. First, make a list of all of the different types of physical tamper-resistant devices and their characteristics. b. Second, consider their differences and similarities. Start formulating your opinions

    MATLAB Code Debugging

    Without changing the codes, the errors boxed is what I am getting when I run these codes. I am not sure if I am supposed to create files first. I would like codes that are basic and running. function out=bisect_1(fname, a, b, eps) % bisection algorithm % fname must be a function handle (if you want to use a string in

    Algorithms binary sequential search

    Consider searching algorithms on the following array of data: [22 21 9 4 16 2 10 14 20 31 26 19 17 28 8 13] Suppose you want to implement a searching algorithm to see if the data set contains the number 19. Demonstrate how the search would go if you used: A sequential search A binary search State the runtime for each o

    Analyze Cost and Role in Decision Making

    Analyzing Cost and Its Role in Decision Making The concept of opportunity cost and examination of how to calculate the cost of alternatives over single and multiple time periods. Analyze cost and its role in the decision-making process by answering the following questions: ? Citing examples, differentiate between opportuni

    Design and Analysis of Algorithms..

    Consider a set G consisting of m integers. a) Design an algorithm that finds and gives as output the k smallest numbers of the whole G sorted in ascending order and has time complexity O(m*lg(m)) and spatial complexity O(m). Note: lg denote the logarithm base 2. b) Design an algorithm that solves the above problem using

    C/C++ Console Program that Uses Arrays

    Create a program in which a user is asked for how many values (s)he wants to enter (maximum 50), then: Asks for the values and stores them into an array of double. Sorts the values in ascending order according to the following algorithm, where size is the number of doubles to be sorted: for i=0..size-2 check all the values b

    Knowledge Management Projects

    What are the potential benefits of knowledge management projects? What strategies should companies follow to achieve positive results in knowledge management projects?

    Bubble Sort Algorithm in C++ That Generates Random Integers

    Implement a Bubble Sort algorithm in C++ that generates a list of 10 random integers and sorts them in ascending order. Each time the program is run, it should use as its input the randomly generated list, sort it using bubble sort and output a sorted list. The program should: 1. Display the randomly generated list. 2. Di

    Write a JAVA program that implements the bubble-sort algorithm.

    Write a sort method in Java that uses the bubble-sort algorithm. The bubble-sort algorithm makes several passes through the array. On each pass, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped; otherwise, the values remain unchanged. The technique is called a bubble sort or sin

    Decision tree for the insertion sort algorithm

    1. Draw the decision tree for the insertion sort algorithm for the following array of names: [Mickey, Minnie, Donald, Goofy]. 2. Create a program to implement the selection sort algorithm, which will sort a list of strings. Selection sort function should sort the list of strings in alphabetical order. You only need to provide

    Seating arrangement to increase social contact

    College Students go out for a party. To increase social contact, they would love to sit at tables so that no two students from the same programme are at the same table. Show how to find such a seating arrangement or prove that no such seating plan is possible. The input is the p programmes, for each i the number ai indicates

    Understanding Excel: Identifying Variables

    Details: Your Aunt Sally has entered all of her stuffed animal data into an Excel workbook. She took your advice and used headings to organize the information. She now wants to have the information sorted in the fields Name, Date Purchased, Purchase Price, Color, Size, and Location for each of her stuffed animals. In addition, h

    A basic overview of algorithm analysis

    An Algorithm is a set of steps that defines how a task must perform to produce expected results. An algorithm can be represented in many ways. A computer program is a formal representation of an algorithm. There are many ways of programming a single problem. Thus, many different algorithms can be developed to solve the same

    Sorting Algorithms for data

    A sorting algorithm is stable if two data items having the same value are not rearranged with respect to each other at any stage of the algorithm. For instance, in the five-element vector 55 12 33 a stable sorting algorithm guarantees that the final ordering is 12 33 55 classify each of the algorithms a

    The high school reunion data has been entered into your Excel workbook and the event is only a few weeks away. Your next step is to create a label for each classmate's family so that you can attach it to the bag that will contain their sweatshirts. You must first obtain the sizes for each attendee and place the order for the sweatshirts with the vendor. The vendor must have at least a week and a half to guarantee delivery.

    The high school reunion data has been entered into your Excel workbook and the event is only a few weeks away. Your next step is to create a label for each classmate's family so that you can attach it to the bag that will contain their sweatshirts. You must first obtain the sizes for each attendee and place the order for the swe

    SubSet Sum using Greedy & Dynamic Algorithms

    1. SubsetSum (greedy algorithms) A SubsetSum is defined as follows: given positive integers a1 . . . an (not necessarily distinct), and a positive integer t, find a subset S of (1 . . . n) such that ∑iε s ai = t, if it exists. a) Suppose each ai is at least twice as large as the sum of all smaller numbers aj . Give a gree

    C++ template class

    Write a class template SortableVector. The class should have a member function that sorts the vector elements in ascending order (your choice of the sorting method). Test the template in a driver program. Do NOT use the STL.

    Querying a Database - Access 2007

    Complete and submit Cases and Places 2, p. AC 135. You will use the BeachCondo Rentals database created in the case study for Unit 2. You will query this database for several types of information and sort the results. You will create and save six queries, and will submit the database containing the queries. Hello class, I

    Algorithm for insertion and merge sort

    Suppose that we compare the insertion sort method with the merge sort method in the same computer. For entries of size n, the classification with insertion requires 8n^2 steps, while classification with merge requires 64n*lg(n) steps. For which values of n, does insertion sort method outclass the merge sort method? Please expl

    Implements a method that receives an array parameter

    Write a program that implements a method that receives an array parameter and sorts that array using the bubble-sort algorithm. The bubble-sort algorithm makes several passes through the array. On each pass, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped: otherwise, the values

    EXCEL Sorting Question

    Please see the attachment. Employee Number Employee Name Order Number Order Type Job Type Total Hours 7926 Chris Jones A50000 BASIC Training 2.000 H 7926 Chris Jones A50000 BASIC Training 3.000 H 7925 Mary Brand A50002 BASIC Training 4.000 H 7925 Mary Brand A50002 BASIC Training 5.000 H 7925 Mary Brand A50002 BASIC Tr

    Students' score computing --JAVA

    Write a program that allows the user to enter students' names followed by their test scores and output the following information(assume that the maximum number of students in the class is 50): a. Class average b. Names of all the students whose test scores are below the class average, with an appropriate message c. High