DHA Suffa University
Department of Computer Science
CS 2001L– Data Structures and Algorithms Lab - (Fall-2024)
Lab 04 – Sorting Algorithms-Part-02
Objective: Implementation of the following Sorting Algorithm
1. Quick Sort
2. Shell Sort
3. Radix Sort
Quick Sort:
Quick sort is a fast sorting algorithm, which is used not only fors educational purposes, but
widely applied in practice. On the average, it has O(n log n) complexity, making quick sort
suitable for sorting big data volumes. There are many different versions of quick sort that pick
pivot in different ways.
● Always pick first element as pivot.
● Always pick last element as pivot
● Pick a random element as pivot.
● Pick median as pivot
Implementation:
Shell Sort:
Shell sort is an improvement over insertion sort. It compares the element separated by a gap of
several positions. A data element is sorted with multiple passes and with each pass gap value
reduces. Shell sort is an algorithm that first sorts the elements far apart from each other and
successively reduces the interval between the elements to be sorted
In shell sort, elements at a specific interval are sorted. The interval between the elements is
gradually decreased based on the sequence used. The performance of the shell sort depends on
the type of sequence used for a given input array.
Some of the optimal sequences used are:
Shell’s original sequence: N/2 , N/4 , …, 1
Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2
Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1.
Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
Suppose, we need to sort the following array.
We are using the shell’s original sequence (N/2, N/4, ...1) as intervals in our algorithm.
In the first loop, if the array size is N = 8 then, the elements lying at the interval of N/2 = 4 are compared
and swapped if they are not in order.
The 0th element is compared with the 4th element.
If the 0th element is greater than the 4th one then, the 4th element is first stored in temp variable and
the 0th element (ie. greater element) is stored in the 4th position and the element stored in temp is
stored in the 0th position.
This process goes on for all the remaining elements.
In the second loop, an interval of N/4 = 8/4 = 2 is taken and again the elements lying at these intervals
are sorted.
The elements at 4th and 2nd position are compared. The elements at 2nd and 0th position are also
compared. All the elements in the array lying at the current interval are compared.
The same process goes on for remaining elements.
Finally, when the interval is N/8 = 8/8 =1 then the array elements lying at the interval of 1 are sorted.
The array is now completely sorted.
Implementation:
Radix Sort:
There are two types of radix sorting:
LSD radix sort starts sorting from the end of strings (least significant digit).
MSD radix sort starts sorting from the beginning of strings (most significant digit).
LSD radix sort
The Least Significant Digit Radix sort algorithm is a classic near-linear-time sorting algorithm. It
is a good example of how additional information about the inputs for an algorithm allow us to
improve our code’s efficiency.
Figure 4.2: LSD radix sort
MSD radix sort
MSD radix sort resembles string quicksort but partitions the strings into σ parts instead of three parts.
Figure 4.3:MSD radix sort
Implementation:
Lab Task
Redefine the shellSort (int *array, int n) function for arrangement in descending order. Also
print the number sequence produced after each gap calculation.
Assignment:
Given the csv file, import the file in a 2D matrix then perform the following tasks:
1. Sort the column book title by applying quick sort and shell sort in such a
way that their respective data in the rows is shifted with the title too, while
sorting.
a. Sort the column through quick sort by taking pivot as first value.
2. Sort the given file through bookid column using LSD radix sort.
Submission Guidelines
Write C++ code, separate function for each operation.
Place your file in a folder named with your rollno (cs172xxx) where xxx is your 3 digit
rollno.
Upload it on LMS.
Note:
Remember -100 policy for plagiarism.
