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.
Bias Stability tutorial all along with the key concepts of Fixed Bias Circuit, Forward Bias Base Emitter, Collector-Emitter Loop, Emitter-Stabilized Bias Circuit, Voltage Divider Bias, Exact Analysis, Approximate Analysis
the power can be calculated basically with the help of just ammeter and voltmeter.
tutorsglobe.com point method assignment help-homework help by online measurement of price elasticity of demand tutors
tutorsglobe.com pulse rate assignment help-homework help by online circulation tutors
www.tutorsglobe.com offers Activity Diagrams homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
Free AP Physics Study Guide, AP Physics Test Papers, AP Physics Practice papers, AP Physics Test pattern and general information, Find AP Physics exam information and resource, material free at Tutorsglobe.com
Energy Band Theory tutorial all along with the key concepts of Energy band, Periodic Potential, Bloch's theorem, Number of states in a band, Metals and Insulators
let 24x7 available professional tutors of sorting assignment help service help you in securing a++ at pocket-friendly prices.
Derivatives of Monosaccharides tutorial all along with the key concepts of Types of Sugar derivatives, Sugar alcohols, Amino sugars, Uronic acids, N-acetylneuraminic acid, Reactions of Monosaccharides and Configuration of Glucose
tutorsglobe.com monera assignment help-homework help by online five kingdom system of classification tutors
Enzymes-Vitamins and Co-enzymes tutorial all along with the key concepts of Definition of Enzymes, Nomenclature of Enzymes, Categorization of Enzymes, General Properties of Enzymes, How Enzymes Work, Co-enzymes and Vitamins
tutorsglobe.com functions of avc assignment help-homework help by online automatic volume control tutors
tutorsglobe.com taxonomy and phylogeny assignment help-homework help by online systematics tutors
www.tutorsglobe.com offers complex metal hydrides homework help, complex metal hydrides assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.
Chemical Instrumentation in Environmental Sciences tutorial all along with the key concepts of Determination of Chloride, Determination of Sulphate, Determination of Fluoride, Determining Iron by Phenanthroline Method
1933182
Questions Asked
3689
Tutors
1460027
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!