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 >> done

Quick 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 b

A) 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 month
else { // 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.