St.
Francis Institute of Technology, Mumbai-400 103
Department of Information Technology
A.Y. 2025-2026
Class: SE-ITA/B, Semester: III
Subject: DATA STRUCTURE LAB
Experiment 8 : Sorting algorithm Implementation
1. Aim: Write a program to implement Insertion sort / Selection sort and Merge sort/Quick
sort algorithm
2. Objectives: After study of this experiment, the student will be able to
● To use basic principles of programming as applied to searching and sorting
● To learn fundamentals of sorting techniques
3. Outcomes: After study of this experiment, the student will be able to
● Implement sorting algorithms on given set of data and understand its operations
● Understand the concepts and apply the techniques of searching, hashing and sorting
4. Prerequisite: Sorting techniques .
5. Requirements: PC and Turbo C compiler version 3.0
6. Pre-Experiment Exercise: Brief Theory:
A. Sorting
A sorting algorithm is defined as an algorithm that puts elements of a list in a certain
order (that can either be numerical order, lexicographical order or any user-defined
order). Efficient sorting algorithms are widely used to optimize the use of other
algorithms like search and merge algorithms which require sorted lists to work correctly.
There are two types of sorting:
• Internal sorting which deals with sorting the data stored in computer’s memory •
External sorting which deals with sorting the data stored in files. External sorting is
applied when there is voluminous data that cannot be stored in computer’s memory.
B. Types of Sorting Techniques
1. Selection Sort
The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of
the list and swaps it with the first element of the unsorted part. This process is repeated for the
remaining unsorted portion until the entire list is sorted.
Technique
Consider an array ARR with N elements. Selection sort works as follows:
First find the smallest value in the array and place it in the first position. Then, find the
second smallest value in the array and place it in the second position. Repeat this procedure
until the entire array is sorted. Therefore,
● In Pass 1, find the position POS of the smallest value in the array and then swap
ARR[POS] and
ARR[0]. Thus, ARR[0] is sorted.
● In Pass 2, find the position POS of the smallest value in sub-array of N–1 elements. Swap
ARR[POS] with ARR[1]. Now, ARR[0] and ARR[1] is sorted.
● In Pass N–1, find the position POS of the smaller of the elements ARR[N–2] and
ARR[N–1]. Swap
ARR[POS] and ARR[N–2] so that ARR[0], ARR[1], ..., ARR[N–1] is sorted.
Algorithm Selection sort:
2. Insertion sort
We divide the array into two parts:
● Sorted part (initially contains the first element)
● Unsorted part (remaining elements)
We pick one element from the unsorted part at a time and insert it into the correct position in the
sorted part.
3. Merge sort:
● 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.
Algorithm Merge Sort:
4. Quick sort
Quick Sort is another Divide and Conquer algorithm. Instead of merging (like Merge Sort), it
uses a pivot to partition the array.
Steps of Quick Sort
1. Choose a pivot element (first, last, middle, or random).
2. Partition the array into two subarrays:
○ Left side → elements smaller than pivot
○ Right side → elements greater than pivot
3. Recursively apply Quick Sort to each subarray.
4. Combine → since the array is sorted in-place, no merging is required.
7. Laboratory Exercise
A. Procedure
Write a C program to implement a sorting algorithm ,show all the following
operations..
i) Enter values in array
ii) Sorting algorithm menu
iv) Display array after every pass (optional)
v) Exit
B. Result/Observation/Program code:
Observe the output for the above code and print it.
8. Post-Experiments Exercise
A. Questions:
1. Sort the following numbers using any above method
13,2,4,56,23,57,89,90,40,34,23,12
B. Conclusion:
1. Summary of Experiment
2. Importance of Experiment
3. Applications of Experiment
C. References:
1. S. K Srivastava, Deepali Srivastava; Data Structures through C in Depth; BPB
Publications; 2011.
2. Reema Thareja; Data Structures using C; Oxford.
3. Data Structures A Pseudocode Approach with C, Richard F. Gilberg & Behrouz
A. Forouzan, second edition, CENGAGE Learning.
--------------------------------