Algorithms & Data Structures - Sorting

Objective:
At the end of the class you should be in a position to answer:
√Understand the basic concepts of internal and external sorts
√Discuss the relative efficiency of different sorts
√Recognize and discuss selection, insertion and exchange sorts
√Discuss the design and operation of external sorts
√Design and implement sequential searches
√Discuss the relative merits of different sequential searches
√Design and implement binary searches


Sort Concepts
√Sorts arrange data according to their value.
√Sorting algorithm are classified as either internal or external.



Insertion Sorts
In each pass of an insertion sort, one or more pieces of data are inserted into their correct location in an ordered list. In this section we study two insertion sorts: the straight insertion sort and the shell sort.



Explanation
In a straight insertion sort, the list at any moment is divided into sorted and unsorted sublists. In each pass the first element of the unsorted sublist is inserted into the sorted sublist.
If we have a list of n elements, it will take at most n-1 passes to sort the data.
The straight selection sort efficiency is O(n²)





Shell Sort
The shell sort algorithm named after its creator, Donald L.Shell.
It is an improved version of the straight insertion sort in which diminishing partitions are used to sort the data.
The Worst case running time of shell sort using shell’s increment is O(N²).









Selection Sort
In each pass of the selection sort, the smallest element is selected from the unsorted sublist and exchanged with the element at the beginning of the unsorted list.
The straight selection sort efficiency is O(n²)





Bubble Sort
Bubble sort is an exchange sort. The basic operation is the exchange of an adjacent pair of elements. So in the single bubble sort algorithm, the program will pass through the data, switching consecutive items which are out of order. After each pass through the list, the program checks to see if any switches were made. If there were, it passes through the list again, switching consecutive items which are still out of order. If no switches are made during an entire pass through the list, the data is sorted.

In the best case the efficiency of bubble sort is O(N).
In the worst case the efficiency of bubble sort is O(NM²)

Example of Bubble sort
Here is an example : we want to sort 390, 205, 182, 45, 235
Bubble sort for the first pass (exchange of an adjacent pairs)
390 205 182 45 235 (Switch 1)
205 390 182 45 235 (Switch 2)
205 182 390 45 235 (Switch 3)
205 182 45 390 235 (Switch 4)
205 182 45 235 390 ( First pass-sorted list)

the first pass moves the largest element (390) to the n^th position ,forming a sorted list of length one
the second pass only has to consider (n-1) elements and moves the second largest element to the (n-1) position.    

Quick Sort
Quick sort is an exchange sort in which a pivot key is placed in its correct position in the array while rearranging other elements widely dispersed across the list.
The efficiemcy of the Quick sort is :
Worst Case = O(N²) - the pivot is the smallest element
Average Case = O(N log n)
Best case = O(N log N) - the pivot is in the middle



Radix Sort
The bin sorting approach can be generalized in a technique that is known as radix sorting.
Assume that we have n integers in the range (0,n²) to be sorted. (For a bin sort, m = n², and we would have an O(n+m) = O(n²) algorithm.) Sort them in two phases:
1. Using n bins, place a_i into bin a_i mod n,
2. Repeat the process using n bins, placing a_i into bin floor(a_i/n), being careful to append to the end of each bin.
This results in a sorted list.

Example
Consider the list of integers
36 9 0 25 1 49 64 16 81 4
Step1: Arrange the element according to the least significant decimal digits








Step2:Arrange the elements according to the most significant digits












Step3: Sorted list is :
0 1 4 9 16 25 36 49 64 81


Merge Sort
The basic merging algorithm takes two input arrays A and B, an output array C, and three counters, Aptr, Bptr, and Cptr, which are initially set to the beginning of their respective arrays. The smaller of A[Aptr] and B[Bptr] is copied to the next entry in C, and the appropriate counters are advanced. When either input list is exhausted, the remainder of the order list is copied to C.

Example
If the array A (Aptr) contains 1, 13 and B (Bptr) contains 2, 15, 27, 38, then the algorithm proceeds as follows.


First, a comparison is done between 1 and 2.
1 is added to C, and then 13 and 2 are compared.



2 is added in C, and 13 and 15 are compared.


The remainder of the array B is then copied to C.