SWE-203 L Data Structure and Algorithm SSUET/QR/114

LAB#05
Sorting on Linear Array

Objective:
To sort a linear array using Selection Sort, Bubble Sort and Merge Sort.

Lab Tasks
1. Object:
Write a program for Selection sort that sorts an array containing numbers, prints all the sort
values of array each followed by its location.
Program

package
lab.pkg5; import
Output
java.util.*;
run:
public
[5, 30, class
45, 60,Lab5
70, {90]
BUILD SUCCESSFUL (total time: 4 seconds)
public static void selectionSort(int[] number)
{ for (int i = 0; i < number.length; i++) {
int min =i;
for (int j = i + 1; j < number.length; j++)
{ if (number[j] < number[min]) {
min = j;
}
}
int swap = number[i];
number[i] =
number[min];
number[min] = swap;
}
}
public static void main(String[] args) {
int[] array = new int[]{5, 30, 60, 45, 90,
70}; selectionSort(array);
System.out.println(Arrays.toString(array));

Name: Rabia Khan 1

Roll no.: 2020-SE-
SWE-203 L Data Structure and Algorithm SSUET/QR/114

2. Object:
Write a program that takes 10 numbers as input in an array. Sort the elements of array by using
Bubble sort. Print each iteration of the sorting process.
Program

package
lab.pkg5; import
Output
java.util.*;
run:
public class
Before Bubble Lab5 {
Sort
static
8 90 void
20 31 70bubbleSort(int[]
340 array)
54 { int a = array.length;
Afterint tem =Sort
Bubble 0;
for(int
8 20 31 54 70i=0;90i 340
< a; i++)
{ for(int j=1; j < (a-i); j+
+){
if(array[j-1] > array[j]){
//swaping the
elements tem =
array[j-1]; array[j-1]
= array[j]; array[j] =
tem;
}
}
}
}
public static void main(String[] args)
{ int array[]
={8,90,20,31,70,340,54};
System.out.println("Before Bubble
Sort"); for(int i=0; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println(
);
bubbleSort(array);

Name: Rabia Khan 2

Roll no.: 2020-SE-
SWE-203 L Data Structure and Algorithm SSUET/QR/114

3. Object:
Write a program that takes 10 random numbers in an array. Sort the elements of array by using
Merge sort. Print each iteration of the sorting process.
Program

package
lab.pkg5; import
java.util.*;

public class Lab5 {

void merge(int array[], int d, int e, int f) {
// Find two subarrays to be
merged int num1 = e - d + 1;
int num2 = f - e;
// Create temp arrays
int M[] = new
int[num1]; int N[] =
new int[num2];
//Copy data to temp arrays
for (int i = 0; i < num1; +
+i){
M[i] = array[d + i];
}
for (int j = 0; j < num2; ++j)
{ N[j] = array[e + 1 + j];
}
// Initial indexes of first and second
subarrays int i = 0, j = 0;
// Initial index of merged subarry
array int k = d;
while (i < num1 && j < num2)
{ if (M[i] <= N[j]) {
array[k] =
M[i]; i++;
}
else {
array[k] =
N[j]; j++;
}
k+
+;
}
// Copy elements of M[] if
any while (i < num1) {
array[k] =
M[i]; i++;
k++;
}
// Copy elements of N[] if any

Name: Rabia Khan 3

Roll no.: 2020-SE-
SWE-203 L Data Structure and Algorithm SSUET/QR/114

k++;
}
}
void sort(int array[], int d, int f)
{ if (d < f) {
int e =d+ (f-d)/2;
sort(array, d, e);
sort(array, e + 1,
f); merge(array, d,
e, f);
}
}
static void printArray(int array[])
{ int n = array.length;
for (int i = 0; i < n; ++i)
{ System.out.print(array[i] +
" ");
System.out.println();
}
}
public static void main(String[] args) {
int array[] = { 46, 27, 14, 55, 71,
19 };
System.out.println("Array"
); printArray(array);
Lab5 ob = new Lab5();
ob.sort(array, 0, array.length -
1);
Output

run:
Arr
ay
46
27
14
55
71
19

Sorted Array
14
19
27
46
55
71

Name: Rabia Khan 4

Roll no.: 2020-SE-
SWE-203 L Data Structure and Algorithm SSUET/QR/114

Home Task
1. Object:
Declare an array of size n to store account balances. Initialize with values 0 to 1000000 and
sort Account No’s according to highest balance values by using Quick sort, For e.g.:
Account No. 3547 Balance 28000
Account No. 1245 Balance 12000
Program

package
lab.pkg5; import
java.util.*;

public class Lab5 {

public static void main(String[] args) {
int[] array = {10500,4000,35000,40000};
quickSort(array,0,array.length-1);
for (int i = array.length-1;i>=0;
i--){
System.out.printf("Account No %d Balance:%d\n",i+1,array[i]);
}
}
public static void swap(int[] array, int i, int j)
{
int temp =
array[i]; array[i]
= array[j];
array[j] = temp;
}
public static int partition(int[] array, int low, int
high){ int pivot = array[high];
int i = (low - 1);
for(int j = low; j <= high - 1; j++)
{ if (array[j] < pivot){
i++;
int temp =
array[i]; array[i]
= array[j];
array[j] = temp;
}
}
int temp = array[i+1];
array[i+1] =
array[high];
array[high] = temp;
return (i + 1);
}
public static void quickSort(int[] array, int low, int

Name: Rabia Khan 5

Roll no.: 2020-SE-
SWE-203 L Data Structure and Algorithm SSUET/QR/114

}
}

Output

run:
Account No 4
Balance:40000 Account No
3 Balance:35000 Account
No 2 Balance:10500
Account No 1

Name: Rabia Khan 6

Roll no.: 2020-SE-
 SWE-203 L Data Structure and SSUET/QR/

LAB#06
Searching in a Linear Array

Objective:
To find an element in linear array using Linear Search and Binary Search

Lab Task
1. Object:
Declare an array of size 10 to store account balances. Initialize with values 0 to
1000000. Check all array if any value is less than 10000. Show message:
Account No. Low Balance
Account No. Low Balance
Program

package
lab.pkg6; import
java.util.*; public
class Lab6 {
public static void main(String[] args)
{ int array[]=new int[10];
for (int i=0;i<array.length;i++)
{ array[i]=(int)
(Math.random()*100000);
}
for (int i=0;i<array.length;i++)
{ if (array[i]<10000)
System.out.println("Account "+(i+1)+" has low balance.");
}

Output

run:
Account 9 has low
balance. Account 10 has
low balance.

Name: Rabia Khan 1

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

2. Object:
Write a program to search in array using Array built-in class.
Program

package
lab.pkg6; import
Output
java.util.*;
run:
public class
Search Lab6 {
for :65
65 at index:3
publicSUCCESSFUL
BUILD static int linearSearch(int[]
(total time: 2array, int
seconds)
num){ for(int i=0;i<array.length;i++){
if(array[i] ==
num ){ return i;
}
}
return -1;
}

public static void main(String[] args)

{ Scanner input = new
Scanner(System.in);
System.out.print("Search for :");
int n = input.nextInt();
int[] a= {5,158,20,65,89,95};
int num = n;
System.out.println(num+" at index:"+linearSearch(a, num));

Name: Rabia Khan 2

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

Home Task
1. Object:
Write a function called occurrences that, given an array of numbers A, prints all the distinct
values in A each followed by its number of occurrences. For example, if A = (28, 1, 0, 1, 0, 3,
4, 0, 0, 3), the function should output the following five lines (here separated by a semicolon)
“28 1; 1 2; 0 4; 3 2; 4 1”.
Program

package lab.pkg6;
import
Output
java.util.HashSet;
import
run:
java.util.Scanner;
Array [0, 1, 3, 4, 28]
0 occurs 4 times
1public
occursclass Lab6 {
2 times
3 occurs 2 times
public 1static
4 occurs timesvoid main(String[] args)
{ int array[]
28 occurs 1 times= {28,1,0,1,0,3,4,0,0,3};
BUILD SUCCESSFULa(total
HashSet<Integer> = new HashSet<Integer>();
time: 0 seconds)

for(int i=0;i<array.length;i++){

a.add(array[i]);
}
System.out.println("Array
"+a); for(int set : a){
int count = 0;
for(int j=0;j<array.length;j+
+){ if(set==array[j]){
count++;
}
}
System.out.println(set+" occurs "+count+ " times ");
}

Name: Rabia Khan 3

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

LAB#07
Singly Linked List Implementation

Objective:
Implementing singly linked list and associated operations

Class Activity
1. Object:
Program

public class SinglyLinkedList

{ class Node{
int data;
Node
next;

public Node(int data)

{ this.data = data;
this.next = null;
}
}

//Represent the head and tail of the singly linked

list public Node head = null;
public Node tail = null;

//addNode() will add a new node to the

list public void addNode(int data) {
//Create a new node
Node newNode = new Node(data);

//Checks if the list is

empty if(head == null) {
//If list is empty, both head and tail will point to new
node head = newNode;
tail = newNode;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode will become new tail of the
list tail = newNode;
}
}

//display() will display all the nodes present in the

Name: Rabia Khan 1

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

//Node current will point to

head Node current = head;

if(head == null)
{ System.out.println("List is
empty"); return;
}
System.out.println("Nodes of singly linked list:
"); while(current != null) {
//Prints each node by incrementing
pointer System.out.print(current.data + "
"); current = current.next;
}
System.out.println();
}
public static void main(String[] args)
{ SinglyLinkedList sList = new
SinglyLinkedList();

//Add nodes to the

list
sList.addNode(1);
sList.addNode(2);
sList.addNode(3);
sList.addNode(4);

//Displays the nodes present in the

list sList.display();

Output

run:
Nodes of singly linked list:
1234
BUILD SUCCESSFUL (total time: 1 second)

Name: Rabia Khan 2

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

Lab tasks
1. Object:
Program
package lab.pkg7;

public class Lab7

{ Node head =
null; static class
Node {
int data;
Node next;
public Node(int data){
this.data = data;
next = null;
}
}
public void insertbegining(int data){
Node n = new Node(data);
n.next= head;
head = n;
}
public void insertAtPosition(Node prev, int data){
Node n = new Node(data);
Node temp;
temp= prev.next;
prev.next= n;
n.next = temp;
}
public void insertend(int data){
Node n = new Node(data);
Node temp=head;
Node prev=null;
while(temp!=null){
prev=temp;
temp=temp.next;
} prev.next=n; n.next=null;
}
public void delete(int data){
Node temp,prev=null;
temp=head;
while(temp!=null && temp.data!=data){
prev=temp; temp=temp.next;
}
prev.next=temp.next;
}
public void searchNode(int data){
Node current= head;
int i=1;
boolean flag=false;
Name: Rabia Khan 3
Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

if(head==null)
{ System.out.println("Empty
List");
}
else{
while(current!=null)
{ if(current.data==data)
{
flag=true;
break;
} i+
+;
current = current.next;
}
}
if (flag)
System.out.println("Element is present in the list at the position:" + i);
else
System.out.println("Element is present not in the list :");
}
public void printList(){
Node temp=head;
while(temp!=null){
System.out.println(temp.data);
temp=temp.next;
}
}
public static void main(String[] args)
{ System.out.println("Records of Students
are:"); Lab7 ll = new Lab7();
Node first= new Node(89);
ll.head= first;
Node second = new Node(25);
first.next = second;
Node third = new Node(78);
second.next = third;
Node fourth = new Node(69);
third.next= fourth;
Node fifth = new Node(92);
fourth.next= fifth;
Node sixth = new Node(33);
fifth.next=sixth;
Node seventh = new Node(48);
sixth.next=seventh;
Node eighth = new Node(8);
seventh.next=eighth ;
Node ninth = new Node(18);
eighth.next=ninth ;
Node tenth = new Node(9);
ninth.next=tenth ;
ll.printList();
Name: Rabia Khan 4
Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

System.out.println("\nAfter Insertion");

Name: Rabia Khan 5

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

ll.insertbegining(77);
ll.insertAtPosition(second,40);
ll.insertend(70);
ll.printList(); System.out.println("\
nSearching"); ll.searchNode(48);
System.out.print("\nAfter
Deletion"); ll.delete(18);
ll.printList();
}
}

Output

run:
Records of Students are:
89
25
78
69
92
33
48
8
18
9

After
Insertion 77
89
25
40
78
69
92
33
48
8
18
9
70

Searching
Element is present in the list at the position:9

After
Deletion77 89
25
40
78

Name: Rabia Khan 6

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

69
92
33
48
8
9
70
BUILD SUCCESSFUL (total time: 0 seconds)

Home Tasks
1. Object:
Program

package lab.pkg7;

public class Lab7

{ Node head =
null;
static class Node
{ String data;
Node next;
public Node(String
data){ this.data =
data;
next = null;
}
}
public void insertbegining(String
data){ Node n = new Node(data);
n.next=
head; head
= n;
}
public void insertAtPosition(Node prev, String data)
{ Node n = new Node(data);
Node temp;
temp=
prev.next;
prev.next= n;
n.next = temp;
}
public void insertend(String
data){ Node n = new
Node(data); Node temp=head;
Node prev=null;
while(temp!

Name: Rabia Khan 7

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

n.next=null;
}
public void delete(String data){
Node temp,prev=null;

temp=head;
while(temp!=null && temp.data!=data){
prev=temp;
temp=temp.next;
}
prev.next=temp.next;
}
public void searchNode(String data){
Node current= head;
int i=1;
boolean flag=false;
if(head==null){
System.out.println("EMPTY LIST");
}
else{
while(current!=null)
{ if(current.data==data)
{
flag=true; break;
} i+
+;
current = current.next;
}
}
if (flag)
System.out.println("Element is present in the list at the position: " + i);
else
System.out.println("Element is not present in the list: ");
}
public void printList(){
Node temp=head;
while(temp!=null){
System.out.println(temp.data);
temp=temp.next;
}
}
public static void main(String[] args)
{ System.out.println("Records Of Students
Are:");
Lab7 ll = new Lab7();
Node first= new Node("Rabia");

ll.head= first;
Node second = new Node("Saqib");
first.next = second;
Node third = new Node("Jazil");
Name: Rabia Khan 8
Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

second.next = third;

Name: Rabia Khan 9

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

Node fourth = new

Node("Hira"); third.next=
fourth;
Node fifth = new
Node("Sana"); fourth.next=
fifth;
Node sixth = new
Node("Alina"); fifth.next=sixth;
Node seventh = new
Node("Ibad");
sixth.next=seventh;
Node eighth = new
Node("Sami");
seventh.next=eighth ;
Node ninth = new Node("Dua");
eighth.next=ninth ;
Node tenth = new
Node("Sadia");
ninth.next=tenth ;
ll.printList(); System.out.println("\
nAfter Insertion");
ll.insertbegining("Maham");
ll.insertAtPosition(fourth,"Anum");
ll.insertend("Saboor");
ll.printList(); System.out.println("\
nSearching"); ll.searchNode("Ibad");

Output

run:
Records Of Students
Are: Rabia
Saq
ib
Jazi
l
Hir
a
San
a
Ali
na
Iba
d
Sa
mi
Dua
Sad
ia

Name: Rabia Khan 1

Roll no.: 2020-SE-
SWE-203 L Data Structure and SSUET/QR/

Alina
Ibad
Sami
Dua
Sadia
Sabo
or

Searching
Element is present in the list at the position: 9

After Deletion:
Maham Rabia
Jazil
Hira
Anu
m
Sana
Alina
Ibad
Sami
Dua
Sadia

Name: Rabia Khan 1

Roll no.: 2020-SE-