The sorting problem
Given a list of n totally orderable items, rearrange the list in increasing (or decreasing) order.
Totally orderable means that any two items can be compared: numbers, characters, strings etc.
The items are usually called keys.
Example This is an instance of the sorting problem:
(12, 5, 8, 16, 9, 31) → (5, 8, 9, 12, 16, 31).
Often, the elements to be sorted contain keys and data:
((5, A),(2, C),(7, A),(2, B),(1, B)) → ((1, B),(2, C),(2, B),(5, A),(7, A)).
Properties of sorting algorithms
Time complexity: worst case and average case.
Space complexity: the amount of extra space needed by the algorithm.
Definition
An algorithm is said in-place if it does not require more than O(log n) space in addition to the input.
Stability: A sorting algorithm is stable if it does not change the order of equal elements
Example
Given the input array: {(5, A),(2, C),(7, A),(2, B),(1, B)}, where we want to sort according to the first element of the pairs (the integers), then:
{(1, B),(2, C),(2, B),(5, A),(7, A)} is a stable sorting.
{(1, B),(2, B),(2, C),(5, A),(7, A)} is not a stable sorting, since the order of (2, B) and (2, C) is reversed.
General purpose sorting algorithms
The first type of sorting algorithms we are going to see are sorting algorithms which can be used to sort any type of keys.
They are based on comparison only and do not assume any other property in the keys (for example, they do not require the keys to be integers or strings).
Insertion sort
Insertion sort gradually builds the sorted array by putting each new key in its correct position.
public static void insertionSort ( int [ ] A , int n ) {
for ( int i = 1; i < n ; i ++) {
int j = i ;
while ( j > 0 && A [ j - 1] > A [ j ]) {
int tmp = A [ j ];
A [ j ] = A [ j - 1];
A [ j - 1] = tmp ;
j - -;
}
}
}Worst case time complexity: O(n 2 ) (quadratic).
Average case time complexity: O(n 2 ).
Space complexity: O(1).
Selection sort
Selection sort gradually builds the sorted array by finding the correct key for each new position
public static void selectionSort ( int [ ] A , int n ) {
for ( int i = 0; i < n - 1; i ++) {
int min = i ;
for ( i n t j = i + 1; j < n ; j ++) {
// Search for the minimum
if ( A [ j ] < A [ min ])
min = j ;
}
// Swap A[i] with A [ min]
int tmp = A [ i ];
A [ i ] = A [ min ];
A [ min ] = tmp ;
}
}
Worst case time complexity: O(n 2 ) (quadratic).
Average case time complexity: O(n 2 ).
Space complexity: O(1).
Example: The array {(2, A),(2, B),(1, C)} will be sorted as {(1, C),(2, B),(2, A)}.
Bubble sort
Bubble sort sorts the array by repeatedly swapping non-ordered adjacent keys. After each for loop iteration, the maximum is moved (or bubbled) towards the end.
public static void bubbleSort ( int A [ ] , int n ) {
for ( int i = 0; i < n - 1; i ++) {
for ( int j = 0; j < n - 1 - i ; j ++) {
if ( A [ j ] > A [ j + 1]) {
// Swap A[j] with A[j + 1]
int tmp = A [ j ];
A [ j ] = A [ j + 1];
A [ j + 1] = tmp ;
}
}
}
}Worst case time complexity: O(n 2 ) (quadratic).
Average case time complexity: O(n 2 ).
Space complexity: O(1).
Merge sort
Merge sort is a divide-and-conquer algorithms to sort an array of n elements:
Divide the array into two equal parts.
Sort each part apart (recursively).
Merge the two sorted parts.
The key step in merge sort is merging two sorted arrays, which can be done in O(n).
Example
Given two arrays B = {1, 4, 6} and C = {2, 3, 7, 8}, the result of merging B and C is {1, 2, 3, 4, 6, 7, 8}.
public static void mergeSort ( int [] A , int l , int r ) {
if ( l >= r )
return ;
int m = ( l + r ) / 2;
mergeSort (A , l , m ) ; // Sort first half
mergeSort (A , m + 1 , r ) ; // Sort second half
merge (A , l , m , r ) ; // Merge
}private static void merge ( int [ ] A , int l , int m , int r ) {
int [ ] B = new i n t [ r - l + 1];
int i = l , j = m + 1 , k = 0;
while ( i <= m && j <= r )
if ( A [ i ] <= A [ j ])
B [ k ++] = A [ i ++];
else
B [ k ++] = A [ j ++];
i f ( i > m )
while ( j <= r )
B [ k ++] = A [ j ++];
else
while ( i <= m )
B [ k ++] = A [ i ++];
for ( k = 0; k < B . length ; k ++)
A [ k + l ] = B [ k ];
}Example:
Example Sort the array: 8, 3, 2, 9, 7, 1, 5, 4.
Worst case time complexity: O(n log n) (sub-quadratic).
Average case time complexity: O(n log n).
Space complexity: O(n) (requires auxiliary memory).
Quick sort
Quick sort is another divide-and-conquer algorithms to sort an array of n elements:
Pick any element of the array and call it the pivot (the first element, or a randomly chosen element for example) .
Rearrange the array so that all elements before the pivot are less or equal the pivot, and all those after the pivot are greater or equal to the pivot (partitioning).
Recursively sort the part of the array before the pivot and the one after the pivot.
public static void quickSort ( int [] A , int l , int r ) {
if ( l < r ) {
int s = partition (A , l , r ) ;
quickSort (A , l , s - 1) ;
quickSort (A , s + 1 , r ) ;
}
}private static int partition ( int [] A , int l , int r ) {
int p = A [ l ] , i = l + 1 , j = r ;
while ( i < j ) {
while ( A [ i ] <= p && i < j )
i ++;
while ( A [ j ] > p && i < j )
j - -;
int tmp = A [ i ];
A [ i ] = A [ j ];
A [ j ] = tmp ;
}
int s ;
if ( A [ i ] <= p ) s = i ; else s = i - 1;
int tmp = A [ l ];
A [ l ] = A [ s ];
A [ s ] = tmp ;
return s ;
}Example
Sort the array:
5, 3, 1, 9, 8, 2, 4, 7.
Worst case time complexity: O(n 2 ) (quadratic). The worst case happens when the array is already sorted for example.
Average case time complexity: O(n log n) (sub-quadratic).
Space complexity: O(1).
Example
The array {(2, A),(2, B),(1, C)} will be sorted as {(1, C),(2, B),(2, A)}.
Specialized sorting algorithms
We have seen that the best comparison-base algorithms are O(n log n) worst case. Can we do better?
The answer is no. It can be proved that: no comparison-based algorithm can sort an array in less than O(n log n) in the worst case.
This result is for general data, but when the keys are of special type (like small positive integers or strings), we can find faster sorting algorithms.
Specialized sorting algorithms do not use comparison in general and can only be used with specific types of keys.
If you need any programming assignment help in data structure programming, data structure project or data structure homework then we are ready to help you.
Send your request at realcode4you@gmail.com and get instant help with an affordable price.
We are always focus to delivered unique or without plagiarism code which is written by our highly educated professional which provide well structured code within your given time frame.
If you are looking other programming language help like C, C++, Java, Python, PHP, Asp.Net, NodeJs, ReactJs, etc. with the different types of databases like MySQL, MongoDB, SQL Server, Oracle, etc. then also contact us.
Comments