Sorting:Definition of a sorting problem:
Input: A series of N numbers (a1, a2,..., aN) Output: A permutation (a1', a2',..., aN') of the input series such that a1' <= a2' <=... <= aN' Things to be considered in the Sorting:
These are some of the difficulties in sorting which can as well occur in real life:
A) The size of list to be ordered is the major concern. At times, the computer memory is not enough to store all data. You might only be capable to hold part of the data within the computer at any time; the rest will perhaps have to stay on disc or tape. This is termed as the problem of external sorting. Though, rest assured that nearly all programming problem size will never be really big such that you require to access disc or tape to execute external sorting... (This hardware access is generally forbidden throughout contests).
B) The other problem is the stability of sorting technique. Illustration: Assume that you are an airline. You have a list of passengers for day's flights. Related to each passenger is the number of his or her flight. You will perhaps want to sort the list into an alphabetical order. No problem... Then, you wish for to re-sort the list by flight number therefore as to get lists of passengers for each flight. Again, "no problem"... - apart from that it would be much nice if, for each flight list, the names were still in alphabetical order. This is the difficulty of stable sorting.
C) To be a bit more mathematical regarding it, assume that we have a list of items {xi} with xa equivalent to xb as far as the sorting comparison is concerned with xa before xb in the list. The sorting technique is stable when xa is sure to come prior to xb in the sorted list.
Lastly, we have the problem of key sorting. The individual items to be sorted may be very big objects (example: complex record cards). All sorting techniques naturally include a lot of moving things being sorted. When the things are much large this might take up a lot of computing time -- much more than that taken just to switch the two integers in an array. Comparison-based sorting algorithms:
Comparison-based sorting algorithms include comparison between two objects a and b to find out one of the three possible relationships among them: less than, equal, or greater than. Such sorting algorithms are dealing with how to utilize this comparison efficiently, and hence we minimize the quantity of such comparison. Let us begin from the most naive version to the most sophisticated comparison based sorting algorithms.
Bubble Sort:
Speed: O(n^2), very slow Space: The size of initial array Coding Complexity: Simple
This is the simplest and unluckily the worst sorting algorithm. This sort will do the double pass on an array and swap 2 values whenever essential. BubbleSort(A) for i <- length[A]-1 down to 1 for j <- 0 to i-1 if (A[j] > A[j+1]) // change ">" to "<" to do a descending sort temp <- A[j] A[j] <- A[j+1] A[j+1] <- temp Slow motion run of Bubble Sort (Bold == sorted area):
5 2 3 1 4 2 3 1 4 5 2 1 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 >> doneQuick Sort:
Speed: O(n log n), is one of the most excellent sorting algorithm. Space: The size of initial array Coding Complexity: Complex, utilizing Divide & Conquer approach
It is one of the most excellent sorting algorithms known. Quick sort employ Divide & Conquer approach and partition each sub-set. Partitioning a set is to divide set into a collection of mutually disjoint sets. This sort is much quicker as compared to "stupid however simple" bubble sorting. Quick sort was introduced by C.A.R Hoare.
Quick Sort - basic idea:
a) Partition the array in O(n) b) Recursively sort left array in O(log2 n) best or average case c) Recursively sort right array in O(log2 n) best or average case Quick sort pseudo code:
QuickSort(A,p,r) if p < r q <- Partition(A,p,r) QuickSort(A,p,q) QuickSort(A,q+1,r)Quick Sort for C/C++ User:
C/C++ standard library <stdlib.h> includes qsort function.
This is not the most excellent quick sort implementation in the world however it is fast enough and very easy to be employed... thus if you are employing C/C++ and require to sort something, you can simply call this built in function:
qsort(<arrayname>,<size>,sizeof(<elementsize>),compare_function);
The only thing that you require to implement is the compare_function that takes in the two arguments of type "const void", that can be cast to suitable data structure, and then return one of such three values:
• negative, if a should be before b • 0, if a equal to b • positive, if a should be after bA) Comparing a list of integers:
Simply cast a and b to the integers
When x < y, x-y is negative, x == y, x-y = 0, x > y, x-y is positive
x-y is a shortcut manner to do it :)
Reverse *x - *y to *y - *x for sorting in decreasing or reducing order
int compare_function(const void *a,const void *b) { int *x = (int *) a; int *y = (int *) b; return *x - *y; }
B) Comparing a list of strings:
For comparing the string, you require strcmp function within string.h lib. strcmp will be by default return -ve,0,ve suitably... to sort in the reverse order, just reverse the sign returned by strcmp
#include <string.h> int compare_function(const void *a,const void *b) { return (strcmp((char *)a,(char *)b)); }
C) Comparing floating point numbers:
int compare_function(const void *a,const void *b) { double *x = (double *) a; double *y = (double *) b; // return *x - *y; // this is WRONG... if (*x < *y) return -1; else if (*x > *y) return 1; return 0; }
D) Comparing records based on the key:
In several times you require sorting more complex stuffs, like record. Here is the simplest manner to do it by using qsort library
typedef struct { int key; double value; } the_record;int compare_function(const void *a,const void *b) { the_record *x = (the_record *) a; the_record *y = (the_record *) b; return x->key - y->key; }Multi field sorting and advanced sorting technique:
Sometimes sorting is not based on one key merely.
For illustration sorting the birthday list. At first, you sort by month, then if the month ties, then sort by date (apparently), and then finally by year.
For illustration, I have an unsorted birthday list such as:
24 - 05 - 1982 - Sunny 24 - 05 - 1980 - Cecilia 31 - 12 - 1999 - End of 20th century 01 - 01 - 0001 - Start of modern calendar
=> I will have a sorted list as:
01 - 01 - 0001 - Start of modern calendar 24 - 05 - 1980 - Cecilia 24 - 05 - 1982 - Sunny 31 - 12 - 1999 - End of 20th century
To do the multi field sorting like this, customarily one will select multiple sort employing sorting algorithm that has "stable-sort" property.
The better way is to do multi field sorting and is to alter the compare_function in such a manner that you break ties accordingly... I will give you an illustration employing birthday list again.
typedef struct { int day,month,year; char *name; } birthday; int compare_function(const void *a,const void *b) { birthday *x = (birthday *) a; birthday *y = (birthday *) b; if (x->month != y->month) // months different return x->month - y->month; // sort by monthelse { // months equal..., try second field... day if (x->day != y->day) // days different return x->day - y->day; // sort by day else // days equal, try third field... year return x->year - y->year; // sort by the year } }Linear-time Sorting:
A) Lower bound of comparison-based sort is O(n log n):
The sorting algorithms are comparison-based sort, they employ comparison function such as <, <=, =, >, >= and so on to compare two elements. We can model this comparison sort by using decision tree model, and we can proof that the minimum height of this tree is O(n log n).
B) Counting Sort:
For Counting Sort, we suppose that the numbers are in the range of [0..k], here k is at most O(n). We set up a counter array which counts how many duplicates within the input, and reorder the output accordingly, devoid of any comparison at all. The Complexity is O(n+k).
C) Radix Sort:
For Radix Sort, we suppose that the input is n d-digits number, here d is reasonably limited.
The Radix Sort will then sorts these numbers digit by digit, beginning with the least significant digit to the most important digit. It generally uses a stable sort algorithm to sort the digits, like Counting Sort above.
Latest technology based Programming Languages Online Tutoring Assistance
Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Programming Languages help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Programming Languages, project ideas and tutorials. We provide email based Programming Languages help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Programming Languages. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Programming Languages Homework help and assignment help services. They use their experience, as they have solved thousands of the Programming Languages assignments, which may help you to solve your complex issues of Programming Languages. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.
tutorsglobe.com nitrogen fixation assignment help-homework help by online nitrogen cycle tutors
tutorsglobe.com rickets and osteomalacia assignment help-homework help by online bones and joints tutors
Theory and lecture notes of Aggregate Supply all along with the key concepts of aggregate supply, Output Relative to Potential and the Inflation Rate, Aggregate Supply and Aggregate Demand. Tutorsglobe offers homework help, assignment help and tutor’s assistance on aggregate supply.
Financial accountancy or financial accounting is the branch of accountancy that for decision makers concerned with the preparation of financial statements, like suppliers, stockholders, banks, government agencies, employees, owners, and other stakeholders.
Laboratory Regulations tutorial all along with the key concepts of Safety Regulations, Format of the Lab Report, Laboratory Care and Waste Disposal
with integrated library systems assignment help service, you can simply get rid of your problems and gain top grades easily!
anatomical differences between dicot stem and monocot stem - dicot stem hypodermis is built up of collenchymatous cells. monocot stem hypodermis is built up of sclerenchymatous cells.
tutorsglobe.com hemophilia assignment help-homework help by online inborn errors of metabolism tutors
Theory and lecture notes of Concept of Construction with ruler and compass all along with the key concepts of construction with ruler and compass, Models of Computation, Theorem of ruler and compass. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Construction with ruler and compass.
tutorsglobe.com sewage treatment and disposal assignment help-homework help by online air pollution tutors
tutorsglobe.com public expenditure assignment help-homework help by online subject matter of public finance tutors
Chemical Kinetics tutorial all along with the key concepts of Factors that affect Reaction rates, Reaction Rates, Rate Laws, Units of rate constant and rate law from experimental data
dish antenna is a receiver antenna that receives the signals propagated by the satellite and provide to the t.v. receiver.
Modern Examples of Evolution tutorial all along with the key concepts of Sickle-cell Anaemia, Industrial Melanism, Chloroquine - Resistance Malaria Parasite, Pesticide-Resistance Insects, HIV, Phylogenetic categorization of Organisms
atomic radii tutorial all along with the key concepts of measurement of atomic radii, covalent radius, van der waal's radius, metallic or crystal radius, ionic radius, factors affecting the atomic radii, periodicity in atomic radii
1960451
Questions Asked
3689
Tutors
1468981
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!