UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk
Lab Manual 03
CS201: Data Structure and Algorithms
Class: BSCS-2k22
Lab 3: Sorting techniques-I
Instructors:
Mr. Awais Mehmood
awais.mehmood@uettaxila.edu.pk
&
Mr. M. Faheem Saleem
muhammad.faheem@uettaxila.edu.pk
CS201: Data Structures and Algorithms Page 1
UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk
Lab Manual 3
Introduction
This lab is about the sorting Operations on Arrays in C++.
Objectives
The objectives of this session is to understand the various sorting operations on arrays in C++.
Tools/Software Requirement
Dev C++
Goals for today’s lab:
• Understanding sorting array operations and write it’s algorithm.
• Convert algorithm to practical implementation.
Sorting Arrays:-
The process of arranging data in a specified order is called sorting. Numeric type data may be
arranged either in ascending or in descending order. Similarly character type data may be
arranged in alphabetical order.
There are different methods to sort data into a list. The most commonly used methods are:
1. Bubble Sort
2. Selection Sort
Bubble Sort:-
Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be
sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.
First pass bubble out the largest element and places in the last position and second pass place the
second largest in the second last position and so on. Thus, in the last pass smallest items is placed
in the first position. Because, it only uses comparisons to operate on elements, it is a comparison
sort.
Example:-
Let us take the array of numbers "5 1 4 2 9", and sort the array from lowest number to greatest
number using bubble sort algorithm. In each step, elements written in bold are being compared.
First Pass: Considering length n
( 5 1 4 2 9 ) ⟶ ( 1 5 4 2 9 ), Here, algorithm compares the first two elements, and swaps them.
CS201: Data Structures and Algorithms Page 2
UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk
( 1 5 4 2 9 ) ⟶ ( 1 4 5 2 9 ), Swap since 5 > 4
( 1 4 5 2 9 ) ⟶ ( 1 4 2 5 9 ), Swap since 5 > 2
( 1 4 2 5 9 ) ⟶ ( 1 4 2 5 9 ), Now, since these elements are already in order (9 > 5), algorithm
does not swap them.
Second Pass: Considering length n - 1
(14259)⟶(14259)
( 1 4 2 5 9 ) ⟶ ( 1 2 4 5 9 ), Swap since 4 > 2
(12459)⟶(12459)
Third Pass: Considering length n -2
( 1 2 4 5 9 ) ⟶ ( 1 2 4 5 9)
(12459)⟶(12459)
Fourth Pass: Considering length n -3
(12459)⟶(12459)
Example 4:-
Sort the following array:-
{6, 1, 2, 3, 4, 5}
CS201: Data Structures and Algorithms Page 3
UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk
We formally state the bubble sort algorithm.
Algorithm:-
(Bubble Sort) Bubble (Data, N)
CS201: Data Structures and Algorithms Page 4
UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk
Here Data is an array with N elements. This algorithm sorts the
elements in DATA.
1. Repeat Step 2 and 3 for K= 1 to N-1.
2. Set PTR=1. [Initialize pass pointer P].
3. Repeat while PTR ≤ N – K [Executes pass]
a. If DATA[PTR]>DATA[PTR+1] then
Interchange DATA[PTR] and DATA[PTR+1].
[End of If structure]
b. Set PTR = PTR +1.
[End of inner Loop]
[End of Step 1 outer Loop]
4. Exit.
Task: Implement bubble sorting algorithm
• For integer array
• For char array
Selection Sort Algorithm:
1. Start with the first element as the minimum element in the unsorted part.
2. Iterate through the unsorted part to find the actual minimum element.
a. Initialize a variable `minIdx` to the index of the current element.
b. For each element in the unsorted part:
- If the current element is less than the element at `minIdx`, update `minIdx` to
the index of the current element.
3. Swap the minimum element (found at `minIdx`) with the first element in the unsorted
part.
4. Move the boundary between the sorted and unsorted parts one element to the right by
incrementing the index where the sorted part ends.
5. Repeat steps 1-4 until the entire array is sorted.
CS201: Data Structures and Algorithms Page 5
UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk
Implementation for Linear Search
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Assume the current element is the minimum
int minIdx = i;
// Find the index of the minimum element in the unsorted part
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) { // For descending order, use arr[j] > arr[minIdx]
minIdx = j;
}
}
// Swap the found minimum element with the first element
std::swap(arr[i], arr[minIdx]);
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout <<endl;
return 0;
}
CS201: Data Structures and Algorithms Page 6
