# Queue Operations In Real World Scenarios Computer Science Essay

**Published:** **Last Edited:**

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

A group of programmers were wondering on how the QUEUE operations can be used in the real world application. You as a team member were asked to produce a program to demonstrate the QUEUE operations in a way that can be easily understood.

## Task 1

You have to write and produce output of the program that demonstrates QUEUE operations (FIFO) in any programming language (preferably C++). Draw the flow chart of the program.

[40 Marks]

## QUESTION 2

## Scenario

As one of the analyst programmers in a software development team, you were assigned to analyse which sorting algorithm is the most suitable and most efficient for sorting up to 50,000 numerical data. Based on your analysis, you are to prepare a report covering the following details.

## Task 1

You have to write a report presenting your findings and justifications for your selection of the sorting algorithm (any 5 types, the selection criteria are based on complexity, simplicity, and implementation). Besides the findings and justifications your report should also contain the advantages and disadvantages of each sorting algorithm.

[60 Marks]

Module Name

Type of coursework /reference no.

Title of the coursework

Student's Declaration

I certify that this assignment is my own work and where materials have been used from other resources, they have been properly acknowledged. I also understand that I will face all the possibility of failing unit if the contents of this assignment are plagiarized.

Signed : ____________________ Date : __________________

## Tick as appropriate Marks obtained

## Year One

## Year Two

## Year

## Three

Date handout

Date received

Assessor's comments/

Feedback.

Student's comments

Name/Signature of Assessor

Name & Signature of Internal verifier.

Date

Date

KOLEJ LINTONUEL logo with text

## B.Sc. (Hons) Software Engineering

## ASSESSMENT CRITERIA AND GRADING SHEET

## (a)

## (b)

## (c)

## (d)

## No.

## Breakdown of assessment criteria

## Weight (%)

## Range of achievement (ï‚‚)

## Marks Awarded (%)

## 1st

## 2ndU

## 2ndL

## 3rd

a

Describe and demonstrate the QUEUE operations with coding.

40%

B

Present the findings the different types of sorting algorithm.

30%

C

Justify the findings of the sorting algorithm

15%

D

Critically, able to explain the advantages and disadvantages of each sorting types.

15%

Contents

## LIST OF FIGURES

1.1 DEFINATION OF QUEUE:Â is a particular kind ofÂ collectionÂ in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. This makes the queue aÂ First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once an element is added, all elements that were added before have to be removed before the new element can be invoked (Anon., 2011).

## 1.2 REPRESENTING A QUEUE

The defining attribute of a queue data structure is the fact that allows access to only the front and back of the structure. Furthermore, elements can only be removed from the front and can only be added to the back. In this way, an appropriate metaphor often used to represent queues is the idea of aÂ checkout line (Harold Sanchez, 2009).

## 1.3 QUEUE IMPLEMENTATION

Theoretically, one characteristic of a queue is that it does not have a specific capacity. Regardless of how many elements are already contained, a new element can always be added. It can also be empty, at which point removing an element will be impossible until a new element has been added again.

Fixed length arrays are limited in capacity and inefficient because items need to be copied towards the head of the queue. However conceptually they are simple and work with early languages such as Fortran and basic which did not have pointers or objects. Most modern languages with objects orÂ pointersÂ can implement or come with libraries for dynamic lists. SuchÂ data structuresÂ may have not specified fixed capacity limit besides memory constraints. QueueÂ overflowÂ results from trying to add an element onto a full queue and queueÂ underflowÂ happens when trying to remove an element from an empty queue (Nguyen et al., 2009).

## 1.3 1 EXAMPLE OF CODES IN C++

produce output of the program that demonstrates QUEUE

#include <iostream>

using namespace std;

int main()

## {

char array[5];

cout<<"enter 5 characters"<<endl;

for(int i=0; i<5; i++)

{ cin>>array [i];}

cout<<"the characters in queue are"<<endl;

for (int j=0; j<5; j++)

## {

cout<<array[j];

## }

## TASK 1

This program demonstrates QUEUE operations (FIFO) in C++ programming language.

## 1.4 PRINT SCREEN

View if queue is empty

View if Queue is full

View last character in Queue

View first character in Queue

Exit button

Delete Queue

Add button

Queue Display screen

Input screen

## FIGURE: 1.1 Queue Operation

The print screen above explain the basic function of a queue, that is first in and last number display, delete queue, empty queue and queue is full, the screen shot of the system has the button for closing of the queue system if the need to stop all operation arise.

## FIGURE: 1.2 Flowchart diagram

## 1.5 Coding of the system in Visual Basic

Private Sub ButtonX7_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button4.Click

'This is for exiting the application system

Dim z As String = MessageBox.Show("Are you sure u want to exit the application?", "Confirmation", MessageBoxButtons.YesNo, MessageBoxIcon.Warning)

If z = vbYes Then

End If

Me.Close()

End Sub

Private Sub ButtonX6_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button6.Click

listbox1.Items.Clear() 'this empty the screen of the system

End Sub

Private Sub ButtonX5_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button7.Click

If listbox1.Items.Count >= 10 Then 'this is to determine value limitation

MessageBox.Show("Queue is Full", "OK", MessageBoxButtons.OK, MessageBoxIcon.Information)

Else

MessageBox.Show("Values are Not Complete or List Empty", "Error", MessageBoxButtons.OK, MessageBoxIcon.Error)

End If

End Sub

Private Sub ButtonX4_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

If listbox1.Text = "" Then 'this determine the number of character in queue

MessageBox.Show("Queue Is Empty or Nothing is Selected", "OK", MessageBoxButtons.OK, MessageBoxIcon.Error)

End If

If listbox1.SelectedIndex <> -1 Then

listbox1.Items.RemoveAt(listbox1.SelectedIndex)

Button5.Enabled = True

End If

End Sub

Private Sub ButtonX3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click

If listbox1.Text = "" Then 'determine which character to delete

MessageBox.Show("Nothing on the List", "Error", MessageBoxButtons.OK, MessageBoxIcon.Error)

Else

Dim str As String

str = listbox1.Items(listbox1.Items.Count - 1)

MessageBox.Show(str)

End If

End Sub

Private Sub ButtonX2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button5.Click

listbox1.Items.Add(TextBox3.Text) 'add integers to system

TextBox3.Text = ""

End Sub

End Class

## 1.6 CONCLUSION

As Software engineer I have implement calculator in visual basic programming language to perform the basic functionality of queue operation, the application can add character, view the first character, and view the last character, delete the first character in queue, the calculator can empty all characters in the queue, and it can determine if queue operation is full as I have determine that ten characters are the maximum queue can hold.

The application has the functionality to exit if the need arise.

## TASK 02

A report presenting your findings and justifications for your selection of the sorting algorithm

2.1 What is Sort?

The process of getting data elements into order is calledÂ sorting. The order may be either ascending or descending order for numbers or alphabetical order for strings (Anon, 2009).

Sorting methods can be classified into two types based on the size of the data to be sorted that is internal sortingÂ andÂ external sorting.

2.1.1Internal-sorting

internal sorting methods are applied on small sets of data which is sufficient to store in the main memory.

Example: bubble sort, insertion sort.

## 2.1.2 External sorting

External sorting methods are applied on large sets of data which reside on secondary storage devices and can't completely fit in the main memory

2.2 Complexity of sorting algorithms:

We can decide complexity of different algorithms by calculating is order on the number of loops and number of iterations the algorithm contain. The complexity can be represented as 0(n) (order of n) (order of n2).

Sorting method can be classified into two types based on the complexity of algorithms that is simple algorithms and sophisticated algorithm.

## 2.3 Simple algorithms:

The algorithm having complexity of 0(on), 0(n2) are known as simple algorithms.

2.4 Sophisticated algorithms:

The algorithms having complexity of 0(n log2n) are known as sophisticated algorithms.

2.5 Stable sort:

A stable sort is a one where two records will retain their order when sorted according to a particular field, even when the two fields have the same content. Thus those two records come out in the same relative order that they were in before sorting, although their positions relative to other records may change.

Types of Sorting Algorithms are

Selection sort

Bubble sort

Insertion sort

Quick sort

Shell sort

Combo sort

Merge sort

Heap sort

Counting sort

Bucket sort

Radix sort

Time sort

Distribution sort

2.6 SELECTION SORT: This type of sort is called selection sort because it works by first find a smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted (Michael., et al. 2009)

## 2.6.1 IMPLEMENTATION

for (int i = 0; i < n; i++)

{ smallest = i;

for (j=i+1; j<n; j++)

{ if (x[smallest] > x[j])

smallest = j; }

if (smallest != i)

{ temp = x[i];

x[i] = x[smallest];

x[smallest] = temp;

## }

## FIGURE: 1.3 Selection Sorting

## 2.6.2 ADVANTAGES OF SELCTION SORT

It does not depend on the initial arrangement of the data.

Easy to implement

In-place sort (requires no additional storage space).

## 2.6.3 DISADVANTAGES OF SELCTION SORT

Its running time depends only slightly on the amount of order already in the file.

The process of finding the minimum element on one pass through the file does not seem to give much information about where the minimum might be on the next pass through the file.

2.7 BUBBLE SORT: Is a simple 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. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted (frederic.et al., 2010).Â

## 2.7.1 IMPLEMENTATION

for (int i = n - 1; i>0; i--)

## {

for (int j = 0; j<i; j++)

## {

if (x[j] > x[j+1])

// swap values j and

// j + 1

## }

## }

## FIGURE: 1.4 Bubble Sorting code

2.7.2 ADVANTGAES OF BUBBLE SORT:

It is easy to write (code)

Â The ability to detect that the list is sorted is efficiently built into the algorithm.

## 2.7.3 DISADVANTGAES OF BUBBLE SORT:

It runs in Big-Theta (n2) time.

2.8 INSERTION SORT: Insertion sortÂ is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists, and often is used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one (Arpita 2010, p.395).

## 2.8.1 IMPLEMENTATION

The code looks like this;

for (int c = 1; c < n; c++)

{ int temp = x[c];

int j = 0;

for (j = c - 1; j >= 0; j--)

## {

if (temp < x[j])

## {

x[j+1] = x[j];

## }

else

break;

## }

x[j+1] = temp;

## }

## FIGURE: 1.5 Insertion Sort

## 2.8.2 ADVANTAGES OF INSERTION

Simple implementation.

Efficient for (quite) small data sets.

Adaptive, i.e. efficient for data sets that are already substantially sorted: theÂ time complexityÂ is O(nÂ +Â d), whereÂ dÂ is the number ofÂ inversions.

More efficient in practice than most other simple quadratic, i.e.Â O(n2) algorithms such asÂ selection sortÂ orÂ bubble sort; the best case (nearly sorted input) isÂ O(n).

Stable, i.e. does not change the relative order of elements with equal keys.

In-place, i.e. only requires a constant amount O(1) of additional memory space.

Online, i.e. can sort a list as it receives it.

## 2.8.3 DISADVANTAGE OF INSERTION

It is less efficient on list containing more number of elements.Â

As the number of elements increases the performance of the program would be slow.Â

Insertion sort needs a large number of element shifts.

## 2.9 Quick Sort: this type of sort is considered to be very efficient,Â with its "divide and conquer" algorithm.Â This sort starts by dividing the original array into two sections (partitions) based upon the value of the first element in the array (mathbits, 2009)

## 2.9.1 Basic features

Similar to mergesort - divide-and-conquer recursive algorithm

One of the fastest sorting algorithms

Average running time O(NlogN)

Worst-case running time O(N2

## 2.9.2 Implementation

Void quicksort (int x[ ], int left, int right)

## {

Int pivot

Partition(x, left, right, pivot);

If (pivot -1>left

## {

quicksort(x, left, pivot);

## }

If (right>pivot+1)

## {

Quicksort(x,pivot+1, right);

## }

## }

## FIGURE: 1.6 Quick Sort

## 2.9.3 Advantages of quick sort

One of the fastest algorithms on average.

Does not need additional memory (the sorting takes place in the array - this is calledÂ in-placeÂ processing). Compare with mergesort: mergesort needs additional memory for merging

## 2.9.4 Disadvantage of Quicksort

The worst-case complexity is O(N2)

## 2.9.5 Complexity of Quicksort

Worst-case: O(N2)

This happens when the pivot is the smallest (or the largest) element.Â

Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements (Lydia, n.d).

Best-case O(NlogN)Â The best case is when the pivot is the median of the array,Â

and then the left and the right part will have same size.

There areÂ logNÂ partitions, and to obtain each partitions we doÂ NÂ comparisonsÂ

(and not more thanÂ N/2Â swaps). Hence the complexity isÂ O(NlogN)

Average-caseÂ -Â O(NlogN)

2.10 SHELL SORT: Â is aÂ sorting algorithm, devised byÂ Donald ShellÂ in 1959, that is a generalization ofÂ insertion sort, which exploits the fact that insertion sort works efficiently on input that is already almost sorted. It improves on insertion sort by allowing the comparison and exchange of elements that are far apart. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted (bogotobogo, 2011).

The idea of Shell sort is the following:

arrange the data sequence in a two-dimensional array

sort the columns of the array

The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column. In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted. However, the number of sorting operations necessary in each step is limited, due to the presortedness of the sequence obtained in the preceding steps.

## 2.10.1 ADVANTAGES

Shell Sort is the best of the O(n2) algorithms.

Shell sort improves on insertion sort by allowing the comparison and exchange of elements that are far apart.

Shell sort is easy to code

A simple change, replacing 2kÂ with 2k-1, improves the worst-case running time to O(N3/2)

It's 5 times faster than the bubble sort and a little over twice as fast as the insertion sort, its closest competitor.

## 2.10.2 DISADVANTAGES

It is not a stable sort.

It's a complex algorithm

It's not efficient as the merge, heap and quick sort.

## 2.10.3 COMPLEXITY

## Best case:

The best case in shell sort is when the array is already sorted in right order. The number comparison is less.

## Average case:

Complexity is O(N logN).

## Worst case:

The running time of shell sort depends on the choice of increment sequence.

The problem with shell increment is that pair of increments is not necessarily relatively prime and smaller increment can have little effect.

## 2.11 Conclusion

The best fitted algorithm according the given requirement is Quick sort as my chosen sorting Algorithm because of several reasons I came across reading about how it works in the World Wide Web, some of this reason are quite complex and some are reasonable.

To start with quick sort is the fastest known comparison based sorting Algorithm, on average and large number of elements like the above scenario sorting 50,000 numerical data which requires 0(n log n) steps.

Quick sorting employs a divide and conquers strategy to relies on partion operation, to partion an array, an element is chosen, called the pivot, all elements are move before the pivot and all greater element are move after it. This can be done effectively in linear time, efficient implementation of quick sort is typically unstable and somewhat complex, but it is the fastest sorting algorithm in practice.

The most popular sorting algorithm and the most complex when choosing a good pivot element, choosing a pivot at random makes it harder to create a performance of 0(N2). Median of tree (first, last, middle) is also a way of avoiding problems.

With more median comparison its better than choosing at random, it's an improvement on the part of picking median (first, last, middle), in the worst case, it can still go 0(N2), but it is a rare case.

For most data, picking the first and last is sufficient, but if worst case scenario arise, the first option would be to pick the central value which has a statistically good pivot for partially sorted data.

If you are sorting a random accessible collection, its general best to pick the physical middle it, with this the data will be sorted or nearly sorted, with this it get the best speed.

## 2.12 Summary

This assignment is consists of two tasks. Task one requires to design, write and produce output of the program that demonstrates queue operations (FIFO) in any programming language, I picked Visual Basic.Net programming language (MS Visual Studio 2011) because the objective of the program to design with attractive interface.

The application design has seven functions which are as follows:

Adding value in queue.

Deleting value in queue.

View the first value in queue.

View last value in queue.

Check if queue values are full.

Empty queue values.

I have deployed the application setup for testing purpose in the cd rom attach to the assignment folder.

Task two requires as analyst programmers in a software development team, to analyse which sorting algorithm is the most suitable and most efficient for sorting up to 50,000 numerical data. a report presenting findings and justifications of selection of the sorting algorithm (any 5 types, the selection criteria are based on complexity, simplicity, and implementation).

Bubble sort

Insertion sort

Shell sort

Quick sort

selection sort

I picked the following sorting algorithm explaining the basic operation and implementation, advantages and disadvantage then for justification I picked quick sorting because it fastest sorting algorithm and it can sort large data, which matches the scenario above to sorting 50,000 numerical data.

Bothe of the tasks is challenging and its give lot of information about concepts of data structure. During the development phase of the program I gain lot of programming skills and knowledge about how to develop the fully functional system.