MODULE 4:
S O RT I N G T E C H N I Q U E S
Sanal Kumar T S.
SCOPE , VIT AP University
SORTIN
G
Sorting is a process that organizes a collection of data into either ascending or descending order.
Types
Internal sort requires that the collection of data fit entirely in the computer’s main memory.
E.g., Bubble Sort, Insertion Sort, Selection sort, Quick sort
External sort when the collection of data cannot fit in the computer’s main memory all at once but
must
reside in secondary storage such as a hard disk.
E.g., Merge sort
Advantages:
Initial sort of the data enhance the performance of an algorithm.
Sorting cost determines the running time.
Comparison-based sorting algorithm makes ordering decisions only on the basis of comparisons.
Sorting algorithms:
Bubble Sort
Insertion Sort
Merge Sort
Quick Sort
Heap Sort
BUBBLE
SORT
Simplest sorting algorithm.
Traversal starts from first element to last element of an array.
In each iteration, the current element is compared with the next element.
If current element is greater than the next element, it is swapped.
Likewise, Compares the current element to adjacent elements repeatedly.
At the end of each iteration, the largest element gets bubbled up at its proper
place.
It is not suitable for large data sets
0 1 2 3 4 BUBBLE
Array
11 3 6 15 4 SORT
Iteration=1 Iteration=2 Iteration=3
First Largest is bubbled up Second Largest is bubbled up Third Largest is bubbled up
BUBBLE
0 1 2 3 4
SORT Array
11 3 6 15 4
void bubbleSort(int a[])
{ int len =
[Link];
for (int i = 0; i < len -1; i++)
{ for
if (a[j]
(int >j =a[j+1])
0; j < {len-i-1; j+//compare
+) { int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
Time Complexity: Worst Case O(n2). Best Case O(n), Avg. Case O(n2).
INSERTION
SORT
Insertion sort is a simple sorting algorithm that is appropriate for small inputs.
Most common sorting technique used by card players.
List is divided into two parts: sorted and unsorted.
In each pass, the first element of the unsorted part is picked up, transferred to the
sorted sublist, and inserted at the appropriate place.
A list of n elements will take at most n-1 passes to sort the data.
Sorted Unsorted
23 78 45 8 32 56 Original List
23 78 45 8 32 56 After pass 1
23 45 78 8 32 56 After pass 2
8 23 45 78 32 56 After pass 3
8 23 32 45 78 56 After pass 4
8 23 32 45 56 78 After pass 5
INSERTION SORT 0 1 2 3 4 5
Array
ALGORITHM 23 78 45 8 32 56
void insertionSort(int a[], int n)
{
for (int i = 1; i < n; i++)
{
int tmp = a[i];
for (int j=i; j>0 && tmp < a[j-1];
j--)
{ a[j] = a[j-1]; //moves element forward
}
a[j] = tmp; //insert element in proper place
}
}
INSERTION SORT –
ANALYSIS
Running time depends on not only the size of the array but also the content of the
array.
⚫ Array is already sorted
Best-case: in O(n)
ascending order.
⚫ Inner loop will not be executed.
⚫ The number of moves: Nil
⚫ The number of key comparisons: (n-1) O(n)
Worst-case: O(n2)
⚫ Array is in reverse order:
⚫ Inner loop is executed i-1 times, for i = 2,3, …, n
⚫ The number of moves: 2*(n-1)+(1+2+...+n-1)= 2*(n-1)+ n*(n-1)/2
⚫ The number of key comparisons: (1+2+...+n-1)= 2* n*(n-1)/2
O(n2)
Average-case: O(n2)
⚫ We have to look at all possible initial data organizations.
So, Insertion Sort time complexity is O(n2)
SELECTION
SORT
The list is divided into sorted and unsorted lists.
Find the smallest element from the unsorted sublist and swap it with the element at the beginning of the
unsorted data.
After each selection and swapping, the index between the two sublists move one element ahead
It is increasing the number of sorted elements and decreasing the number of unsorted ones.
Pass denotes moving one element from the unsorted sublist to the sorted sublist at each time.
A list of n elements requires n-1 passes to completely rearrange the data.
SELECTION
SORT
Sorted Unsorted
23 78 45 8 32 56 Original List
8 78 45 23 32 56 After pass 1
8 23 45 78 32 56 After pass 2
8 23 32 78 45 56 After pass 3
8 23 32 45 78 56 After pass 4
8 23 32 45 56 78 After pass 5
SELECTION
SORT 0 1 2 3 4
void selectionSort( int a[]) Array
{ 11 3 6 15 4
for (int i = 0; i < [Link] - 1; i++) {
int min_index = i;
for (int j = i+1; j < [Link] ; j++)
{
if (a[j] < a[min_index]) {
min_index = j; // searching lowest index
int smallerNumber = a[min_index]; //swapping
a[min_index] = a[i];
a[i] = smallerNumber; }
}
SELECTION SORT -
ANALYSIS
In general, compare the elements and move (exchange)
elements.
So, Count the number of comparisons and the number of
[Link] operations does not affect the final result.
Ignore
In selection sort, the outer for loop executes n-1 times.
Also, invoke swap function once at each iteration.
Total Swaps: n-1
Total Moves: 3*(n-1) (Each swap contains three moves)
The inner for loop executes the size of the unsorted part minus 1 (from 1 to n-1), and in each
iteration it make one comparison.
No. of comparisons = 1+2+...+n-1 = n*(n-1)/2
So, Time complexity is O(n2)
The best case, the worst case, and the average case are same. O(n2)
⚫ It denotes the behavior of the selection sort does not depend on the initial organization of
data.
⚫ Since O(n2) grows so rapidly, the selection sort algorithm is appropriate only for small n.
⚫ Although the selection sort requires O(n2) comparisons, it only requires O(n) moves.
COMPARISON OF O(n), O(log n) AND O(n2)
n O(log n) O(n2 )
16 256
64 4K
256 8 64K
1,024 10 1M
16,384 14 256M
131,072 17 16G
262,144 18 6.87E+10
524,288 19 2.74E+11
1,048,576 20 1.09E+12
1,073,741,824 30 1.15E+18
MERGE SORT
• Merge sort is a sorting algorithm that uses the divide, conquer, and
combine algorithmic paradigm.
• Divide means partitioning the n-element array to be sorted into two sub-
arrays of n/2 elements.
• If A is an array containing zero or one element, then it is already sorted.
However, if there are more elements in the array, divide A into two sub-
arrays, A1 and A2 , each containing about half of the elements of A.
• Conquer means sorting the two sub-arrays recursively using merge sort.
Combine means merging the two sorted sub-arrays of size n/2 to
produce the sorted array of n elements.
MERGE SORT -
EXAMPLE
6 3 9 1 5 4 7 2
divide
6 3 9 1 5 4 7 2
divide
divide
6 3 9 1 5 4 7 2
divide divide divide
divide
6 3 9 1 5 4 7 2
merge merge merge merge
3 6 1 9 4 5 2 7
merge merge
1 3 6 9 2 4 5 7
merge
1 2 3 4 5 6 7 9
Time Complexity is O(n log
QUICKSORT
• This algorithm works by using a divide-and-conquer strategy to divide a single
unsorted array into two smaller sub-arrays.
• The quick sort algorithm works as follows:
• 1. Select an element pivot from the array elements.
• 2. Rearrange the elements in the array in such a way that all elements that are
less than the pivot appear before the pivot and all elements greater than the
pivot element come after it (equal values can go either way). After such a
partitioning, the pivot is placed in its final position. This is called the partition
operation.
• 3. Recursively sort the two sub-arrays thus obtained. (One with sub-list of values
smaller than that of the pivot element and the other having higher value
elements.)
• Like merge sort, the base case of the recursion occurs when the array
has zero or one element because in that case the array is already
sorted.
• After each iteration, one element (pivot) is always in its final position.
Hence, with every iteration, there is one less element to be sorted in
the array.
• Thus, the main task is to find the pivot element, which will partition
the array into two halves. To understand how we find the pivot
element, follow the steps given below. (We take the first element in
the array as pivot.)
Complexity of Quick Sort
• In the average case, the running time of quick sort can be given as O(n
log n). The partitioning of the array which simply loops over the
elements of the array once uses O(n) time
Pseudocode Quick Sort
void quick_sort(int a[], int beg, int end)
{
int loc;
if(beg<end)
{
loc = partition(a, beg, end);
quick_sort(a, beg, loc-1);
quick_sort(a, loc+1, end);
}
}
partition(int a[], int beg, int end)
{ if(flag!=1)
int left, right, temp, loc, flag; {
loc = left = beg; while((a[loc] >= a[left]) && (loc!=left))
right = end; left++;
flag = 0; if(loc==left)
while(flag != 1) flag =1;
{ else if(a[loc] <a[left])
{
while((a[loc] <= a[right]) && (loc!=right))
temp = a[loc];
right--;
a[loc] = a[left];
if(loc==right) a[left] = temp;
flag =1; loc = left;
else if(a[loc]>a[right]) }
{ }
temp = a[loc]; }
a[loc] = a[right]; return loc;
a[right] = temp; }
loc = right;
}
QU ICKS ORT – ANALYSIS
Fastest known sorting
Average case complexity O(n log
n)
Worst-case complexity O(n2)
⚫ Rarely happens, if coded correctly
Thank You
1.
References
Goodrich, Michael T & Roberto Tamassia, and “Data Structures & Algorithms in Java”, WILEY
publications 2015.
2. Sartaj Sahni, “Data Structures, Algorithms and Applications in Java”, Second Edition, Universities
Press.
3. Mark Allen Weiss, “Data Structures & Algorithm Analysis in Java”, Third Edition,
Pearson
Publishing.
67